|
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; |