The Details of DDD Algorithm for Parallel Software Contest (PSC'97)

Shuji YAMAMURA, Akio OKUMURA, Takeshi SHIMOMURA, and Atsushi NUNOME

May 29, 1997

Given Problems

Solve m 0/1 knapsack problems and compete on the value of the package packed in the knapsack given by each problem i (0 ≦ i ≦ m) and the total execution time.

Scoring Rule

Solve all m problems within the time limit. You'll be ranked in order of the sum of m value points and one time point.

At the quality of result: Score 10 points to 1 point in order of the value of result.
At calculation time: The program which have been got more than 1 point in some problems can score 10 points to 1 point in order of quickness.

The Condition of Problem

The number of problems m must not exceed 10.
The time limit is over one minute.

Our Solution

We choose one between the following two algorithms in compliance with the scale of a problem.

DPA(Dynamic Programming Algorithm)
- Advantages
  - We can get an optimul solution certainly.
  - We can predict the calculation time owing to the weight limit of knapsacks or the number of objects.
- Defects
  - It is inapplicable to the large scale problem because of the using much memory and the limitation of calculation time.
DDD(Dynamic Decision Diagram) Algorithm

DDD Algorithm

Dynamically construction method of a B-Tree inserting each object
You can get an optimul solution by tracing back the B-Tree from the leaf node.

Advantages
- You can solve a large scale problem by limiting leaf nodes.
- Saving memory
Defects
- It is difficult to decide the number of leaf nodes for getting an optimul solution.

This figure shows the DDD creation process when you get an optimul solution with given three objects in that table. (Provided that the weight limit w is 4.)

In initial condition, the DDD is composed of two nodes, a root node and a leaf node. A leaf node has two numerical information, the sum of weights and the sum of values. The upper side of a leaf node is the sum of weights, and the lower side is the sum of values in that figure.

First, construct the DDD by appending the object x₁. At this time, insert node x₁ between the root node and the leaf node. Then, the figure shows two newly generated nodes. The left one is "the leaf node if you do not append the object x₁", and the right one is "the leaf node if you append the object x₁".

Similarly, construct new node by inserting an object between leaf node and other object node successively.

If the sum of weights have been over the weight limit of the knapsack by appending the object x₁ or x₂, set the link NULL and do not generate new leaf node.

Thus, the following figure shows the final DDD that have been appended all objects.

Finally, find the most-valued node in all leaf nodes and trace back links from the node to the root node. Then, you should get optimul solution.

By using this algorithm, the number of leaf nodes is the knapsack's limited weight + 1 at most. So, the leaf nodes will not increase explosively as you construct a traditional B-Tree. When you append an object to the DDD, you have only to process the leaf nodes which have been generated at that moment. In that respect, DDD algorithm is superior to DPA.

Most Valuable Selection(MVS)

A large number of objects will make too many leaf nodes during DDD construction. So, our algorithm avoids this problem by Most Valuable Selection(MVS).

MVS reduces the leaf node by grouping some leaf nodes. The following figure shows the condition of the leaf nodes.

The Relationship of Grouping Parameter and Calculation Time

Problem Number	1	2	3	4	5	6	7	8	9
The Number of Objects	200	200	200	300	300	42	100	100	500
The Size of Knapsacks	227800	121700	52400	334200	181050	14320	28084	28205	700544
The Number of Groups(Final)	38386	38386	38386	25281	25281	191555	78386	78386	14938
The Number of Groups(Optimul)	832	1255	4764	9033	6706	754	28085	3526	4766
Optimul Time(sec)	0.53	0.79	3.26	8.99	6.60	0.09	7.40	0.91	6.68

Machine: Sun Ultra1(167MHz), 128MB Memory

In case of solving the problem number 6 to 8 with DPA,

Problem Number	6	7	8
Time(sec)	0.91	3.59	3.56

Known Problems

The relevance of an approximate result and the Grouping Parameter is not yet clear.
Parallelized only at problem level.

yamamu2salia.dj.kit.ac.jp
okumur2aalia.dj.kit.ac.jp
shimom2talia.dj.kit.ac.jp
nunome2aalia.dj.kit.ac.jp

Back to ARK