� � � � � � � � • �15.083J Integer Programming and Combinatorial Optimization Fall 2009 Mixed-Integer Programming I Mixed-Integer Linear Programming max cx + hy s.t. Ax + Gy ≤ b x integral where c, h, A, G, and b are rational vectors and matrices, respectively. Projections • Let P ⊆ Rn+p, where (x, y) ∈ P is interpreted as x ∈ Rn and y ∈ Rp. • The projection of P onto the x-space Rn is proj (P ) = {x ∈ Rn : ∃ y ∈ Rp with (x, y) ∈ P }. xTheorem 1. Let P = (x, y) : Ax + Gy ≤ b . Then proj (P ) = {x : v t(b − Ax) ≥ 0 for all t ∈ T },xwhere {vt}t∈T is the set of extreme rays of {v : vG = 0, v ≥ 0}. The Fundamental Theorem of MILP Theorem 2 (Meyer 1974). Given rational matrices A and G and a rational vector b, let P = (x, y) : Ax + Gy ≤ b and S = (x, y) ∈ P : x integral . There exist rational matrices A�, G�, and a rational vector b� such that conv(S) = (x, y) : A�x + G�y ≤ b� . Proof: We may assume that S = ∅. • By the Minkowski-Weyl Theorem, P = conv(V ) + cone(R), where V = (v1, . . . , vp) and R = (r1, . . . , rq). • We may assume that V is a rational matrix and R is an integral matrix. 1� � � � � � � � � � � �� � � � �• Consider the following truncation of P : p q pT = (x, y) : (x, y) = λiv i + µj rj , λi = 1, i=1 j=1 i=1 .λ ≥ 0, 0 ≤ µ ≤ 1 • T is bounded and is the projection of a rational polyhedron. It therefore is a rational polytope. • Let TI = (x, y) ∈ T : x integral . Claim: conv(TI ) is a rational polytope. • Since T is a polytope, X = x : ∃ y s.th. (x, y) ∈ TI is finite. • For fixed ¯x ∈ X, Tx¯= (¯x, y) : (¯x, y) ∈ TI is a rational polytope. Hence, Tx¯= conv(Vx¯) for some rational matrix Vx¯. • Since X is finite, there is a rational matrix VTI which contains all the columns of all matrices Vx¯, for ¯x ∈ X. • Therefore, conv(TI ) = conv(VTI ), which proves the claim. • (¯x, y¯) ∈ S iff ¯x is integral and there exist λ ≥ 0, p λi = 1, and µ ≥ 0 such that i=1 p q q(¯x, y¯) = λiv i + (µj − �µj �)rj + �µj �rj . i=1 j=1 j=1 • The point ip =1 λivi + jq =1(µj − �µj �)rj belongs to T . • Since ¯x and �µj �rj are integral it also belongs to TI . Thus • S = TI + RI , (1) where RI is the set of integral conic combinations of r1, . . . , rq. • (1) implies that conv(S) = conv(TI ) + cone(R). • By the above claim conv(TI ) is a rational polytope. • Thus conv(S) is a rational polyhedron (having the same recession cone as P ). Union of Polyhedra • Consider k polyhedra Pi = {x ∈ Rn : Aix ≤ bi}, i = 1, . . . , k. One can show that conv(∪ik =1Pi) is a polyhedron. • 2� � � � � � � � • � � � � • Furthermore, we will show that this polyhedron can be obtained as the projection onto Rn of a polyhedron with polynomially many variables and constraints in a higher-dimensional space. • (The closure is needed: let P1 be a single point and let P2 be a line that does not contain P2.) Theorem 3. For i = 1, . . . , k, let Pi = Qi + Ci be nonempty polyhedra. Then Q = conv(∪k Qi)i=1is a polytope, C = conv(∪ik =1Ci) is a finitely generated cone, and conv(∪ik =1Pi) = Q + C. • No proof here, but note that the claims on Q and C are straightforward to check. • One consequence of the proof is that if P1, . . . , Pk have identical recession cones, then conv(∪ki=1Pi) is a polyhedron. Theorem 4 (Balas 1974). Consider k polyhedra Pi = Qi + Ci = {x ∈ Rn : Aix ≤ bi} and let Y ⊆ Rn+kn+k be the polyhedron defined by k kAix i ≤ bi yi, x i = x, yi = 1, yi ≥ 0 for i = 1, . . . , k. i=1 i=1 Then projx(Y ) = Q + C, where Q = conv(∪ik =1Qi) and C = conv(∪ki=1Ci). Proof: • First, let x ∈ Q + C. • There exist wi ∈ Qi and zi ∈ Ci such that x = i yiwi + i zi, where yi ≥ 0 and i yi = 1. • Let xi = yiwi + zi . Then Aixi ≤ biyi and x = i xi . • This shows x ∈ proj (Y ).x• Now, let x ∈ proj (Y ).x• There exist x1, . . . , xk, y such that x = i xi where Aixi ≤ biyi, i yi = 1, y ≥ 0. • Let I = {i : yi > 0}. • For i ∈ I, let zi = xi . Then zi ∈ Pi. yi • Since Pi = Qi + Ci, we can write zi = wi + ri where wi ∈ Qi and ri ∈ Ci. yi • For i �∈ I, we have Aixi ≤ 0, that is xi ∈ Ci. Let ri = xi for i �∈ I. Then, x = yiz i + x i = yiw i + r i ∈ Q + C. i∈Ii�∈Ii∈Ii 3� � � � Lift-and-Project Revisited We consider mixed-0/1 linear programs: min cx s.t. Ax ≥ b xj ∈ {0, 1} for j = 1, . . . , n xj ≥ 0 for j = n + 1, . . . , n + p We let P = {x ∈ Rn+p : Ax ≥ b} and S = {x ∈ {0, 1}n × Rp : Ax ≥ b}.+ + We assume that Ax ≥ b includes −xj ≥ −1 for j = 1, . . . , n, but not x ≥ 0. Given an index j ∈ {1, . . . , n}, let Pj = conv (Ax ≥ b, x ≥ 0, xj = 0) ∪ (Ax ≥ b, x ≥ 0, xj = 1) . • By definition, this is the tightest possible relaxation among all relaxations that ignore the integrality of all variables xi, i =� j. • n Pj is called the lift-and-project closure:• j=1 nconv(S) ⊆ Pj ⊆ P. j=1 • On 35 mixed-0/1 linear programs from MIPLIB, the lift-and-project closure reduces the integrality gap by 37% on average [Bonami …