lemon-project-template-glpk
diff deps/glpk/examples/bpp.mod @ 9:33de93886c88
Import GLPK 4.47
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 20:59:10 +0100 |
parents | |
children |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/deps/glpk/examples/bpp.mod Sun Nov 06 20:59:10 2011 +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;