**
Fill This Form To Receive Instant Help**

Homework answers / question archive / Valid Inequalities for Structured Integer Programs Consider the 0, 1 knapsack set K := {x € {0,1}n : Snj=1 S\ajxj; < b} Where 6 > 0 and aj > 0

Valid Inequalities for Structured Integer Programs

Consider the 0, 1 knapsack set

K := {x € {0,1}^{n} : S^{n}_{j=1} S\a_{j}x_{j}; __<__ b}

Where 6 > 0 and a_{j} > 0. We further assume that a_{j} __<__ b for all j € N.

Problem 3

Recall that a cover is a subset C Ì N such that S_{j}_{?C} a_{j} > 6 and it is minimal if S_{j}_{?C/[k] }a_{j} £ b for all k € C. For any cover C, the cover inequality associated with C is

S_{j}_{?C} x_{j} £ ? C ? - 1,

(a) Let C be a cover for K. Show that the cover inequality associated with C is facet-defining for

P_{C} := conv(K)Ç{x € R^{n} : x_{j} = 0, j € N\C} if and only if C is a minimal cover.

(b) Let C be a minimal cover, let h € C such that a_{h} = max_{j}_{?C} a_{j}. Show that the inequality

S_{j}_{?C}x_{j} + S_{j}_{?N/C} a_{j}/a_{h} . x_{j} £ ?C? - 1

is a Chvatal inequality for P:= {x € R^{n} : S^{n}_{j=1} a_{j}x_{j }£ b, 0 __<__ x __<__ 1}.

(c) Consider a binary set S := {x € {0,1}" : A_{x} __<__ b} of dimension n, where A is a nonnegative matrix. Suppose we start with a facet-defining inequality S_{j}_{?C}a_{j}x_{j} £ b of conv(S) Ç {x : x_{j} = 0,j € N\C}. Consider the following lifting procedure

Choose an ordering j_{1},--- , ji of the indices in N\C. Let C_{0} = C and C_{h} = C_{h-1} È j_{h}}

For h = 1 up to h = i, compute

a_{jh} := b — max{ S_{j}_{?Ch-1}a_{j}x_{j} : x € S, x_{j} = 0, j ? N\C_{h}, x_{jh} = 1}.

Show that the inequality S^{n}_{j=1}a_{j}x_{j} £ b obtained this way is facet-defining for conv(S).