[BEL12a] Convex reformulations of Integer Quadratically Constrained Problems

Conférence Internationale avec comité de lecture : ISMP (21th International Symposium of Mathematical programming), August 2012, pp.1 page, Berlin, Germany,

Mots clés: General integer programming, Quadratically constrained programming, Linear reformulation, Quadratic convex reformulation, Semi-definite programming, Experiments

Résumé: We consider a general integer program (QQP) where both the objective function and the constraints are quadratic. We show that the quadratic convex reformulation approach can be extended to that case. This approach consists in designing a program, equivalent to QQP, with a quadratic convex objective function and linear or quadratic convex constraints. The resulting program is then solved by a standard solver. We start by dealing with the objective function. For this, we solve a semi-definite program from which we deduce a reformulation of (QQP) as an equivalent problem (P) having a convex quadratic objective function. We then handle the quadratic constraints of (P). We propose and compare linear and quadratic convex reformulations of these constraints. Finally, we give some numerical results comparing our different approaches.

Equipe: oc


@inproceedings {
title="{Convex reformulations of Integer Quadratically Constrained Problems}",
author=" A. Billionnet and S. Elloumi and A. Lambert ",
booktitle="{ISMP (21th International Symposium of Mathematical programming)}",
pages="1 page",
address="Berlin, Germany",