|
alpar@1
|
1 |
/* TRICK, A Transportation Design Problem */
|
|
alpar@1
|
2 |
|
|
alpar@1
|
3 |
/* Translated from the Mosel modeling language to GNU MathProg by
|
|
alpar@1
|
4 |
Andrew Makhorin <mao@gnu.org> */
|
|
alpar@1
|
5 |
|
|
alpar@1
|
6 |
/* This example model is described in the article "Formulations and
|
|
alpar@1
|
7 |
Reformulations in Integer Programming" by Michael Trick (it is
|
|
alpar@1
|
8 |
publicly available at http://mat.gsia.cmu.edu/trick/formul04.pdf).
|
|
alpar@1
|
9 |
|
|
alpar@1
|
10 |
This model demonstrates an amazing effect when including in the
|
|
alpar@1
|
11 |
formulation an additional constraint, which is redundant even for
|
|
alpar@1
|
12 |
LP relaxation, makes the model easy for solving with the B&B. */
|
|
alpar@1
|
13 |
|
|
alpar@1
|
14 |
set TRUCKS := 1..10;
|
|
alpar@1
|
15 |
|
|
alpar@1
|
16 |
set PACKAGES := 1..20;
|
|
alpar@1
|
17 |
|
|
alpar@1
|
18 |
param capacity{TRUCKS};
|
|
alpar@1
|
19 |
|
|
alpar@1
|
20 |
param size{PACKAGES};
|
|
alpar@1
|
21 |
|
|
alpar@1
|
22 |
param cost{TRUCKS};
|
|
alpar@1
|
23 |
|
|
alpar@1
|
24 |
param can_use{PACKAGES, TRUCKS};
|
|
alpar@1
|
25 |
|
|
alpar@1
|
26 |
var x{PACKAGES, TRUCKS}, binary;
|
|
alpar@1
|
27 |
|
|
alpar@1
|
28 |
var y{TRUCKS}, binary;
|
|
alpar@1
|
29 |
|
|
alpar@1
|
30 |
minimize total: sum{i in TRUCKS} cost[i] * y[i];
|
|
alpar@1
|
31 |
|
|
alpar@1
|
32 |
f1{i in TRUCKS}:
|
|
alpar@1
|
33 |
sum{j in PACKAGES} size[j] * x[j,i] <= capacity[i] * y[i];
|
|
alpar@1
|
34 |
|
|
alpar@1
|
35 |
f2{i in TRUCKS, j in PACKAGES}:
|
|
alpar@1
|
36 |
x[j,i] <= y[i];
|
|
alpar@1
|
37 |
|
|
alpar@1
|
38 |
f3{j in PACKAGES}:
|
|
alpar@1
|
39 |
sum{i in TRUCKS} can_use[j,i] * x[j,i] = 1;
|
|
alpar@1
|
40 |
|
|
alpar@1
|
41 |
redundant_constraint:
|
|
alpar@1
|
42 |
sum{i in TRUCKS} capacity[i] * y[i] >= sum{j in PACKAGES} size[j];
|
|
alpar@1
|
43 |
|
|
alpar@1
|
44 |
data;
|
|
alpar@1
|
45 |
|
|
alpar@1
|
46 |
param capacity :=
|
|
alpar@1
|
47 |
[1] 100 [2] 200 [3] 100 [4] 200 [5] 100 [6] 200 [7] 100 [8] 200
|
|
alpar@1
|
48 |
[9] 100 [10] 200;
|
|
alpar@1
|
49 |
|
|
alpar@1
|
50 |
param size :=
|
|
alpar@1
|
51 |
[1] 17 [2] 21 [3] 54 [4] 45 [5] 87 [6] 34 [7] 23 [8] 45 [9] 12
|
|
alpar@1
|
52 |
[10] 43 [11] 54 [12] 39 [13] 31 [14] 26 [15] 75 [16] 48 [17] 16
|
|
alpar@1
|
53 |
[18] 32 [19] 45 [20] 55;
|
|
alpar@1
|
54 |
|
|
alpar@1
|
55 |
param cost :=
|
|
alpar@1
|
56 |
[1] 1 [2] 1.8 [3] 1 [4] 1.8 [5] 1 [6] 1.8 [7] 1 [8] 1.8 [9] 1
|
|
alpar@1
|
57 |
[10] 1.8;
|
|
alpar@1
|
58 |
|
|
alpar@1
|
59 |
param can_use (tr):
|
|
alpar@1
|
60 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 :=
|
|
alpar@1
|
61 |
1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0
|
|
alpar@1
|
62 |
2 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0
|
|
alpar@1
|
63 |
3 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0
|
|
alpar@1
|
64 |
4 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0
|
|
alpar@1
|
65 |
5 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0
|
|
alpar@1
|
66 |
6 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0
|
|
alpar@1
|
67 |
7 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0
|
|
alpar@1
|
68 |
8 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1
|
|
alpar@1
|
69 |
9 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1
|
|
alpar@1
|
70 |
10 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1;
|
|
alpar@1
|
71 |
|
|
alpar@1
|
72 |
end;
|