Second-order cone relaxations for binary quadratic polynomial programs

B. Ghaddar, J.C. Vera, M.F. Anjos

Research output: Contribution to journalArticleScientificpeer-review

10 Citations (Scopus)

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 nonconvex 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 midsize 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 nonconvex 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 it is comparable in terms of bounds.
Original languageEnglish
Pages (from-to)391-414
JournalSIAM Journal on Optimization
Volume21
Issue number1
DOIs
Publication statusPublished - 2011

Fingerprint Dive into the research topics of 'Second-order cone relaxations for binary quadratic polynomial programs'. Together they form a unique fingerprint.

Cite this