lemon-project-template-glpk

comparison deps/glpk/examples/bpp.mod @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:575deda93e45
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;