About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Mathematical Programming Computation
Paper
Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods
Abstract
We present effective linear programming based computational techniques for solving nonconvex quadratic programs with box constraints (BoxQP). We first observe that known cutting planes obtained from the Boolean Quadric Polytope (BQP) are computationally effective at reducing the optimality gap of BoxQP. We next show that the Chvátal–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 a common integrality-based preprocessing technique and a particular convex quadratic relaxation, we develop a solver that can effectively solve a well-known family of test instances. Our linear programming based solver is competitive with SDP-based state of the art solvers on small instances and sparse instances. Most of our computational techniques have been implemented in the recent version of CPLEX and have led to significant performance improvements on nonconvex quadratic programs with linear constraints.