Paper Info
Title
A p-cone sequential relaxation procedure for 0-1 integer programs
Abstract
Several authors have introduced sequential relaxation techniques-based on linear and/or semi-definite programming-to generate the convex hull of 0-1 integer points in a polytope in at most n steps. In this paper, we introduce a sequential relaxation technique, which is based on p-order cone programming (1≤p≤∞). We prove that our technique generates the convex hull of 0-1 solutions asymptotically. In addition, we show that our method generalizes and subsumes several existing methods. For example, when p=∞, our method corresponds to the well-known procedure of Lovasz and Schrijver based on linear programming. Although the p-order cone programs in general sacrifice some strength compared to the analogous linear and semi-definite programs, we show that for p=2 they enjoy a better theoretical iteration complexity. Computational considerations of our technique are discussed.
Year
DOI
Venue
2009
10.1080/10556780903057341
Optimization Methods & Software - GLOBAL OPTIMIZATION
Keywords
Field
DocType
convex hull,semi-definite program,p-order cone program,linear programming,sequential relaxation technique,p-order cone programming,semi-definite programming-to,relaxation,method corresponds,method generalizes,second-order cone programming,existing method,integer programming,integer program,global optimization,cone programming,p-cone sequential relaxation procedure,linear program,second order cone programming
Second-order cone programming,Discrete mathematics,Mathematical optimization,Combinatorics,Cutting-plane method,Convex combination,Convex polytope,Linear programming relaxation,Conic optimization,Mathematics,Semidefinite programming,Convex cone
Journal
Volume
Issue
ISSN
24
4-5
1055-6788
Citations 
PageRank 
References 
3
0.56
15
Authors
2
Name
Order
Citations
PageRank
Samuel Burer1114873.09
Jieqiu Chen2372.20