Optimization Online


Second-Order Cone Relaxations for Binary Quadratic Polynomial Programs

Bissan Ghaddar (bghaddar***at***uwaterloo.ca)
Juan C. Vera (jvera***at***uwaterloo.ca)
Miguel F. Anjos (manjos***at***uwaterloo.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


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society