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. */
16 set PACKAGES := 1..20;
18 param capacity{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];
33 sum{j in PACKAGES} size[j] * x[j,i] <= capacity[i] * y[i];
35 f2{i in TRUCKS, j in PACKAGES}:
39 sum{i in TRUCKS} can_use[j,i] * x[j,i] = 1;
42 sum{i in TRUCKS} capacity[i] * y[i] >= sum{j in PACKAGES} size[j];
47 [1] 100 [2] 200 [3] 100 [4] 200 [5] 100 [6] 200 [7] 100 [8] 200
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;
56 [1] 1 [2] 1.8 [3] 1 [4] 1.8 [5] 1 [6] 1.8 [7] 1 [8] 1.8 [9] 1
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;