Journal article
A p-cone sequential relaxation procedure for 0-1 integer programs
Optimization methods & software, Vol.24(4-5), pp.523-548
10/01/2009
DOI: 10.1080/10556780903057341
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 Lovász 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.
Details
- Title: Subtitle
- A p-cone sequential relaxation procedure for 0-1 integer programs
- Creators
- Samuel Burer - University of IowaJieqiu Chen - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Optimization methods & software, Vol.24(4-5), pp.523-548
- Publisher
- Taylor & Francis
- DOI
- 10.1080/10556780903057341
- ISSN
- 1055-6788
- eISSN
- 1029-4937
- Language
- English
- Date published
- 10/01/2009
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380518402771
Metrics
1 Record Views