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