Global solution of non-convex quadratically constrained quadratic programs. (2nd January 2019)

• Record Type: Journal Article
• Authors: Elloumi, Sourour; Lambert, Amélie
• Is Part Of: Optimization methods and software. Volume 34:Number 1(2019)
• Page Start: 98
• Page End: 114
• Publication Date: 2019-01-02
• Subjects: general mixed-integer quadratic programming -- global optimization -- spatial branch-and-bound -- quadratic convex relaxation -- experiments; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2017.1350675
• Languages: English
• ISSNs: 1055-6788

Abstract

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 calledMIQCR 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 ofMIQCR which applies to any QCQP. Let( P ) be a QCQP. Our approach to solve( P ) is first to build an equivalent mixed-integer quadratic problem( P ∗ ) . This equivalent problem( P ∗ ) has a quadratic convex objective function, linear constraints, and additional variables y that are meant to satisfy the additional quadratic constraintsy = x x T, where x are the initial variables of problem( P ) . We then propose to solve( P ∗ ) 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 ofQuadProgBB, and with the solversCplex, Couenne, Scip, BARON andGloMIQO .