lemon-project-template-glpk

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