COS 226 Programming Assignment Checklist: Bin Packing

Goals

Here are the main goals of the assignment.

• Use a priority queue and a binary search tree in an interesting domain.
• Use iterators.
• Implement heuristics for an NP-hard combinatorial optimization problem.

Do I need to use a binary heap for worst-fit and a binary search tree for best-fit? No, these are just a suggestion, but probably good ones. However, you should be able to handle the large instances (a million weights).

Can I use an Iterable collection such as Queue or java.util.LinkedList to store the list of files associated with each disk? Absolutely. Now that you know how to implement it, we encourage you to take advantage of Java's foreach loops.

Am I required to format the list of file sizes exactly as in the reference solution? No, this is not a requirement, but we recommend using StdOut.printf() and String.format().

My Disk data type is mutable, but I am using it as the key in a priority queue or symbol table. Will that create a problem? No, provided you are careful not to mutate a Disk while it is on the data structure. Instead, remove it from the data structure, mutate it, and then reinsert it.

How should I implement the ceiling function for the best-fit heuristic? To do it efficiently, use a (balanced) binary search tree. The sorted symbol table and sorted set data types (ST.java and SET.java) provide this functionality. However, these data structures prohibit duplicate keys, e.g., two disks with the same remaining capacity. There are a number of work-a-rounds. One approach is to modify the compareTo() method in Disk to use a unique id field to break ties when two Disk objects have the same remaining capacity. Another approach is to create a separate data structure, say MultiSET.java, that allows duplicate keys.

I get the error "foreach not applicable to expression type" when I compile SET.java. What am I doing wrong? There was a bug in an early version of DrJava. Try compiling from the command-line or downloading the latest version of DrJava.

How do I ask Java for more memory? Use the -Xmx flag. For example, the following asks Java for 100MB of space.

% java -Xmx100m BestFit < input20.txt

Is there an input on which best-fit decreasing will give a suboptimal solution? Yes, there are many. Here's a short one { 400000, 400000, 300000, 300000, 300000, 300000}.

Input, Output, and Testing

Input.   Your program should read in a sequence of integers between 0 and 1000000 separated by whitespace from standard input. Here are some sample input files. You may also use Generator.java to generate random test instances. It takes 3 command line inputs N, L, and U, and generates N pseudorandom integers between L and U.

Reference solutions.   For reference, we provide our executable code for the two heuristics on Windows, Solaris, and OS X. Choose the version of worstfit226 for your operating system and execute with worstfit226 < input.txt. Note that these programs were written in C, so you may see slightly different behavior, e.g., the formatting of the numbers. Also, the priority queue is not "stable", so although the remaining capacities of all the disk should match, you may get different file sizes on some disks.

readme.txt

You may use the following readme file template. Besides providing details about your implementation which are not clear from the comments within your source code, your readme.txt file should also contain:

• For the analysis, generate some input files with random file sizes between 0 and 200000, and between 100000 and 700000 using Generator.java. Create two tables (one for each class of inputs) as follows: for each value of N = 100, 1000, 10000, 100000, 1000000, print the total of the file sizes (in GB), the number of disks used by worst-fit and worst-fit decreasing (even better if you report the average over several random trials for each value of N). Print the running time in seconds for worst-fit.

• Discuss the relative effectiveness of the heuristics. The number of disks is the most important factor, but you should also comment the running time.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

• Download the directory bins to your system. It contains a number of sample input files, a problem instance generator, a priority queue data type, and a template readme.txt file.

• Create a data type Disk.java to represent a disk. For now, give it an instance variable to store the amount of space left (and possibly a unique id for use in debugging). Make Disk implement the Comparable<Disk> interface so that you will be able to insert disks into a priority queue or sorted symbol table. Also, include a toString() method for debugging and to produce the required output. Use the method String.format() to format the output nicely.

• Worst-fit heuristic.

  • Write the client program WorstFit.java to implement the worst-fit algorithm. But only keep track of the remaining space in each disk, instead of remembering which sound file sizes go which disks.

  • Modify Disk.java so that each Disk stores a list of the sound file sizes that it stores, say using a Sequence or java.util.LinkedList. Include a method to add an (integer) sound file size to the disk.

  • Update WorstFit.java so that it adds sound file sizes to the appropriate disks.

  • Test your programs on a variety of input data.

• Best-fit heuristic.

  • Copy WorstFit.java to BestFit.java.

• Implement IntegerReverseSorter.java. If you use MaxPQ, it will be just a few lines of code.

Researchers have proved some amazing things about bin packing heuristics. For example, if the optimal packing uses B bins then the best-fit decreasing algorithm is guaranteed to use no more than 11B/9 + 1 bins (within 22% of best possible). The original proof of this result (for the first-fit decreasing heuristic) required over 70 pages of analysis! The file worstcase30.txt gives a worst-case instance where the best-fit decreasing algorithm uses 11 bins even though the weights fit snugly into 9 bins.