lemon-project-template-glpk

comparison deps/glpk/examples/todd.mod @ 9:33de93886c88

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