Fill This Form To Receive Instant Help

#### 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

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. We further assume that aj < b for all j € N.

Problem 3

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

Sj?C xj £ ? C ? - 1,

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

PC := conv(K)Ç{x € Rn : xj = 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 ah = maxj?C aj. Show that the inequality

Sj?Cxj + Sj?N/C aj/ah . xj £ ?C? - 1

is a Chvatal inequality for P:= {x € Rn : Snj=1 ajxj £ b, 0 < x < 1}.

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

Choose an ordering j1,--- , ji of the indices in N\C. Let C0 = C and Ch = Ch-1 È jh}

For h = 1 up to h = i, compute

ajh := b — max{ Sj?Ch-1ajxj : x € S, xj = 0, j ? N\Ch, xjh = 1}.

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