|
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; |