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

作     者：Hong, Sung-Pil Tuncel, Levent 

作者机构：Seoul Natl Univ Dept Ind Engn Seoul 151744 South Korea Univ Waterloo Fac Math Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2008年第156卷第1期

页      面：25-41页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Korea Science and Engineering Foundation  KOSEF  (R01-2005-000-10271-0) 

主　　题：lift-and-project semidefinite lifting semidefinite programming integer programming 

摘      要：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 Lovasz 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. (c) 2007 Elsevier B.V. All rights reserved.