Monday, August 15, 2011

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.