1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/examples/bpp.mod	Mon Dec 06 13:09:21 2010 +0100
     1.3 @@ -0,0 +1,83 @@
     1.4 +/* BPP, Bin Packing Problem */
     1.5 +
     1.6 +/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
     1.7 +
     1.8 +/* Given a set of items I = {1,...,m} with weight w[i] > 0, the Bin
     1.9 +   Packing Problem (BPP) is to pack the items into bins of capacity c
    1.10 +   in such a way that the number of bins used is minimal. */
    1.11 +
    1.12 +param m, integer, > 0;
    1.13 +/* number of items */
    1.14 +
    1.15 +set I := 1..m;
    1.16 +/* set of items */
    1.17 +
    1.18 +param w{i in 1..m}, > 0;
    1.19 +/* w[i] is weight of item i */
    1.20 +
    1.21 +param c, > 0;
    1.22 +/* bin capacity */
    1.23 +
    1.24 +/* We need to estimate an upper bound of the number of bins sufficient
    1.25 +   to contain all items. The number of items m can be used, however, it
    1.26 +   is not a good idea. To obtain a more suitable estimation an easy
    1.27 +   heuristic is used: we put items into a bin while it is possible, and
    1.28 +   if the bin is full, we use another bin. The number of bins used in
    1.29 +   this way gives us a more appropriate estimation. */
    1.30 +
    1.31 +param z{i in I, j in 1..m} :=
    1.32 +/* z[i,j] = 1 if item i is in bin j, otherwise z[i,j] = 0 */
    1.33 +
    1.34 +   if i = 1 and j = 1 then 1
    1.35 +   /* put item 1 into bin 1 */
    1.36 +
    1.37 +   else if exists{jj in 1..j-1} z[i,jj] then 0
    1.38 +   /* if item i is already in some bin, do not put it into bin j */
    1.39 +
    1.40 +   else if sum{ii in 1..i-1} w[ii] * z[ii,j] + w[i] > c then 0
    1.41 +   /* if item i does not fit into bin j, do not put it into bin j */
    1.42 +
    1.43 +   else 1;
    1.44 +   /* otherwise put item i into bin j */
    1.45 +
    1.46 +check{i in I}: sum{j in 1..m} z[i,j] = 1;
    1.47 +/* each item must be exactly in one bin */
    1.48 +
    1.49 +check{j in 1..m}: sum{i in I} w[i] * z[i,j] <= c;
    1.50 +/* no bin must be overflowed */
    1.51 +
    1.52 +param n := sum{j in 1..m} if exists{i in I} z[i,j] then 1;
    1.53 +/* determine the number of bins used by the heuristic; obviously it is
    1.54 +   an upper bound of the optimal solution */
    1.55 +
    1.56 +display n;
    1.57 +
    1.58 +set J := 1..n;
    1.59 +/* set of bins */
    1.60 +
    1.61 +var x{i in I, j in J}, binary;
    1.62 +/* x[i,j] = 1 means item i is in bin j */
    1.63 +
    1.64 +var used{j in J}, binary;
    1.65 +/* used[j] = 1 means bin j contains at least one item */
    1.66 +
    1.67 +s.t. one{i in I}: sum{j in J} x[i,j] = 1;
    1.68 +/* each item must be exactly in one bin */
    1.69 +
    1.70 +s.t. lim{j in J}: sum{i in I} w[i] * x[i,j] <= c * used[j];
    1.71 +/* if bin j is used, it must not be overflowed */
    1.72 +
    1.73 +minimize obj: sum{j in J} used[j];
    1.74 +/* objective is to minimize the number of bins used */
    1.75 +
    1.76 +data;
    1.77 +
    1.78 +/* The optimal solution is 3 bins */
    1.79 +
    1.80 +param m := 6;
    1.81 +
    1.82 +param w := 1 50, 2 60, 3 30, 4 70, 5 50, 6 40;
    1.83 +
    1.84 +param c := 100;
    1.85 +
    1.86 +end;