Description

This model implements a simple binary optimization model for the bin packing problem.
It uses embedded code Python to read data from the J.E. Beasley ORLib instance
collection at http://people.brunel.ac.uk/~mastjjb/jeb/orlib/binpackinfo.html.
Moreover, it uses various methods to determine the number of bins required. The number of
bins is required at compile time of GAMS (set j). In default, execution time GAMS code in
an embedded code GAMS section estimates the number of bins.

Large Model of Type : MIP

Category : GAMS Model library

Main file : binpacking.gms   includes :  binpack5.txt

$title Bin packing problem with different ways to estimate number of bins (binpack,SEQ=433)

$onText
This model implements a simple binary optimization model for the bin packing problem.
It uses embedded code Python to read data from the J.E. Beasley ORLib instance
collection at http://people.brunel.ac.uk/~mastjjb/jeb/orlib/binpackinfo.html.
Moreover, it uses various methods to determine the number of bins required. The number of
bins is required at compile time of GAMS (set j). In default, execution time GAMS code in
an embedded code GAMS section estimates the number of bins.
$offText


Set i 'items';
Parameter s(i<) 'item sizes';
Scalar B 'bin capacity';

$if not set instance $set instance binpack5.txt
$onEmbeddedCode Python:
with open('%instance%') as fp:
   s = []
   for i, line in enumerate(fp):
      if i == 2:
         B = float(line.split()[0])
         I = int(line.split()[1])
         gams.set('B',[B])
      elif i >= 3:
         s.append((str(i-2),float(line)))
         if i-2 == I: break
   gams.set('s',s)
$offEmbeddedCode s b

* Randomize the item size
s(i) = uniform(0.9,1.1)*s(i);

$if not set method $set method ecgams
$ifThenI %method%==ecgams
* Use embedded GAMS to use execution time loop for a simple bound on bins
Scalar nj 'number of bins required to pack all items';
$save.keepCode bp
$onEmbeddedCode GAMS: restart=bp
* Implement simple bound on number of bins required
scalar size 'size of the active bin' /0/;
nj = 1;
loop(i, size = size+s(i); if (size>B, nj = nj+1; size = s(i)));
$offEmbeddedCode nj
$eval NJ nj
$elseIfI %method%==sizei
* Use the number of items as bound on number of bins required
$eval NJ card(i)
$elseIfI %method%==fixed
* Use a ratio of items as bound on number of bins (can be too small)
$eval NJ round(card(i)/3)
$elseIfI %method%==explicit
* Use user supplied number of bins (can be too small)
$if not set NJ $set NJ 10
$else
$error 'No valid method selected to estimate number of bins'
$endIf

$log --- This model works with %NJ% bins.

Set j 'bins' / b1*b%NJ% /;

* Simple optimization model to minimize number of bins:
Binary variable y(i,j) 'assignment of item to bin', z(j) 'bin open';
Variable open_bins 'number of open bins';

Equations
    defopen(j) 'allow item in open bins only'
    defone(i)  'assign each item to one bin'
    defobj     'count number of open bins';
    
defopen(j)..   sum(i, s(i)*y(i,j)) =l= z(j)*B;
defone(i)..    sum(j, y(i,j)) =e= 1;
defobj..       open_bins =e= sum(j, z(j));

model bp 'bin packing' /all/;

bp.resLim=10; solve bp min open_bins using mip;
abort$(bp.modelStat <> %modelStat.integerSolution% and
       bp.modelStat <> %modelStat.feasibleSolution% and
       bp.modelStat <> %modelStat.optimal%) 'No integer solution. Perhaps set j (bins) too small';