[BEL11] A solution method for quadratically constrained integer problems

Conférence Internationale avec comité de lecture : Optimization 2011, Lisbon, Portugal., July 2011, pp.64,

Mots clés: Integer quadratic programming, convex reformulation,semidefinite programming

Résumé: We consider an integer program (QQP) where both the objective function and the constraints contain quadratic terms. We show that the quadratic convex reformulation approach can be extended to that case. We start by solving a semidefinite programming problem (SDP). From the dual solution of SDP, we deduce reformulation of QQP as an equivalent problem (QLP) having a convex quadratic objective and linear constraints. Problem (QLP) is then solved by a mixed integer quadratic programming solver. The interesting point is that the continuous relaxation bound of QLP is equal to the optimal value of SDP. We give some numerical results showing the efficiency of the approach.

Equipe: oc


@inproceedings {
title="{A solution method for quadratically constrained integer problems}",
author=" A. Billionnet and S. Elloumi and A. Lambert ",
booktitle="{Optimization 2011, Lisbon, Portugal.}",