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