1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/examples/todd.mod	Mon Dec 06 13:09:21 2010 +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;