# source:glpk-cmake/examples/trick.mod@1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

• Generated files and doc/notes are removed
File size: 2.2 KB
Line
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
14set TRUCKS := 1..10;
15
16set PACKAGES := 1..20;
17
18param capacity{TRUCKS};
19
20param size{PACKAGES};
21
22param cost{TRUCKS};
23
24param can_use{PACKAGES, TRUCKS};
25
26var x{PACKAGES, TRUCKS}, binary;
27
28var y{TRUCKS}, binary;
29
30minimize total: sum{i in TRUCKS} cost[i] * y[i];
31
32f1{i in TRUCKS}:
33      sum{j in PACKAGES} size[j] * x[j,i] <= capacity[i] * y[i];
34
35f2{i in TRUCKS, j in PACKAGES}:
36      x[j,i] <= y[i];
37
38f3{j in PACKAGES}:
39      sum{i in TRUCKS} can_use[j,i] * x[j,i] = 1;
40
41redundant_constraint:
42      sum{i in TRUCKS} capacity[i] * y[i] >= sum{j in PACKAGES} size[j];
43
44data;
45
46param capacity :=
47      [1] 100 [2] 200 [3] 100 [4] 200 [5] 100 [6] 200 [7] 100 [8] 200
48      [9] 100 [10] 200;
49
50param 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
55param 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
59param 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
72end;
Note: See TracBrowser for help on using the repository browser.