ExactBinPackLab: An Exhaustive Search Algorithm for Bin Packing
About the Lab
The One-Dimensional Bin Packing Problem is: given a list of
n weights in the range
lo,
hi, to pack the
weights into unit-capacity bins so as to minimize the total number
of bins used. Bin Packing is NP-Hard.
This lab contains generators and code
for an exhaustive-search algorithm
for bin packing. The algorithm generates every permutation of the list, and
for each, then applies the Next Fit packing rule. This guarantees
to find the optimal packing, but it takes exponential time.
Resources and Links
There are 4 versions of the algorithm, written in Java. A generator
of random uniform lists on (0,1) is internal to the code.
Projects
- How much improvement in (number of recursive stages) does each algorithm tuneup yield? For
which values of n and/or u are the tuneups most effective?
- Apply additional algorithm and code-tuning ideas suggested in the book (pruning, changing
computation order, cutoffs at small problem sizes, collapsing hierarchies, ...).
How much more speed can you squeeze out of this algorithim?
- Getting good timing statistics for Java programs is notoriously difficult, because of the
use of the Virtual Machine, and extra features like garbage collection. Try different profilers
and timing tools, and see which ones give you the best accuracy and precision. How much variation
among platforms is there, when you run identical processes.
- Re-implement the algorithms in C++ and compare computation times.