An efficient compact quadratic convex reformulation for general integer quadratic programs

Alain Billionnet, Sourour Elloumi and Amélie Lambert
2013
Type de publication :
Article (revues avec comité de lecture)
Journal :
Computational Optimization and Applications, vol. 54, pp. 141-162
Editeur :
Springer Verlag
HAL :
hal-01126098
Mots clés :
Computational experiments; Integer Programming; Exact Convex Reformulation; Quadratic Programming;
Résumé :
We address the exact solution of general integer quadratic programs with linear constraints. These programs constitute a particular case of mixed-integer quadratic programs for which we introduce in a general solution method based on quadratic convex reformulation, that we called MIQCR. This reformulation consists in designing an equivalent quadratic program with a convex objective function. The problem reformulated by MIQCR has a relatively important size that penalizes its solution time. In this paper, we propose a convex reformulation less general than MIQCR because it is limited to the general integer case, but that has a significantly smaller size. We call this approach Compact Quadratic Convex Reformulation (CQCR). We evaluate CQCR from the computational point of view. We perform our experiments on instances of general integer quadratic programs with one equality constraint. We show that CQCR is much faster than MIQCR and than the general non-linear solver BARON to solve these instances. Then, we consider the particular class of binary quadratic programs. We compare MIQCR and CQCR on instances of the Constrained Task Assignment Problem. These experiments show that CQCR can solve instances that MIQCR and other existing methods fail to solve.
Mots clés (traduction) :
Programmation en nombres entiers; Expériences computationnelles; Programmation quadratique; Exacte Reformulation convexe;
BibTeX :
@article{Bil-Ell-Lam-2013,
    author={Alain Billionnet and Sourour Elloumi and Amélie Lambert },
    title={An efficient compact quadratic convex reformulation for 
           general integer quadratic programs },
    journal={Computational Optimization and Applications },
    year={2013 },
    volume={54 },
    pages={141--162},
}