lemon-project-template-glpk
diff deps/glpk/examples/todd.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/todd.mod Sun Nov 06 20:59:10 2011 +0100 1.3 @@ -0,0 +1,36 @@ 1.4 +/* TODD, a class of hard instances of zero-one knapsack problems */ 1.5 + 1.6 +/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ 1.7 + 1.8 +/* Chvatal describes a class of instances of zero-one knapsack problems 1.9 + due to Todd. He shows that a wide class of algorithms - including all 1.10 + based on branch and bound or dynamic programming - find it difficult 1.11 + to solve problems in the Todd class. More exactly, the time required 1.12 + by these algorithms to solve instances of problems that belong to the 1.13 + Todd class grows as an exponential function of the problem size. 1.14 + 1.15 + Reference: 1.16 + Chvatal V. (1980), Hard knapsack problems, Op. Res. 28, 1402-1411. */ 1.17 + 1.18 +param n > 0 integer; 1.19 + 1.20 +param log2_n := log(n) / log(2); 1.21 + 1.22 +param k := floor(log2_n); 1.23 + 1.24 +param a{j in 1..n} := 2 ** (k + n + 1) + 2 ** (k + n + 1 - j) + 1; 1.25 + 1.26 +param b := 0.5 * floor(sum{j in 1..n} a[j]); 1.27 + 1.28 +var x{1..n} binary; 1.29 + 1.30 +maximize obj: sum{j in 1..n} a[j] * x[j]; 1.31 + 1.32 +s.t. cap: sum{j in 1..n} a[j] * x[j] <= b; 1.33 + 1.34 +data; 1.35 + 1.36 +param n := 15; 1.37 +/* change this parameter to choose a particular instance */ 1.38 + 1.39 +end;