Global solution of non-convex quadratically constrained quadratic programs
Authors:
- 28 July 2017
- journal article
- research article
- Published by Taylor & Francis in Optimization Methods and Software
- Vol. 34 (1) , 98-114
Abstract
The class of mixed-integer quadratically constrained quadratic programs (QCQP) consists of minimizing a quadratic function under quadratic constraints where the variables could be integer or continuous. On a previous paper we introduced a method called MIQCR for solving QCQPs with the following restriction: all quadratic sub-functions of purely continuous variables are already convex. In this paper, we propose an extension of MIQCR which applies to any QCQP. Let be a QCQP. Our approach to solve is first to build an equivalent mixed-integer quadratic problem . This equivalent problem has a quadratic convex objective function, linear constraints, and additional variables y that are meant to satisfy the additional quadratic constraints , where x are the initial variables of problem . We then propose to solve by a branch-and-bound algorithm based on the relaxation of the additional quadratic constraints and of the integrality constraints. This type of branching is known as spatial branch-and-bound. Computational experiences are carried out on a total of 325 instances. The results show that the solution time of most of the considered instances is improved by our method in comparison with the recent implementation of QuadProgBB, and with the solvers Cplex, Couenne, Scip, BARON and GloMIQO.
Keywords
Funding Information
- Fondation Mathématique Jacques Hadamard (FMJH)
- Gaspard Monge Program for Optimization and operations research (PGMO)
This publication has 48 references indexed in Scilit:
- Computational Experience with Applications of Bilinear Cutting PlanesIndustrial & Engineering Chemistry Research, 2013
- Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxationsMathematical Programming, 2012
- Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisonsMathematical Programming, 2011
- Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-boundComputational Optimization and Applications, 2007
- Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 ProblemMathematical Programming, 2006
- Global optimization of mixed-integer nonlinear programs: A theoretical and computational studyMathematical Programming, 2004
- CSDP, A C library for semidefinite programmingOptimization Methods and Software, 1999
- ?BB: A global optimization method for general constrained nonconvex problemsJournal of Global Optimization, 1995
- New properties and computational improvement of the GOP algorithm for problems with quadratic objective functions and constraintsJournal of Global Optimization, 1993
- Algorithms for bound constrained quadratic programming problemsNumerische Mathematik, 1989