6.859/15.083 Integer Programming and Combinatorial Optimization Fall 2009 Cutting Plane Methods I Cutting Planes • Consider max{wx : Ax ≤ b, x integer}. • Establishing the optimality of a solution is equivalent to proving wx ≤ t is valid for all integral solutions of Ax ≤ b, where t is the maximum value. • Without the integrality restriction, we could prove the validity of wx ≤ t with the help of LP duality. • Our goal is to establish a similar method for integral solutions. • Consider the linear system 2x1 + 3x2 ≤ 27 2x1 − 2x2 ≤ 7 −6x1 − 2x2 ≤ −9 −2x1 − 6x2 ≤ −11 −6x1 + 8x2 ≤ 21 • As can easily be seen, every integral solution satisfies x2 ≤ 5. • However, we cannot derive this directly with LP duality because there is a fractional vector, (9/2, 6), with x2 = 6. • Instead, let us multiply the last inequality by 1/2: −3x1 + 4x2 ≤ 21/2. • Every integral solution satisfies the stronger inequality −3x1 + 4x2 ≤ 10, obtained by rounding 21/2 down to the nearest integer. • Multiplying this inequality by 2 and the first inequality by 3, and adding the resulting in-equalities, gives: 17x2 ≤ 101. • Multiplying by 1/17 and rounding down the right-hand side, we can conclude: x2 ≤ 5. 1� � • In general, suppose our system consists of aix ≤ bi i = 1, . . . , m. • Let y1, . . . , ym ≥ 0 and set mc = yiai i=1 and md = yibi. i=1 • Trivially, every solution to Ax ≤ b satisfies cx ≤ d. • If c is integral, all integral solutions to Ax ≤ b also satisfy cx ≤ �d�. • cx ≤ �d� is called a Gomory-Chv´atal cut (GC cut). • “Cut” because the rounding operation cuts off part of the original polyhedron. • GC cuts can also be defined directly in terms of the polyhedron P defined by Ax ≤ b: just take a valid inequality cx ≤ d for P with c integral and round down to cx ≤ �d�. • The use of the nonnegative numbers yi is to provide a derivation of cx ≤ �d�. With the yi’s in hand, we are easily convinced that cx ≤ d and cx ≤ �d� are indeed valid. Cutting-Plane Proofs • A cutting-plane proof of an inequality wx ≤ t from Ax ≤ b is a sequence of inequalities am+kx ≤ bm+k k = 1, . . . , M together with nonnegative numbers yki k = 1, . . . , M, i = 1, . . . , m + k − 1 such that for each k = 1, . . . , M, the inequality am+kx ≤ bm+k is derived from aix ≤ bi i = 1, . . . , m + k − 1 using the numbers yki, i = 1, . . . , m + k − 1, and such that the last inequality in the sequence is wx ≤ t. Theorem 1 (Chv´atal 1973, Gomory 1960). Let P = {x : Ax ≤ b} be a rational polytope and let wx ≤ t be an inequality, with w integral, satisfied by all integral vectors in P . Then there exists a cutting-plane proof of wx ≤ t� from Ax ≤ b, for some t� ≤ t. Proof idea: • 2– Push wx ≤ l into the polytope as far as possible. – Use induction to show that the face F induced by wx ≤ l contains no integral points. – Push the inequality to wx ≤ l − 1. – Continuing this, we eventually reach wx ≤ t. • Need technique to translate the cutting-plane proof on F to a proof on the entire polytope: Lemma 2. Let F be a face of a rational polytope P . If cx ≤ �d� is a GC cut for F , then there exists a GC cut c�x ≤ �d�� for P such that F ∩ {x : c�x ≤ �d��} = F ∩ {x : cx ≤ �d�}. Proof: • Let P = {x : A�x ≤ b�, A��x ≤ b��}, where A�� and b�� are integral. • Let F = {x : A�x ≤ b�, A��x = b��}. • We may assume that d = max{cx : x ∈ F }. • By LP duality, there exist vectors y� ≥ 0 and y�� such that y�A� + y��A�� = c y�b� + y��b�� = d. • To obtain a GC cut for P we must replace y�� by a vector that is nonnegative. • To this end, define c� = c − �y���A�� = y�A� + (y�� − �y���)A�� d� = d − �y���b�� = y�b� + (y�� − �y���)b�� • Then c� is integral, and c�x ≤ d� is a valid inequality for P . • Moreover, since �d� = �d�� + �y���b��, =F ∩ {x : c�x ≤ �d��} =F ∩ {x : c�x ≤ �d��, �y���A��x = �y���b��}F ∩ {x : cx ≤ �d�}. 3• �Theorem 3. Let P = {x : Ax ≤ b} be a rational polytope that contains no integral vectors. Then there exists a cutting-plane proof of 0x ≤ −1 from Ax ≤ b. Proof: Induction on the dimension of P .• • Theorem trivial if dim(P ) = 0. So assume dim(P ) ≥ 1. • Let wx ≤ l be an inequality, with w integral, that induces a proper face of P . • Let P ¯= {x ∈ P : wx ≤ �l�}. If P ¯= ∅, then we can use Farkas’ Lemma to deduce 0x ≤ −1 from Ax ≤ b, wx ≤ �l�. • Suppose P ¯= ∅, and let F = {x ∈ P ¯: wx = �l�}. • Note that dim(F ) < dim(P ). • By the induction hypothesis, there exists a cutting-plane proof of 0x ≤ −1 from Ax ≤ b, wx = �l�. • Using the lemma, we get a cutting-plane proof, from Ax ≤ b, wx ≤ �l � of an inequality cx ≤ �d� such that ¯ P ∩ {x : cx ≤ �d�, wx = �l�} = ∅. Thus, after applying this sequence of cuts to P ¯, we have wx ≤ �l� − 1 as a GC cut. • • As P is bounded, min{wx : x ∈ P } is finite. • Continuing in the above manner, letting P ¯= {x ∈ P : wx ≤ �l�−1}, and so on, we eventually obtain a cutting-plane proof of some wx ≤ t such that P ∩ {x : wx ≤ t} = ∅. • With Farkas’ Lemma we then derive 0x ≤ −1 from Ax ≤ b, wx ≤ t. Theorem 4 (Chv´atal 1973, Gomory 1960). Let P = {x : Ax ≤ b} be a rational polytope and let wx ≤ t be an inequality, with w integral, satisfied by all integral vectors in P . Then there exists a cutting-plane proof of wx ≤ t� from Ax ≤ b, for some t� ≤ t. Proof: • Let l = max{w x …