1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/examples/min01ks.mod	Mon Dec 06 13:09:21 2010 +0100
     1.3 @@ -0,0 +1,111 @@
     1.4 +/* min01ks.mod - finding minimal equivalent 0-1 knapsack inequality */
     1.5 +
     1.6 +/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
     1.7 +
     1.8 +/* It is obvious that for a given 0-1 knapsack inequality
     1.9 +
    1.10 +      a[1] x[1] + ... + a[n] x[n] <= b,  x[j] in {0, 1}              (1)
    1.11 +
    1.12 +   there exist infinitely many equivalent inequalities with exactly the
    1.13 +   same feasible solutions.
    1.14 +
    1.15 +   Given a[j]'s and b this model allows to find an inequality
    1.16 +
    1.17 +      alfa[1] x[1] + ... + alfa[n] x[n] <= beta,  x[j] in {0, 1},    (2)
    1.18 +
    1.19 +   which is equivalent to (1) and where alfa[j]'s and beta are smallest
    1.20 +   non-negative integers.
    1.21 +
    1.22 +   This model has the following formulation:
    1.23 +
    1.24 +      minimize
    1.25 +
    1.26 +         z = |alfa[1]| + ... + |alfa[n]| + |beta| =                  (3)
    1.27 +
    1.28 +           = alfa[1] + ... + alfa[n] + beta
    1.29 +
    1.30 +      subject to
    1.31 +
    1.32 +         alfa[1] x[1] + ... + alfa[n] x[n] <= beta                   (4)
    1.33 +
    1.34 +                              for all x satisfying to (1)
    1.35 +
    1.36 +         alfa[1] x[1] + ... + alfa[n] x[n] >= beta + 1               (5)
    1.37 +
    1.38 +                              for all x not satisfying to (1)
    1.39 +
    1.40 +         alfa[1], ..., alfa[n], beta are non-negative integers.
    1.41 +
    1.42 +   Note that this model has n+1 variables and 2^n constraints.
    1.43 +
    1.44 +   It is interesting, as noticed in [1] and explained in [2], that
    1.45 +   in most cases LP relaxation of the MIP formulation above has integer
    1.46 +   optimal solution.
    1.47 +
    1.48 +   References
    1.49 +
    1.50 +   1. G.H.Bradley, P.L.Hammer, L.Wolsey, "Coefficient Reduction for
    1.51 +      Inequalities in 0-1 Variables", Math.Prog.7 (1974), 263-282.
    1.52 +
    1.53 +   2. G.J.Koehler, "A Study on Coefficient Reduction of Binary Knapsack
    1.54 +      Inequalities", University of Florida, 2001. */
    1.55 +
    1.56 +param n, integer, > 0;
    1.57 +/* number of variables in the knapsack inequality */
    1.58 +
    1.59 +set N := 1..n;
    1.60 +/* set of knapsack items */
    1.61 +
    1.62 +/* all binary n-vectors are numbered by 0, 1, ..., 2^n-1, where vector
    1.63 +   0 is 00...00, vector 1 is 00...01, etc. */
    1.64 +
    1.65 +set U := 0..2^n-1;
    1.66 +/* set of numbers of all binary n-vectors */
    1.67 +
    1.68 +param x{i in U, j in N}, binary, := (i div 2^(j-1)) mod 2;
    1.69 +/* x[i,j] is j-th component of i-th binary n-vector */
    1.70 +
    1.71 +param a{j in N}, >= 0;
    1.72 +/* original coefficients */
    1.73 +
    1.74 +param b, >= 0;
    1.75 +/* original right-hand side */
    1.76 +
    1.77 +set D := setof{i in U: sum{j in N} a[j] * x[i,j] <= b} i;
    1.78 +/* set of numbers of binary n-vectors, which (vectors) are feasible,
    1.79 +   i.e. satisfy to the original knapsack inequality (1) */
    1.80 +
    1.81 +var alfa{j in N}, integer, >= 0;
    1.82 +/* coefficients to be found */
    1.83 +
    1.84 +var beta, integer, >= 0;
    1.85 +/* right-hand side to be found */
    1.86 +
    1.87 +minimize z: sum{j in N} alfa[j] + beta; /* (3) */
    1.88 +
    1.89 +phi{i in D}: sum{j in N} alfa[j] * x[i,j] <= beta; /* (4) */
    1.90 +
    1.91 +psi{i in U diff D}: sum{j in N} alfa[j] * x[i,j] >= beta + 1; /* (5) */
    1.92 +
    1.93 +solve;
    1.94 +
    1.95 +printf "\nOriginal 0-1 knapsack inequality:\n";
    1.96 +for {j in 1..n} printf (if j = 1 then "" else " + ") & "%g x%d",
    1.97 +   a[j], j;
    1.98 +printf " <= %g\n", b;
    1.99 +printf "\nMinimized equivalent inequality:\n";
   1.100 +for {j in 1..n} printf (if j = 1 then "" else " + ") & "%g x%d",
   1.101 +   alfa[j], j;
   1.102 +printf " <= %g\n\n", beta;
   1.103 +
   1.104 +data;
   1.105 +
   1.106 +/* These data correspond to the very first example from [1]. */
   1.107 +
   1.108 +param n := 8;
   1.109 +
   1.110 +param a := [1]65, [2]64, [3]41, [4]22, [5]13, [6]12, [7]8, [8]2;
   1.111 +
   1.112 +param b := 80;
   1.113 +
   1.114 +end;