I wrote a Java program to begin analyzing a certain aspect of bin packing my professor mentioned last semester. The version of bin packing investigated is as follows:
Bins hold up to 1.0 of ‘straws’
The size of straws is constrained as low as 0.1 (in my case I used steps of 0.5, so 0.5) and as high as 1.0
Each straw is passed one at a time and placed into the first bin it fits in (or in the case it fits in no existing bin, a new bin is created)
Waste is defined as the amount of empty space in a bin (and therefore the total amount of wasted space across bins for a given run)
Now, the weirdness was a result he encountered when he examined bin packing constrained at 0.1, 0.2, …, 0.9, 1.0 straw sizes. According to him there was a strange lump at 0.8 where there was more waste than at higher and lower values. That is, a maximum formed at 0.8.
My data (below) on a single run reflects similar results. Total waste peaks at 0.8 with a value of 3,263.027; average waste per bin peaks at 0.7 with a value of 0.218; Total bins and average straws per bin do not peak at an unusual place but at the maximum straw size.
These results are typical of my trials (roughly a few dozen). I’ve not yet added functionality to gather and process the data over many trials. The data below represents 20 runs each on 30,000 straws randomly chosen to be greater than zero and less than the straw constraint for that run.
I’ll add a follow-up story to this when I have added the ability to automatically gather the data for runs and created some graphs. I’ll also release my source at that time. And, if I’m feeling lucky I may try to give some simple analysis of why I think this occurs.
A CSV looks to be the easiest way to create the file output from the program and then I’ll import it into OpenOfficeOrg Calc to create graphs.
=== Maximum Straw Size: 0.05 ===
Total Waste: 14.195
Average Waste per bin: 0.019
Total Bins: 766
Average Straws per bin: 39.164=== Maximum Straw Size: 0.1 ===
Total Waste: 51.983
Average Waste per bin: 0.033
Total Bins: 1552
Average Straws per bin: 19.33=== Maximum Straw Size: 0.15 ===
Total Waste: 119.784
Average Waste per bin: 0.05
Total Bins: 2373
Average Straws per bin: 12.642=== Maximum Straw Size: 0.2 ===
Total Waste: 216.584
Average Waste per bin: 0.067
Total Bins: 3216
Average Straws per bin: 9.328=== Maximum Straw Size: 0.25 ===
Total Waste: 338.669
Average Waste per bin: 0.083
Total Bins: 4080
Average Straws per bin: 7.353=== Maximum Straw Size: 0.3 ===
Total Waste: 489.451
Average Waste per bin: 0.099
Total Bins: 4961
Average Straws per bin: 6.047=== Maximum Straw Size: 0.35 ===
Total Waste: 691.107
Average Waste per bin: 0.117
Total Bins: 5928
Average Straws per bin: 5.061=== Maximum Straw Size: 0.4 ===
Total Waste: 941.426
Average Waste per bin: 0.136
Total Bins: 6934
Average Straws per bin: 4.327=== Maximum Straw Size: 0.45 ===
Total Waste: 1,206.66
Average Waste per bin: 0.151
Total Bins: 7968
Average Straws per bin: 3.765=== Maximum Straw Size: 0.5 ===
Total Waste: 1,470.779
Average Waste per bin: 0.163
Total Bins: 9013
Average Straws per bin: 3.329=== Maximum Straw Size: 0.55 ===
Total Waste: 1,808.49
Average Waste per bin: 0.179
Total Bins: 10103
Average Straws per bin: 2.969=== Maximum Straw Size: 0.6 ===
Total Waste: 2,171.645
Average Waste per bin: 0.195
Total Bins: 11135
Average Straws per bin: 2.694=== Maximum Straw Size: 0.65 ===
Total Waste: 2,580.432
Average Waste per bin: 0.209
Total Bins: 12339
Average Straws per bin: 2.431=== Maximum Straw Size: 0.7 ===
Total Waste: 2,926.006
Average Waste per bin: 0.218
Total Bins: 13405
Average Straws per bin: 2.238=== Maximum Straw Size: 0.75 ===
Total Waste: 3,094.46
Average Waste per bin: 0.217
Total Bins: 14245
Average Straws per bin: 2.106=== Maximum Straw Size: 0.8 ===
Total Waste: 3,263.027
Average Waste per bin: 0.213
Total Bins: 15297
Average Straws per bin: 1.961=== Maximum Straw Size: 0.85 ===
Total Waste: 3,257.898
Average Waste per bin: 0.205
Total Bins: 15870
Average Straws per bin: 1.89=== Maximum Straw Size: 0.9 ===
Total Waste: 3,244.492
Average Waste per bin: 0.195
Total Bins: 16675
Average Straws per bin: 1.799=== Maximum Straw Size: 0.95 ===
Total Waste: 3,231.088
Average Waste per bin: 0.185
Total Bins: 17501
Average Straws per bin: 1.714=== Maximum Straw Size: 1.0 ===
Total Waste: 3,037.173
Average Waste per bin: 0.168
Total Bins: 18119
Average Straws per bin: 1.656