|
 
|
[BEL16a] Exact quadratic convex reformulations of mixed-integer quadratically constrained problems
Revue Internationale avec comité de lecture : Journal Mathematical Programming, vol. 158(1-2), pp. 235-266, 2016, (doi:10.1007/s10107-015-0921-2)Mots clés: Integer quadratic programming - Equivalent convex reformulation - Semidefinite programming - Branch-and-bound algorithm
Résumé:
We propose a solution approach for the general problem (QP) of minimizing a quadratic function of
bounded integer variables subject to a set of quadratic constraints. The resolution is based on the
reformulation of the original problem (QP) into an equivalent quadratic problem whose continuous
relaxation is convex, so that it can be effectively solved by a branch-and-bound algorithm based on
quadratic convex relaxation. We concentrate our efforts on finding a reformulation such that the
continuous relaxation bound of the reformulated problem is as tight as possible. Furthermore, we extend
our method to the case of mixed-integer quadratic problems with the following restriction: all quadratic
sub-functions of purely continuous variables are already convex. Finally, we illustrate the different results
of the article by small examples and we present some computational experiments on pure-integer and
mixed-integer instances of (QP). Most of the considered instances with up to 53 variables can be solved by
our approach combined with the use of Cplex.
Equipe:
oc
BibTeX
| @article { | |||
| BEL16a, | |||
| title | = | "{Exact quadratic convex reformulations of mixed-integer quadratically constrained problems }", | |
| author | = | "A. Billionnet and S. Elloumi and A. Lambert", | |
| journal | = | "Mathematical Programming", | |
| year | = | 2016, | |
| volume | = | 158, | |
| number | = | 1-2, | |
| pages | = | "235-266", | |
| doi | = | "10.1007/s10107-015-0921-2", | |
| } | |||
