alpar@1: /* TRICK, A Transportation Design Problem */
alpar@1: 
alpar@1: /* Translated from the Mosel modeling language to GNU MathProg by
alpar@1:    Andrew Makhorin <mao@gnu.org> */
alpar@1: 
alpar@1: /* This example model is described in the article "Formulations and
alpar@1:    Reformulations in Integer Programming" by Michael Trick (it is
alpar@1:    publicly available at http://mat.gsia.cmu.edu/trick/formul04.pdf).
alpar@1: 
alpar@1:    This model demonstrates an amazing effect when including in the
alpar@1:    formulation an additional constraint, which is redundant even for
alpar@1:    LP relaxation, makes the model easy for solving with the B&B. */
alpar@1: 
alpar@1: set TRUCKS := 1..10;
alpar@1: 
alpar@1: set PACKAGES := 1..20;
alpar@1: 
alpar@1: param capacity{TRUCKS};
alpar@1: 
alpar@1: param size{PACKAGES};
alpar@1: 
alpar@1: param cost{TRUCKS};
alpar@1: 
alpar@1: param can_use{PACKAGES, TRUCKS};
alpar@1: 
alpar@1: var x{PACKAGES, TRUCKS}, binary;
alpar@1: 
alpar@1: var y{TRUCKS}, binary;
alpar@1: 
alpar@1: minimize total: sum{i in TRUCKS} cost[i] * y[i];
alpar@1: 
alpar@1: f1{i in TRUCKS}:
alpar@1:       sum{j in PACKAGES} size[j] * x[j,i] <= capacity[i] * y[i];
alpar@1: 
alpar@1: f2{i in TRUCKS, j in PACKAGES}:
alpar@1:       x[j,i] <= y[i];
alpar@1: 
alpar@1: f3{j in PACKAGES}:
alpar@1:       sum{i in TRUCKS} can_use[j,i] * x[j,i] = 1;
alpar@1: 
alpar@1: redundant_constraint:
alpar@1:       sum{i in TRUCKS} capacity[i] * y[i] >= sum{j in PACKAGES} size[j];
alpar@1: 
alpar@1: data;
alpar@1: 
alpar@1: param capacity :=
alpar@1:       [1] 100 [2] 200 [3] 100 [4] 200 [5] 100 [6] 200 [7] 100 [8] 200
alpar@1:       [9] 100 [10] 200;
alpar@1: 
alpar@1: param size :=
alpar@1:       [1] 17 [2] 21 [3] 54 [4] 45 [5] 87 [6] 34 [7] 23 [8] 45 [9] 12
alpar@1:       [10] 43 [11] 54 [12] 39 [13] 31 [14] 26 [15] 75 [16] 48 [17] 16
alpar@1:       [18] 32 [19] 45 [20] 55;
alpar@1: 
alpar@1: param cost :=
alpar@1:       [1] 1 [2] 1.8 [3] 1 [4] 1.8 [5] 1 [6] 1.8 [7] 1 [8] 1.8 [9] 1
alpar@1:       [10] 1.8;
alpar@1: 
alpar@1: param can_use (tr):
alpar@1:       1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 :=
alpar@1:    1  1  1  1  1  1  1  0  0  0  0  1  1  1  1  0  0  0  0  0  0
alpar@1:    2  1  1  1  1  1  1  1  1  0  0  1  1  1  1  1  1  1  0  0  0
alpar@1:    3  0  1  1  1  1  0  0  0  0  0  0  1  1  1  1  1  1  0  0  0
alpar@1:    4  0  0  1  1  1  1  1  1  1  1  0  0  1  1  1  1  1  1  0  0
alpar@1:    5  0  0  1  1  1  1  0  0  0  0  0  0  0  1  1  1  1  1  1  0
alpar@1:    6  0  0  0  1  1  1  1  0  0  0  0  0  0  1  1  1  0  0  0  0
alpar@1:    7  0  0  0  0  1  1  1  1  1  0  0  0  0  0  1  1  1  1  0  0
alpar@1:    8  0  0  0  0  1  1  1  1  1  1  0  0  0  0  0  1  1  1  1  1
alpar@1:    9  0  0  0  0  0  1  1  1  1  0  0  0  0  0  0  0  1  1  1  1
alpar@1:   10  0  0  0  0  0  0  0  1  1  1  0  0  0  0  0  0  0  0  1  1;
alpar@1: 
alpar@1: end;