Second-Order Cone Relaxations for Binary Quadratic Polynomial Programs

Bissan Ghaddar (bghaddaruwaterloo.ca)
Juan C. Vera (jverauwaterloo.ca)
Miguel F. Anjos (manjosuwaterloo.ca)

Abstract: Several types of relaxations for binary quadratic polynomial programs can be obtained using linear, second-order cone, or semidefinite techniques. In this paper, we propose a general framework to construct conic relaxations for binary quadratic polynomial programs based on polynomial programming. Using our framework, we re-derive previous relaxation schemes and provide new ones. In particular, we present three relaxations for binary quadratic polynomial programs. The first two relaxations, based on second-order cone and semidefinite programming, represent a significant improvement over previous practical relaxations for several classes of non-convex binary quadratic polynomial problems. From a practical point of view, due to the computational cost, semidefinite-based relaxations for binary quadratic polynomial problems can be used only to solve small to mid-size instances. To improve the computational efficiency for solving such problems, we propose a third relaxation based purely on second-order cone programming. Computational tests on different classes of non-convex binary quadratic polynomial problems, including quadratic knapsack problems, show that the second-order cone-based relaxation outperforms the semidefinite-based relaxations that are proposed in the literature in terms of computational efficiency and is comparable in terms of bounds.

Keywords: polynomial optimization, second-order cone programming, semidefinite programming, binary quadratic problem

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Nonlinear Optimization

Category 3: Combinatorial Optimization

Citation: Published in SIAM Journal on Optimization, 21(1): 391-414, 2011

Download:

Entry Submitted: 10/31/2009
Entry Accepted: 10/31/2009
Entry Last Modified: 04/05/2011

Modify/Update this entry