New Relaxations for Binary Quadratic Problems Using Second-Order Cone Programming

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

Abstract: We present a general framework for conic relaxations based on polynomial programming. Using this framework, we can re-derive previous relaxation schemes and provide new ones for general binary quadratic optimization. In particular, we propose a second-order cone programming relaxation that can be strengthened by adding triangle inequalities. Computational tests on the max-cut problem, the unconstrained version of binary quadratic optimization, show that the strengthened second-order cone-based relaxation outperforms the semidefinite-based relaxation in terms of computational efficiency and is comparable in terms of bounds. In order to gain insight into the performance of our approach on constrained quadratic binary problems, we also compare the second-order cone relaxation for the quadratic knapsack problem to the strongest semidefinite relaxation in the literature. The computational results confirm that using the second-order cone relaxation with triangle inequalities provides a bound that is competitive with the semidefinite bound strengthened with triangle inequalities but the former relaxation is computationally more efficient.

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:

Download: [PDF]

Entry Submitted: 10/31/2009
Entry Accepted: 10/31/2009
Entry Last Modified: 10/31/2009

Modify/Update this entry