# source:glpk-cmake/examples/min01ks.mod@1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

• Generated files and doc/notes are removed
File size: 3.1 KB
Line
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 x + ... + 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 x + ... + 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| + ... + |alfa[n]| + |beta| =                  (3)
24
25           = alfa + ... + alfa[n] + beta
26
27      subject to
28
29         alfa x + ... + alfa[n] x[n] <= beta                   (4)
30
31                              for all x satisfying to (1)
32
33         alfa x + ... + alfa[n] x[n] >= beta + 1               (5)
34
35                              for all x not satisfying to (1)
36
37         alfa, ..., 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  and explained in , 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
53param n, integer, > 0;
54/* number of variables in the knapsack inequality */
55
56set 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
62set U := 0..2^n-1;
63/* set of numbers of all binary n-vectors */
64
65param 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
68param a{j in N}, >= 0;
69/* original coefficients */
70
71param b, >= 0;
72/* original right-hand side */
73
74set 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
78var alfa{j in N}, integer, >= 0;
79/* coefficients to be found */
80
81var beta, integer, >= 0;
82/* right-hand side to be found */
83
84minimize z: sum{j in N} alfa[j] + beta; /* (3) */
85
86phi{i in D}: sum{j in N} alfa[j] * x[i,j] <= beta; /* (4) */
87
88psi{i in U diff D}: sum{j in N} alfa[j] * x[i,j] >= beta + 1; /* (5) */
89
90solve;
91
92printf "\nOriginal 0-1 knapsack inequality:\n";
93for {j in 1..n} printf (if j = 1 then "" else " + ") & "%g x%d",
94   a[j], j;
95printf " <= %g\n", b;
96printf "\nMinimized equivalent inequality:\n";
97for {j in 1..n} printf (if j = 1 then "" else " + ") & "%g x%d",
98   alfa[j], j;
99printf " <= %g\n\n", beta;
100
101data;
102
103/* These data correspond to the very first example from . */
104
105param n := 8;
106
107param a := 65, 64, 41, 22, 13, 12, 8, 2;
108
109param b := 80;
110
111end;
Note: See TracBrowser for help on using the repository browser.