Optimization Online


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

Sung-Pil Hong (sphong***at***cau.ac.kr)
Levent Tuncel (ltuncel***at***math.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

  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 Programming Society