A p-Cone Sequential Relaxation Procedure for 0-1 Integer Programs

Samuel Burer (samuel-bureruiowa.edu)
Jieqiu Chen (jieqiu-chenuiowa.edu)

Abstract: 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.

Keywords: Global optimization, integer programming, second-order cone programming, cone programming, relaxation

Category 1: Global Optimization (Theory )

Category 2: Integer Programming (0-1 Programming )

Category 3: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Citation: Manuscript, Department of Management Sciences, University of Iowa, Iowa City, IA 52240, USA, February, 2008

Download: [PDF]

Entry Submitted: 02/11/2008
Entry Accepted: 02/11/2008
Entry Last Modified: 06/04/2008

Modify/Update this entry