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

Import glpk4.45
 Generated files and doc/notes are removed

File size:
1.0 KB

Line  

1  /* TODD, a class of hard instances of zeroone knapsack problems */ 

2  

3  /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ 

4  

5  /* Chvatal describes a class of instances of zeroone 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, 14021411. */ 

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; 

Note: See
TracBrowser
for help on using the repository browser.