15.083 Lecture 17: Cutting Plane Methods I

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 ai x ≤ bi i = 1, . . . , m. • Let y1 , . . . , ym ≥ 0 and set c= m � yi ai i=1 and d= m � yi bi . 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átal 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+k x ≤ 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+k x ≤ bm+k is derived from ai x ≤ 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átal 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átal 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{wx : x ∈ P }, and let P¯ = {x ∈ P : wx ≤ �l�}. • If �l� ≤ t, we are done, so suppose not. • Consider the face F = {x ∈ P¯ : wx = �l�}. • Since t < �l�, F contains no integral points. • By the previous theorem, there exists a cuting-plane proof of 0x ≤ −1 from Ax ≤ b, wx = �l�. 4 • 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. • Continuing in this fashion, we finally derive an inequality wx ≤ t� with t� ≤ t. Chvátal Rank • GC cuts have an interesting connection with the problem of finding linear descriptions of combinatorial convex hulls. • In this context, we do not think of cuts coming sequentially, as in cutting-plane proofs, but rather in waves that provide successively tighter approximations to PI , the convex hull of integral points in P . • Let P � be the set of all points in P that satisfy every GC cut for P . Theorem 5 (Schrijver 1980). If P is a rational polyhedron, then P � is also a rational polyhedron. Proof: • Let P = {x : Ax ≤ b} with A and b integral. • Claim: P � is defined by Ax ≤ b and all inequalities that can be written as (yA)x ≤ �yb� for some vector y such that 0 ≤ y < 1 and yA is integral. • Note that this would give the result. • So let wx ≤ �t� be a GC cut, derived from Ax ≤ b with the nonnegative vector y. • Let y � = y − �y�. • Then w� = y � A = w − �y�A is integral. • Moreover, t� = y � b = t − �y�b differs from t by an integral amount. • So the cut w� x ≤ �t� � derived with y � , together with the valid inequality (�y�A)x ≤ �y�b sum to wx ≤ t. Letting P (0) = P and P (i) = (P (i−1) )� , we have P = P (0) ⊇ P (1) ⊇ P (2) ⊇ · · · ⊇ PI . Theorem 6. If P is a rational polyhedron, then P (k) = PI for some integer k. 5 The least k for which P (k) = PI is called the Chvátal rank of P . • In general, there is no upper bound on the Chvátal rank in terms of the dimension of the polyhedron. • For polytopes P ⊆ [0, 1]n , the Chvátal rank is O(n2 log n). • If for a family of polyhedra P the problem max{wx : x ∈ PI } is NP-complete, then, assuming � co-NP, there is no fixed k such that P (k) = PI for all P . NP = Gomory’s Cutting-Plane Procedure • Consider max{cx : Ax = b, x ∈ Zn+ }. • Given an (optimal) LP basis B, write the IP as � max cB B −1 b + c̄j xj j∈N s.t. xBi + � āij xj = ¯bi i = 1, . . . , m xj ∈ Z j = 1, . . . , n j∈N • c̄j ≤ 0 for all j ∈ N ; ¯bi ≥ 0 for all i = 1, . . . , m. • If the LP solution is not integral, then there exists row i with ¯bi �∈ Z. • The GC cut for row i is xBi + � �āij �xj ≤ �¯bi �. j∈N • Substitute for xBi to get � (āij − �āij �)xj ≥ ¯bi − �¯bi �. j∈N • Or if fij = āij − �āij �, fi = ¯bi − �¯bi �, then � fij xij ≥ fi . j∈N 6