lemon-project-template-glpk
diff deps/glpk/examples/trick.mod @ 9:33de93886c88
Import GLPK 4.47
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 20:59:10 +0100 |
parents | |
children |
line diff
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;