### Abstract

Original language | English |
---|---|

Pages (from-to) | 391-414 |

Journal | SIAM Journal on Optimization |

Volume | 21 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2011 |

### Fingerprint

### Cite this

*SIAM Journal on Optimization*,

*21*(1), 391-414. https://doi.org/10.1137/100802190

}

*SIAM Journal on Optimization*, vol. 21, no. 1, pp. 391-414. https://doi.org/10.1137/100802190

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

Research output: Contribution to journal › Article › Scientific › peer-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 -