Second-order cone relaxations for binary quadratic polynomial programs

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

Research output: Contribution to journalArticleScientificpeer-review

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

Second-order Cone
Quadratic Polynomial
Cones
Polynomials
Binary
Second-order Cone Programming
Computational efficiency
Computational Efficiency
Relaxation Scheme
Semidefinite Programming
Knapsack Problem
Computational Cost
Programming
Polynomial

Cite this

@article{40db89bb36454922b06454d1b6b0dedd,
title = "Second-order cone relaxations for binary quadratic polynomial programs",
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.",
author = "B. Ghaddar and J.C. Vera and M.F. Anjos",
year = "2011",
doi = "10.1137/100802190",
language = "English",
volume = "21",
pages = "391--414",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "1",

}

Second-order cone relaxations for binary quadratic polynomial programs. / Ghaddar, B.; Vera, J.C.; Anjos, M.F.

In: SIAM Journal on Optimization, Vol. 21, No. 1, 2011, p. 391-414.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Second-order cone relaxations for binary quadratic polynomial programs

AU - Ghaddar, B.

AU - Vera, J.C.

AU - Anjos, M.F.

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

U2 - 10.1137/100802190

DO - 10.1137/100802190

M3 - Article

VL - 21

SP - 391

EP - 414

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 1

ER -