Given a 0-1 integer programming problem, several authors have introduced sequential relaxation techniques --- based on linear and/or semidefinite programming --- that generate the convex hull of integer points in at most $n$ steps. In this paper, we introduce a sequential relaxation technique, which is based on $p$-order cone programming ($1 \le p \le \infty$). 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 = \infty$, our method corresponds to the well-known procedure of Lov\'asz and Schrijver based on linear programming (so that finite convergence is obtained by our method in special cases). Although the $p$-order cone programs in general sacrifice some strength compared to the analogous linear and semidefinite programs, we show that for $p = 2$ they enjoy a better theoretical iteration complexity. Computational considerations of our technique are also discussed.
Citation
Manuscript, Department of Management Sciences, University of Iowa, Iowa City, IA 52240, USA, February, 2008
Article
View A p-Cone Sequential Relaxation Procedure for 0-1 Integer Programs