alpar@9: /* BPP, Bin Packing Problem */
alpar@9: 
alpar@9: /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
alpar@9: 
alpar@9: /* Given a set of items I = {1,...,m} with weight w[i] > 0, the Bin
alpar@9:    Packing Problem (BPP) is to pack the items into bins of capacity c
alpar@9:    in such a way that the number of bins used is minimal. */
alpar@9: 
alpar@9: param m, integer, > 0;
alpar@9: /* number of items */
alpar@9: 
alpar@9: set I := 1..m;
alpar@9: /* set of items */
alpar@9: 
alpar@9: param w{i in 1..m}, > 0;
alpar@9: /* w[i] is weight of item i */
alpar@9: 
alpar@9: param c, > 0;
alpar@9: /* bin capacity */
alpar@9: 
alpar@9: /* We need to estimate an upper bound of the number of bins sufficient
alpar@9:    to contain all items. The number of items m can be used, however, it
alpar@9:    is not a good idea. To obtain a more suitable estimation an easy
alpar@9:    heuristic is used: we put items into a bin while it is possible, and
alpar@9:    if the bin is full, we use another bin. The number of bins used in
alpar@9:    this way gives us a more appropriate estimation. */
alpar@9: 
alpar@9: param z{i in I, j in 1..m} :=
alpar@9: /* z[i,j] = 1 if item i is in bin j, otherwise z[i,j] = 0 */
alpar@9: 
alpar@9:    if i = 1 and j = 1 then 1
alpar@9:    /* put item 1 into bin 1 */
alpar@9: 
alpar@9:    else if exists{jj in 1..j-1} z[i,jj] then 0
alpar@9:    /* if item i is already in some bin, do not put it into bin j */
alpar@9: 
alpar@9:    else if sum{ii in 1..i-1} w[ii] * z[ii,j] + w[i] > c then 0
alpar@9:    /* if item i does not fit into bin j, do not put it into bin j */
alpar@9: 
alpar@9:    else 1;
alpar@9:    /* otherwise put item i into bin j */
alpar@9: 
alpar@9: check{i in I}: sum{j in 1..m} z[i,j] = 1;
alpar@9: /* each item must be exactly in one bin */
alpar@9: 
alpar@9: check{j in 1..m}: sum{i in I} w[i] * z[i,j] <= c;
alpar@9: /* no bin must be overflowed */
alpar@9: 
alpar@9: param n := sum{j in 1..m} if exists{i in I} z[i,j] then 1;
alpar@9: /* determine the number of bins used by the heuristic; obviously it is
alpar@9:    an upper bound of the optimal solution */
alpar@9: 
alpar@9: display n;
alpar@9: 
alpar@9: set J := 1..n;
alpar@9: /* set of bins */
alpar@9: 
alpar@9: var x{i in I, j in J}, binary;
alpar@9: /* x[i,j] = 1 means item i is in bin j */
alpar@9: 
alpar@9: var used{j in J}, binary;
alpar@9: /* used[j] = 1 means bin j contains at least one item */
alpar@9: 
alpar@9: s.t. one{i in I}: sum{j in J} x[i,j] = 1;
alpar@9: /* each item must be exactly in one bin */
alpar@9: 
alpar@9: s.t. lim{j in J}: sum{i in I} w[i] * x[i,j] <= c * used[j];
alpar@9: /* if bin j is used, it must not be overflowed */
alpar@9: 
alpar@9: minimize obj: sum{j in J} used[j];
alpar@9: /* objective is to minimize the number of bins used */
alpar@9: 
alpar@9: data;
alpar@9: 
alpar@9: /* The optimal solution is 3 bins */
alpar@9: 
alpar@9: param m := 6;
alpar@9: 
alpar@9: param w := 1 50, 2 60, 3 30, 4 70, 5 50, 6 40;
alpar@9: 
alpar@9: param c := 100;
alpar@9: 
alpar@9: end;