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, competing based on the value of the items packed in the knapsack for each problem i (0 ≦ i ≦ m) and the total execution time.

Scoring Rule

Solve all m problems within the time limit. Ranking is based on the total of the m value points plus one time point.

For the quality of results: Score 10 to 1 points based on the value of result.
For calculation time: Programs that score more than 1 point in some problems can earn 10 to 1 points based on speed.

The Condition of Problem

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

Our Solution

We choose between the following two algorithms based on the scale of the problem.

DPA (Dynamic Programming Algorithm)
- Advantages
  - We can certainly obtain an optimul solution.
  - We can predict the calculation time based on the weight limit of knapsacks or the number of objects.
- Defects
  - It is inapplicable to large-scale problems due to high memory usage and time limitations.
DDD (Dynamic Decision Diagram) Algorithm

DDD Algorithm

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

Advantages
- You can solve large-scale problems by limiting leaf nodes.
- Memory efficient
Defects
- It is difficult to determine the number of leaf nodes needed for an optimul solution.

This figure illustrates the DDD creation process for obtaining an optimul solution with three given objects from the table. (Assuming the weight limit w is 4.)

Initially, the DDD consists of two nodes: a root node and a leaf node. A leaf node contains two numerical values: the sum of weights (upper side) and the sum of values (lower side) in the 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 nodes by successively inserting an object between a leaf node and another object node.

If the sum of weights exceeds the weight limit of the knapsack when appending object x₁ or x₂, set the link NULL and do not generate a new leaf node.

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

Finally, find the highest-valued node among all leaf nodes and trace the links back from this node to the root node to obtain the optimul solution.

Using this algorithm, the number of leaf nodes is at most the knapsack's weight limit plus 1. Thus, leaf nodes do not increase explosively as in a traditional Binary Tree. When appending an object to the DDD, only the leaf nodes generated at that moment need processing. In this respect, the DDD algorithm is superior to the DPA.

Most Valuable Selection (MVS)

A large number of objects can create too many leaf nodes during DDD construction. Our algorithm avoids this problem using Most Valuable Selection (MVS).

MVS reduces the number of leaf nodes by grouping them. The following figure shows the condition of the leaf nodes.

The Relationship of Grouping Parameter and Calculation Time

[Diagram of the relationship between the number of objects and the number of groups]

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

For solving the problems 6 to 8 using DPA,

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

Known Problems

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

Shuji Yamamura (yamamu2salia.dj.kit.ac.jp)
Akio Okumura (okumur2aalia.dj.kit.ac.jp)
Takeshi Shimomura (shimom2talia.dj.kit.ac.jp)
Atsushi Nunome (nunome2aalia.dj.kit.ac.jp)

All email addresses listed here are correct at the time of publication and are no longer valid.

Back to ARK