lemon-project-template-glpk

view deps/glpk/examples/trick.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
line source
1 /* TRICK, A Transportation Design Problem */
2
3 /* Translated from the Mosel modeling language to GNU MathProg by
4 Andrew Makhorin <mao@gnu.org> */
5
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).
9
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. */
13
14 set TRUCKS := 1..10;
15
16 set PACKAGES := 1..20;
17
18 param capacity{TRUCKS};
19
20 param size{PACKAGES};
21
22 param cost{TRUCKS};
23
24 param can_use{PACKAGES, TRUCKS};
25
26 var x{PACKAGES, TRUCKS}, binary;
27
28 var y{TRUCKS}, binary;
29
30 minimize total: sum{i in TRUCKS} cost[i] * y[i];
31
32 f1{i in TRUCKS}:
33 sum{j in PACKAGES} size[j] * x[j,i] <= capacity[i] * y[i];
34
35 f2{i in TRUCKS, j in PACKAGES}:
36 x[j,i] <= y[i];
37
38 f3{j in PACKAGES}:
39 sum{i in TRUCKS} can_use[j,i] * x[j,i] = 1;
40
41 redundant_constraint:
42 sum{i in TRUCKS} capacity[i] * y[i] >= sum{j in PACKAGES} size[j];
43
44 data;
45
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;
49
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;
54
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;
58
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;
71
72 end;