Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra

Sung-Pil Hong (sphongcau.ac.kr)
Levent Tuncel (ltuncelmath.uwaterloo.ca)

Abstract: We present a unifying framework to establish a lower-bound on the number of semidefinite programming based, lift-and-project iterations (rank) for computing the convex hull of the feasible solutions of various combinatorial optimization problems. This framework is based on the maps which are commutative with the lift-and-project operators. Some special commutative maps were originally observed by Lov\'{a}sz and Schrijver, and have been used usually implicitly in the previous lower-bound analyses. In this paper, we formalize the lift-and-project commutative maps and propose a general framework for lower-bound analysis, in which we can recapture many of the previous lower-bound results on the lift-and-project ranks.

Keywords: lift-and-project, semidefinite lifting, semidefinite programming, integer programming

Category 1: Integer Programming (0-1 Programming )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: CORR2004-05, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, ON, Canada, February/2004.

Download: [Compressed Postscript]

Entry Submitted: 03/04/2004
Entry Accepted: 03/04/2004
Entry Last Modified: 03/04/2004

Modify/Update this entry