  


A Comprehensive Analysis of Polyhedral LiftandProject Methods
Yu Hin Au (aumsoe.edu) Abstract: We consider liftandproject methods for combinatorial optimization problems and focus mostly on those liftandproject methods which generate polyhedral relaxations of the convex hull of integer solutions. We introduce many new variants of SheraliAdams and BienstockZuckerberg operators. These new operators fill the spectrum of polyhedral liftandproject 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 worstcase 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 BienstockZuckerberg 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 worstcase instances for the positive semidefinite Lov\'{a}szSchrijver liftandproject operator are also bad instances for the strongest variants of the SheraliAdams operator with positive semidefinite strengthenings, and discuss some consequences for integrality gaps of convex relaxations. Keywords: combinatorial optimization, liftandproject 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  