1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/examples/trick.mod	Sun Nov 06 20:59:10 2011 +0100
     1.3 @@ -0,0 +1,72 @@
     1.4 +/* TRICK, A Transportation Design Problem */
     1.5 +
     1.6 +/* Translated from the Mosel modeling language to GNU MathProg by
     1.7 +   Andrew Makhorin <mao@gnu.org> */
     1.8 +
     1.9 +/* This example model is described in the article "Formulations and
    1.10 +   Reformulations in Integer Programming" by Michael Trick (it is
    1.11 +   publicly available at http://mat.gsia.cmu.edu/trick/formul04.pdf).
    1.12 +
    1.13 +   This model demonstrates an amazing effect when including in the
    1.14 +   formulation an additional constraint, which is redundant even for
    1.15 +   LP relaxation, makes the model easy for solving with the B&B. */
    1.16 +
    1.17 +set TRUCKS := 1..10;
    1.18 +
    1.19 +set PACKAGES := 1..20;
    1.20 +
    1.21 +param capacity{TRUCKS};
    1.22 +
    1.23 +param size{PACKAGES};
    1.24 +
    1.25 +param cost{TRUCKS};
    1.26 +
    1.27 +param can_use{PACKAGES, TRUCKS};
    1.28 +
    1.29 +var x{PACKAGES, TRUCKS}, binary;
    1.30 +
    1.31 +var y{TRUCKS}, binary;
    1.32 +
    1.33 +minimize total: sum{i in TRUCKS} cost[i] * y[i];
    1.34 +
    1.35 +f1{i in TRUCKS}:
    1.36 +      sum{j in PACKAGES} size[j] * x[j,i] <= capacity[i] * y[i];
    1.37 +
    1.38 +f2{i in TRUCKS, j in PACKAGES}:
    1.39 +      x[j,i] <= y[i];
    1.40 +
    1.41 +f3{j in PACKAGES}:
    1.42 +      sum{i in TRUCKS} can_use[j,i] * x[j,i] = 1;
    1.43 +
    1.44 +redundant_constraint:
    1.45 +      sum{i in TRUCKS} capacity[i] * y[i] >= sum{j in PACKAGES} size[j];
    1.46 +
    1.47 +data;
    1.48 +
    1.49 +param capacity :=
    1.50 +      [1] 100 [2] 200 [3] 100 [4] 200 [5] 100 [6] 200 [7] 100 [8] 200
    1.51 +      [9] 100 [10] 200;
    1.52 +
    1.53 +param size :=
    1.54 +      [1] 17 [2] 21 [3] 54 [4] 45 [5] 87 [6] 34 [7] 23 [8] 45 [9] 12
    1.55 +      [10] 43 [11] 54 [12] 39 [13] 31 [14] 26 [15] 75 [16] 48 [17] 16
    1.56 +      [18] 32 [19] 45 [20] 55;
    1.57 +
    1.58 +param cost :=
    1.59 +      [1] 1 [2] 1.8 [3] 1 [4] 1.8 [5] 1 [6] 1.8 [7] 1 [8] 1.8 [9] 1
    1.60 +      [10] 1.8;
    1.61 +
    1.62 +param can_use (tr):
    1.63 +      1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 :=
    1.64 +   1  1  1  1  1  1  1  0  0  0  0  1  1  1  1  0  0  0  0  0  0
    1.65 +   2  1  1  1  1  1  1  1  1  0  0  1  1  1  1  1  1  1  0  0  0
    1.66 +   3  0  1  1  1  1  0  0  0  0  0  0  1  1  1  1  1  1  0  0  0
    1.67 +   4  0  0  1  1  1  1  1  1  1  1  0  0  1  1  1  1  1  1  0  0
    1.68 +   5  0  0  1  1  1  1  0  0  0  0  0  0  0  1  1  1  1  1  1  0
    1.69 +   6  0  0  0  1  1  1  1  0  0  0  0  0  0  1  1  1  0  0  0  0
    1.70 +   7  0  0  0  0  1  1  1  1  1  0  0  0  0  0  1  1  1  1  0  0
    1.71 +   8  0  0  0  0  1  1  1  1  1  1  0  0  0  0  0  1  1  1  1  1
    1.72 +   9  0  0  0  0  0  1  1  1  1  0  0  0  0  0  0  0  1  1  1  1
    1.73 +  10  0  0  0  0  0  0  0  1  1  1  0  0  0  0  0  0  0  0  1  1;
    1.74 +
    1.75 +end;