COIN-OR::LEMON - Graph Library

source: glpk-cmake/examples/todd.mod @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 1.0 KB
Line 
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
15param n > 0 integer;
16
17param log2_n := log(n) / log(2);
18
19param k := floor(log2_n);
20
21param a{j in 1..n} := 2 ** (k + n + 1) + 2 ** (k + n + 1 - j) + 1;
22
23param b := 0.5 * floor(sum{j in 1..n} a[j]);
24
25var x{1..n} binary;
26
27maximize obj: sum{j in 1..n} a[j] * x[j];
28
29s.t. cap: sum{j in 1..n} a[j] * x[j] <= b;
30
31data;
32
33param n := 15;
34/* change this parameter to choose a particular instance */
35
36end;
Note: See TracBrowser for help on using the repository browser.