COS 226 Programming Assignment Checklist: Bin Packing

Here are the main goals of the assignment.

• Use a priority queue in an interesting domain.
• Use a list.
• Create a dynamically resizable array.
• Use a heuristic for an NP-hard combinatorial optimization problem.

My program doesn't compile when I hit the Compile button on the Web submission system. Is this OK? No. You will lose a substantial number of points if you don't follow the instructions.

Do I need to use a binary heap? No, that's just a suggestion, but probably a good one. However, you should be able to handle the large instances (a million weights).

Can I use the Java library LinkedList or ArrayList to store the files associated with each disk? Yes, and you are encouraged to use Java's foreach syntax to iterate through the elements when printing them out.

Am I required to format the list of file sizes exactly as in the reference solution? No, this is not a requirement. For C programmers, Java 1.5 contains methods System.out.printf and String.format that work much like printf.

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 ADT, a template readme.txt file.

• Implement IntegerSorter.java. Read in the data from standard input, put it in an integer array, and use the system sort. The main challenge is that you don't know how many integers you'll be reading in. Use a repeated-doubling strategy to dynamically resize the array as needed.

• Create a data type Disk.java to represent a disk. For now, give it a data member to store the amount of space left (and possibly a unique id for use in debugging). Make Disk implement the Comparable interface so that you will be able to insert disks onto a priority queue. Also, include a toString method for debugging and to produce the required output.

• 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. You may wish to add some (very minor) functionality to your priority queue interface.

• Modify Disk.java so that each Disk stores a list of the sound file sizes that it stores, say using an ArrayList. 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.

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.