lemon-project-template-glpk

comparison deps/glpk/examples/min01ks.mod @ 11:4fc6ad2fb8a6

find changesets by author, revision, files, or words in the commit message
Test GLPK in src/main.cc
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 21:43:29 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:e55381c005d9
1 /* min01ks.mod - finding minimal equivalent 0-1 knapsack inequality */
2
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
4
5 /* It is obvious that for a given 0-1 knapsack inequality
6
7 a[1] x[1] + ... + a[n] x[n] <= b, x[j] in {0, 1} (1)
8
9 there exist infinitely many equivalent inequalities with exactly the
10 same feasible solutions.
11
12 Given a[j]'s and b this model allows to find an inequality
13
14 alfa[1] x[1] + ... + alfa[n] x[n] <= beta, x[j] in {0, 1}, (2)
15
16 which is equivalent to (1) and where alfa[j]'s and beta are smallest
17 non-negative integers.
18
19 This model has the following formulation:
20
21 minimize
22
23 z = |alfa[1]| + ... + |alfa[n]| + |beta| = (3)
24
25 = alfa[1] + ... + alfa[n] + beta
26
27 subject to
28
29 alfa[1] x[1] + ... + alfa[n] x[n] <= beta (4)
30
31 for all x satisfying to (1)
32
33 alfa[1] x[1] + ... + alfa[n] x[n] >= beta + 1 (5)
34
35 for all x not satisfying to (1)
36
37 alfa[1], ..., alfa[n], beta are non-negative integers.
38
39 Note that this model has n+1 variables and 2^n constraints.
40
41 It is interesting, as noticed in [1] and explained in [2], that
42 in most cases LP relaxation of the MIP formulation above has integer
43 optimal solution.
44
45 References
46
47 1. G.H.Bradley, P.L.Hammer, L.Wolsey, "Coefficient Reduction for
48 Inequalities in 0-1 Variables", Math.Prog.7 (1974), 263-282.
49
50 2. G.J.Koehler, "A Study on Coefficient Reduction of Binary Knapsack
51 Inequalities", University of Florida, 2001. */
52
53 param n, integer, > 0;
54 /* number of variables in the knapsack inequality */
55
56 set N := 1..n;
57 /* set of knapsack items */
58
59 /* all binary n-vectors are numbered by 0, 1, ..., 2^n-1, where vector
60 0 is 00...00, vector 1 is 00...01, etc. */
61
62 set U := 0..2^n-1;
63 /* set of numbers of all binary n-vectors */
64
65 param x{i in U, j in N}, binary, := (i div 2^(j-1)) mod 2;
66 /* x[i,j] is j-th component of i-th binary n-vector */
67
68 param a{j in N}, >= 0;
69 /* original coefficients */
70
71 param b, >= 0;
72 /* original right-hand side */
73
74 set D := setof{i in U: sum{j in N} a[j] * x[i,j] <= b} i;
75 /* set of numbers of binary n-vectors, which (vectors) are feasible,
76 i.e. satisfy to the original knapsack inequality (1) */
77
78 var alfa{j in N}, integer, >= 0;
79 /* coefficients to be found */
80
81 var beta, integer, >= 0;
82 /* right-hand side to be found */
83
84 minimize z: sum{j in N} alfa[j] + beta; /* (3) */
85
86 phi{i in D}: sum{j in N} alfa[j] * x[i,j] <= beta; /* (4) */
87
88 psi{i in U diff D}: sum{j in N} alfa[j] * x[i,j] >= beta + 1; /* (5) */
89
90 solve;
91
92 printf "\nOriginal 0-1 knapsack inequality:\n";
93 for {j in 1..n} printf (if j = 1 then "" else " + ") & "%g x%d",
94 a[j], j;
95 printf " <= %g\n", b;
96 printf "\nMinimized equivalent inequality:\n";
97 for {j in 1..n} printf (if j = 1 then "" else " + ") & "%g x%d",
98 alfa[j], j;
99 printf " <= %g\n\n", beta;
100
101 data;
102
103 /* These data correspond to the very first example from [1]. */
104
105 param n := 8;
106
107 param a := [1]65, [2]64, [3]41, [4]22, [5]13, [6]12, [7]8, [8]2;
108
109 param b := 80;
110
111 end;