Bin Packing

For pure bin packing problems some really good heuristics exist. For the problem illustrated in http://www.developerfusion.com/article/5540/bin-packing/ one of the best solutions is:

So if we solve to optimality, do we gain a lot? From http://en.wikipedia.org/wiki/Bin_packing_problem is looks doubtful. Indeed when I solve:

$ontext    Bin packing example $offtext sets    b 'bins' /bin1*bin19/    i 'items' /item1*item45/ ; scalar binsize /80/; parameter itemsize(i) /   item1   26, item2   57, item3   18, item4    8, item5   45   item6   16, item7   22, item8   29, item9    5, item10  11   item11   8, item12  27, item13  54, item14  13, item15  17   item16  21, item17  63, item18  14, item19  16, item20  45   item21   6, item22  32, item23  57, item24  24, item25  18   item26  27, item27  54, item28  35, item29  12, item30  43   item31  36, item32  72, item33  14, item34  28, item35   3   item36  11, item37  46, item38  27, item39  42, item40  59   item41  26, item42  41, item43  15, item44  41, item45  68 /; variables    x(i,b)  'assignment'    y(b)    'whether bin is used'    z       'count used bins' ; binary variable x,y; * relax y: automatically integer y.prior(b) = INF; equations    onebin(i)    cap(b)    binusd    obj    symmetry(b) ; onebin(i)..    sum(b, x(i,b)) =e= 1; cap(b)..       sum(i, x(i,b)*itemsize(i)) =l= binsize; binusd(i,b)..  y(b) =g= x(i,b); obj..          z =e= sum(b, y(b)); symmetry(b+1)..  y(b) =g= y(b+1); model m1 /onebin,cap,binusd,obj/; model m2 /onebin,cap,binusd,obj,symmetry/; option optcr=0; solve m1 minimizing z using mip;

we get an optimal solution with 17 bins.

Of course as discussed in http://yetanothermathprogrammingconsultant.blogspot.com/2011/07/scheduling-of-tv-advertisement-theory.html my real models are almost always much more complicated than shown in these stylized bin packing examples. In those cases a MIP-based solution algorithm can be even more worthwhile than a (simple) heuristic as there is more room for improvement. In the real case we dealt with a complicated multi-objective model where our model seems to outperform the heuristic in almost all objectives. This is the case even after the heuristic was improved using some fine-tuning after looking at our solutions.