lemon-project-template-glpk
view deps/glpk/examples/trick.mod @ 11:4fc6ad2fb8a6
Test GLPK in src/main.cc
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 21:43:29 +0100 |
| parents | |
| children |
line source
1 /* TRICK, A Transportation Design Problem */
3 /* Translated from the Mosel modeling language to GNU MathProg by
4 Andrew Makhorin <mao@gnu.org> */
6 /* This example model is described in the article "Formulations and
7 Reformulations in Integer Programming" by Michael Trick (it is
8 publicly available at http://mat.gsia.cmu.edu/trick/formul04.pdf).
10 This model demonstrates an amazing effect when including in the
11 formulation an additional constraint, which is redundant even for
12 LP relaxation, makes the model easy for solving with the B&B. */
14 set TRUCKS := 1..10;
16 set PACKAGES := 1..20;
18 param capacity{TRUCKS};
20 param size{PACKAGES};
22 param cost{TRUCKS};
24 param can_use{PACKAGES, TRUCKS};
26 var x{PACKAGES, TRUCKS}, binary;
28 var y{TRUCKS}, binary;
30 minimize total: sum{i in TRUCKS} cost[i] * y[i];
32 f1{i in TRUCKS}:
33 sum{j in PACKAGES} size[j] * x[j,i] <= capacity[i] * y[i];
35 f2{i in TRUCKS, j in PACKAGES}:
36 x[j,i] <= y[i];
38 f3{j in PACKAGES}:
39 sum{i in TRUCKS} can_use[j,i] * x[j,i] = 1;
41 redundant_constraint:
42 sum{i in TRUCKS} capacity[i] * y[i] >= sum{j in PACKAGES} size[j];
44 data;
46 param capacity :=
47 [1] 100 [2] 200 [3] 100 [4] 200 [5] 100 [6] 200 [7] 100 [8] 200
48 [9] 100 [10] 200;
50 param size :=
51 [1] 17 [2] 21 [3] 54 [4] 45 [5] 87 [6] 34 [7] 23 [8] 45 [9] 12
52 [10] 43 [11] 54 [12] 39 [13] 31 [14] 26 [15] 75 [16] 48 [17] 16
53 [18] 32 [19] 45 [20] 55;
55 param cost :=
56 [1] 1 [2] 1.8 [3] 1 [4] 1.8 [5] 1 [6] 1.8 [7] 1 [8] 1.8 [9] 1
57 [10] 1.8;
59 param can_use (tr):
60 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 :=
61 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0
62 2 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0
63 3 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0
64 4 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0
65 5 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0
66 6 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0
67 7 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0
68 8 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1
69 9 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1
70 10 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1;
72 end;