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 : Snj=1  S\ajxj; < b} Where 6 > 0 and aj > 0

Math

Share With

---

Valid Inequalities for Structured Integer Programs

Consider the 0, 1 knapsack set

                         K := {x € {0,1}ⁿ : Sⁿ_j=1  S\a_jx_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ⁿ : 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?Cx_j + S_j?N/C a_j/a_h . x_j £ ?C? - 1

is a Chvatal inequality for P:= {x € Rⁿ : Sⁿ_j=1 a_jx_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?Ca_jx_j £ b of conv(S) Ç {x : x_j = 0,j € N\C}. Consider the following lifting procedure

Choose an ordering j₁,--- , ji of the indices in N\C. Let C₀ = C and C_h = C_h-1 È j_h}

For h = 1 up to h = i, compute

a_jh := b — max{ S_j?Ch-1a_jx_j : x € S, x_j = 0, j ? N\C_h, x_jh = 1}.

Show that the inequality Sⁿ_j=1a_jx_j £ b obtained this way is facet-defining for conv(S).