lemon-project-template-glpk

annotate deps/glpk/examples/trick.mod @ 10:5545663ca997

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