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