|
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; |