Fill This Form To Receive Instant Help

#### Let P: = {x € Rn : Ax £ b} be a polyhedron, let J Ì {1,… ,n}, and let S: ={x ? P: xj € Z, j € I} be a mixed integer set, where I indexes the integer variables

###### Math

Let P: = {x € Rn : Ax £ b} be a polyhedron, let J Ì {1,… ,n}, and let S: ={x ? P: xj € Z, j € I} be a mixed integer set, where I indexes the integer variables. C: = {1,…, n}\ I to be the index set of the continuous variables.

The Theory of Valid inequalities

Problem 1

Given a vector π € Zn such that πj = 0 for all j € C, πx is integer for all x € S. Thus, for any π0 € Z, it follows that every x € S satisfies exactly one of πx £ π0 or πx ³ π0 + 1

P1: = PÇ{x : πx £ π0}

P2: = PÇ{x : πx ³ π0 + 1}

Clearly, conv(S) Ì conv(P1È P2). For u € Rm, let u+ be defined by u+i := max{0,ui} and let u- := (—u)+. AI and AC are the matrices comprising the columns of A with indices I and C respectively. Suppose uAI is integral, uAc = 0, and ub Ï Z.

(a) Show the following inequality is valid for S

U+(b— Ax)/¦ + u-(b— Ax)/1-¦  ³1

Where f := ub — |ub|.

(b) Suppose now P := {x € Rn : Ax =b,x > 0}. Let a := uA, b := ub, f := ub— [ub], and ¦j = aj —|aj], j € I. Use Part (a) to prove the following valid inequality for S

Sj?I,¦j£¦¦j/¦.xj + S j?I,¦j>¦1-¦j/1-¦.xj + Sj?C,aj³0aj/¦.xj - Sj?C,aj<0aj/1-¦.x j³1.

This is Gomory’s mixed integer inequality.

(c) For the two-dimensional mixed integer set {(e, v) € Z x R+ e - v  £ b} recall the rounding inequality

e - 1/1-¦.v £ [b],

Where f := b — |b|. Suppose that we are given a valid inequality for P written in the form

πx – (c - cx) £ b

Such that πI is integral, πc = 0, and cx £ c is a valid inequality for P. Then πx is an integer and c — cx ³ 0 for all x € S. Using the simple mixed integer rounding with variable substitution gives the inequality

πx – 1/1-¦. (c - cx) £ b

Show that any inequality of the form in part (a) can be derived using the mixed integer rounding procedure above.

(d) Let T= {x € Zn, y ? Rp+ : S ajxj + S Jjyj £ b}, where aj ? Z for all j, gcd(a1,--- ,an) = 1, and b Ï Z. Show that the following mixed integer rounding inequality defines a facet of conv(T).

S ajxj + 1/1-¦ Sj?J- Jjyj £ b,

Where J- = {j : gj < O} and f = b- |b}.

Problem 2

For mixed integer set S := {x € P : xj € Z,j € I} where P:= {x € Rn : Ax < b}. The Chvatal inequality is u > 0

(uA)x £ ub.

The Chvatal closure Pch of P is the set of points in P satisfying all the Chvatal inequalities.

PCh := {x € P: (uA)x < |ub| for all u > 0 s.t. uAI € ZI,uAc = 0}.

(a) Suppose S := PÇZn is a pure integer set. Show that PCh is the set of all points in P satisfying the Chvatal inequalities (uA) < [ub] for all u such that uA € Zn and 0 < u < 1.

(b) Show that for pure integer linear sets PCh is a polyhedron.

(c) Let P := {(x,y) ? R2 : 2x > y, 2x + y < 2,y > 0} and S := PÇ(Z x R). Show that conv(S) ¹ P and that the Chvatal closure of P is P itself.

Valid Inequalities for Structured Integer Programs

Consider the 0, 1 knapsack set

K := {x € {0,1}" : Snj=1 ajxj £ b}

Where b > 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?Caj > b 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?Cxj £ ?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=1ajxj £ 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)