A colleague was backing up files to DVDs and wanted to know a good bin-packing heuristic. I pointed him to First-Fit-Decreasing and Best-Fit-Decreasing, nicely described the Wikipedia entry on bin-packing, but suggested as long as he was doing that he ought to try Bubblesearch as well. Recall Bubblesearch just tries random perturbations of the greedy ordering, to try to find a better solution; the full description is in this paper.
His reported results are that with FFD everything fit into 5 DVDs, which was the minimum necessary; but he did find that Bubblesearch improved the utilization of the first 4 DVDs from 94% to 99% (with about 10,000 random perturbations, and some small parameter tuning), which he thought was impressive.
Your mileage my vary, and I'm sure there are better specific heuristics for bin-packing. The point behind Bubblesearch is that it is a natural extension for a wide class of Greedy heuristics, and moreover is really easy to understand and to implement. My completely self-interested and biased opinion is that it (or something like it) should be taught in all undergraduate algorithms classes....
Subscribe to:
Post Comments (Atom)
2 comments:
I would be interested with the result of the output of gaffitter
http://gaffitter.sourceforge.net/ which is utility that solves this
type of problem using genetic algorithms (or optionally first fit).
I have to say, I looked at the page and found it all very confusing. I asked my colleague to take a look, and his comments were:
"Here's my comparison: mine is 397 lines; theirs is 3747 lines.
Reading their source, I was unable to learn the information I most
wanted to know: how much overhead is consumed by the iso9660 metadata
for files." I don't think it excited him -- though this isn't to say it couldn't eke out that last 1% or so of utilization remaining...
Post a Comment