[9] | 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; |
---|