lemon-project-template-glpk
view deps/glpk/examples/trick.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 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;