summaryrefslogtreecommitdiff
path: root/glpk-5.0/examples/trick.mod
diff options
context:
space:
mode:
authorPasha <pasha@member.fsf.org>2023-01-27 00:54:07 +0000
committerPasha <pasha@member.fsf.org>2023-01-27 00:54:07 +0000
commitef800d4ffafdbde7d7a172ad73bd984b1695c138 (patch)
tree920cc189130f1e98f252283fce94851443641a6d /glpk-5.0/examples/trick.mod
parentec4ae3c2b5cb0e83fb667f14f832ea94f68ef075 (diff)
downloadoneapi-master.tar.gz
oneapi-master.tar.bz2
simplex-glpk with modified glpk for fpgaHEADmaster
Diffstat (limited to 'glpk-5.0/examples/trick.mod')
-rw-r--r--glpk-5.0/examples/trick.mod72
1 files changed, 72 insertions, 0 deletions
diff --git a/glpk-5.0/examples/trick.mod b/glpk-5.0/examples/trick.mod
new file mode 100644
index 0000000..df5717b
--- /dev/null
+++ b/glpk-5.0/examples/trick.mod
@@ -0,0 +1,72 @@
+/* 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;