lemon-project-template-glpk: deps/glpk/examples/todd.mod annotate

lemon-project-template-glpk

Import GLPK 4.47

author	Alpar Juttner <alpar@cs.elte.hu>
date	Sun, 06 Nov 2011 20:59:10 +0100
parents
children

rev	line source
alpar@9	1 /* TODD, a class of hard instances of zero-one knapsack problems */
alpar@9	2
alpar@9	3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
alpar@9	4
alpar@9	5 /* Chvatal describes a class of instances of zero-one knapsack problems
alpar@9	6 due to Todd. He shows that a wide class of algorithms - including all
alpar@9	7 based on branch and bound or dynamic programming - find it difficult
alpar@9	8 to solve problems in the Todd class. More exactly, the time required
alpar@9	9 by these algorithms to solve instances of problems that belong to the
alpar@9	10 Todd class grows as an exponential function of the problem size.
alpar@9	11
alpar@9	12 Reference:
alpar@9	13 Chvatal V. (1980), Hard knapsack problems, Op. Res. 28, 1402-1411. */
alpar@9	14
alpar@9	15 param n > 0 integer;
alpar@9	16
alpar@9	17 param log2_n := log(n) / log(2);
alpar@9	18
alpar@9	19 param k := floor(log2_n);
alpar@9	20
alpar@9	21 param a{j in 1..n} := 2 (k + n + 1) + 2 (k + n + 1 - j) + 1;
alpar@9	22
alpar@9	23 param b := 0.5 * floor(sum{j in 1..n} a[j]);
alpar@9	24
alpar@9	25 var x{1..n} binary;
alpar@9	26
alpar@9	27 maximize obj: sum{j in 1..n} a[j] * x[j];
alpar@9	28
alpar@9	29 s.t. cap: sum{j in 1..n} a[j] * x[j] <= b;
alpar@9	30
alpar@9	31 data;
alpar@9	32
alpar@9	33 param n := 15;
alpar@9	34 /* change this parameter to choose a particular instance */
alpar@9	35
alpar@9	36 end;