Optimization Online


A Comprehensive Analysis of Polyhedral Lift-and-Project Methods

Yu Hin Au (au***at***msoe.edu)
Levent Tunšel (ltuncel***at***uwaterloo.ca)

Abstract: We consider lift-and-project methods for combinatorial optimization problems and focus mostly on those lift-and-project methods which generate polyhedral relaxations of the convex hull of integer solutions. We introduce many new variants of Sherali--Adams and Bienstock--Zuckerberg operators. These new operators fill the spectrum of polyhedral lift-and-project operators in a way which makes all of them more transparent, easier to relate to each other, and easier to analyze. We provide new techniques to analyze the worst-case performances as well as relative strengths of these operators in a unified way. In particular, using the new techniques and a result of Mathieu and Sinclair from 2009, we prove that the polyhedral Bienstock--Zuckerberg operator requires at least $\sqrt{2n}- \frac{3}{2}$ iterations to compute the matching polytope of the $(2n+1)$-clique. We further prove that the operator requires approximately $\frac{n}{2}$ iterations to reach the stable set polytope of the $n$-clique, if we start with the fractional stable set polytope. Lastly, we show that some of the worst-case instances for the positive semidefinite Lov\'{a}sz--Schrijver lift-and-project operator are also bad instances for the strongest variants of the Sherali--Adams operator with positive semidefinite strengthenings, and discuss some consequences for integrality gaps of convex relaxations.

Keywords: combinatorial optimization, lift-and-project methods, design and analysis of algorithms with discrete structures, integer programming, semidefinite programming, convex relaxations

Category 1: Integer Programming

Category 2: Combinatorial Optimization

Category 3: Linear, Cone and Semidefinite Programming

Citation: Preprint, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, June 2015

Download: [PDF]

Entry Submitted: 12/20/2013
Entry Accepted: 12/20/2013
Entry Last Modified: 01/08/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society