Optimization Online


Solving Box-Constrained Nonconvex Quadratic Programs

Pierre Bonami (pierre.bonami***at***es.ibm.com)
Oktay Gunluk (gunluk***at***us.ibm.com)
Jeff Linderoth (linderoth***at***wisc.edu)

Abstract: We present effective computational techniques for solving nonconvex quadratic programs with box constraints (BoxQP). We first observe that cutting planes obtained from the Boolean Quadric Polytope (BQP) are computationally effective at reducing the optimality gap of BoxQP. We next show that the Chvatal-Gomory closure of the BQP is given by the odd-cycle inequalities even when the underlying graph is not complete. By using these cutting planes in a spatial branch-and-cut framework, together with an integrality-based branching technique and a strengthened convex quadratic relaxation, we develop a solver that can effectively solve a well-known family of test instances. Most of our computational techniques have been implemented in the recent version of CPLEX and lead to significant performance improvements on nonconvex quadratic programs with linear constraints.

Keywords: Nonconvex Quadratic Programming Global Optimization Boolean Quadric Polytope

Category 1: Nonlinear Optimization (Quadratic Programming )


Download: [PDF]

Entry Submitted: 06/13/2016
Entry Accepted: 06/13/2016
Entry Last Modified: 06/13/2016

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 Optimization Society