alpar@1: /* TODD, a class of hard instances of zero-one knapsack problems */
alpar@1: 
alpar@1: /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
alpar@1: 
alpar@1: /* Chvatal describes a class of instances of zero-one knapsack problems
alpar@1:    due to Todd. He shows that a wide class of algorithms - including all
alpar@1:    based on branch and bound or dynamic programming - find it difficult
alpar@1:    to solve problems in the Todd class. More exactly, the time required
alpar@1:    by these algorithms to solve instances of problems that belong to the
alpar@1:    Todd class grows as an exponential function of the problem size.
alpar@1: 
alpar@1:    Reference:
alpar@1:    Chvatal V. (1980), Hard knapsack problems, Op. Res. 28, 1402-1411. */
alpar@1: 
alpar@1: param n > 0 integer;
alpar@1: 
alpar@1: param log2_n := log(n) / log(2);
alpar@1: 
alpar@1: param k := floor(log2_n);
alpar@1: 
alpar@1: param a{j in 1..n} := 2 ** (k + n + 1) + 2 ** (k + n + 1 - j) + 1;
alpar@1: 
alpar@1: param b := 0.5 * floor(sum{j in 1..n} a[j]);
alpar@1: 
alpar@1: var x{1..n} binary;
alpar@1: 
alpar@1: maximize obj: sum{j in 1..n} a[j] * x[j];
alpar@1: 
alpar@1: s.t. cap: sum{j in 1..n} a[j] * x[j] <= b;
alpar@1: 
alpar@1: data;
alpar@1: 
alpar@1: param n := 15;
alpar@1: /* change this parameter to choose a particular instance */
alpar@1: 
alpar@1: end;