Bin Packing
Some experiments and thoughts with bin packing. Do sizes of objects vs. bins make more difference than it seems?
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.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)
=== 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