| [9] | 1 | /* BPP, Bin Packing Problem */ |
|---|
| 2 | |
|---|
| 3 | /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ |
|---|
| 4 | |
|---|
| 5 | /* Given a set of items I = {1,...,m} with weight w[i] > 0, the Bin |
|---|
| 6 | Packing Problem (BPP) is to pack the items into bins of capacity c |
|---|
| 7 | in such a way that the number of bins used is minimal. */ |
|---|
| 8 | |
|---|
| 9 | param m, integer, > 0; |
|---|
| 10 | /* number of items */ |
|---|
| 11 | |
|---|
| 12 | set I := 1..m; |
|---|
| 13 | /* set of items */ |
|---|
| 14 | |
|---|
| 15 | param w{i in 1..m}, > 0; |
|---|
| 16 | /* w[i] is weight of item i */ |
|---|
| 17 | |
|---|
| 18 | param c, > 0; |
|---|
| 19 | /* bin capacity */ |
|---|
| 20 | |
|---|
| 21 | /* We need to estimate an upper bound of the number of bins sufficient |
|---|
| 22 | to contain all items. The number of items m can be used, however, it |
|---|
| 23 | is not a good idea. To obtain a more suitable estimation an easy |
|---|
| 24 | heuristic is used: we put items into a bin while it is possible, and |
|---|
| 25 | if the bin is full, we use another bin. The number of bins used in |
|---|
| 26 | this way gives us a more appropriate estimation. */ |
|---|
| 27 | |
|---|
| 28 | param z{i in I, j in 1..m} := |
|---|
| 29 | /* z[i,j] = 1 if item i is in bin j, otherwise z[i,j] = 0 */ |
|---|
| 30 | |
|---|
| 31 | if i = 1 and j = 1 then 1 |
|---|
| 32 | /* put item 1 into bin 1 */ |
|---|
| 33 | |
|---|
| 34 | else if exists{jj in 1..j-1} z[i,jj] then 0 |
|---|
| 35 | /* if item i is already in some bin, do not put it into bin j */ |
|---|
| 36 | |
|---|
| 37 | else if sum{ii in 1..i-1} w[ii] * z[ii,j] + w[i] > c then 0 |
|---|
| 38 | /* if item i does not fit into bin j, do not put it into bin j */ |
|---|
| 39 | |
|---|
| 40 | else 1; |
|---|
| 41 | /* otherwise put item i into bin j */ |
|---|
| 42 | |
|---|
| 43 | check{i in I}: sum{j in 1..m} z[i,j] = 1; |
|---|
| 44 | /* each item must be exactly in one bin */ |
|---|
| 45 | |
|---|
| 46 | check{j in 1..m}: sum{i in I} w[i] * z[i,j] <= c; |
|---|
| 47 | /* no bin must be overflowed */ |
|---|
| 48 | |
|---|
| 49 | param n := sum{j in 1..m} if exists{i in I} z[i,j] then 1; |
|---|
| 50 | /* determine the number of bins used by the heuristic; obviously it is |
|---|
| 51 | an upper bound of the optimal solution */ |
|---|
| 52 | |
|---|
| 53 | display n; |
|---|
| 54 | |
|---|
| 55 | set J := 1..n; |
|---|
| 56 | /* set of bins */ |
|---|
| 57 | |
|---|
| 58 | var x{i in I, j in J}, binary; |
|---|
| 59 | /* x[i,j] = 1 means item i is in bin j */ |
|---|
| 60 | |
|---|
| 61 | var used{j in J}, binary; |
|---|
| 62 | /* used[j] = 1 means bin j contains at least one item */ |
|---|
| 63 | |
|---|
| 64 | s.t. one{i in I}: sum{j in J} x[i,j] = 1; |
|---|
| 65 | /* each item must be exactly in one bin */ |
|---|
| 66 | |
|---|
| 67 | s.t. lim{j in J}: sum{i in I} w[i] * x[i,j] <= c * used[j]; |
|---|
| 68 | /* if bin j is used, it must not be overflowed */ |
|---|
| 69 | |
|---|
| 70 | minimize obj: sum{j in J} used[j]; |
|---|
| 71 | /* objective is to minimize the number of bins used */ |
|---|
| 72 | |
|---|
| 73 | data; |
|---|
| 74 | |
|---|
| 75 | /* The optimal solution is 3 bins */ |
|---|
| 76 | |
|---|
| 77 | param m := 6; |
|---|
| 78 | |
|---|
| 79 | param w := 1 50, 2 60, 3 30, 4 70, 5 50, 6 40; |
|---|
| 80 | |
|---|
| 81 | param c := 100; |
|---|
| 82 | |
|---|
| 83 | end; |
|---|
