Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem - ENSTA Paris - École nationale supérieure de techniques avancées Paris Accéder directement au contenu
Article Dans Une Revue Mathematical Programming Computation Année : 2007

Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem

Résumé

Abstract In this paper, we consider problem (P) of minimizing a quadratic function q(x)=x t Qx+c t x of binary variables. Our main idea is to use the recent Mixed Integer Quadratic Programming (MIQP) solvers. But, for this, we have to first convexify the objective function q(x). A classical trick is to raise up the diagonal entries of Q by a vector u until (Q+diag(u)) is positive semidefinite. Then, using the fact that x i 2=x i, we can obtain an equivalent convex objective function, which can then be handled by an MIQP solver. Hence, computing a suitable vector u constitutes a preprocessing phase in this exact solution method. We devise two different preprocessing methods. The first one is straightforward and consists in computing the smallest eigenvalue of Q. In the second method, vector u is obtained once a classical SDP relaxation of (P) is solved. We carry out computational tests using the generator of (Pardalos and Rodgers, 1990) and we compare our two solution methods to several other exact solution methods. Furthermore, we report computational results for the max-cut problem.
Fichier principal
Vignette du fichier
MPA_Bil_Ell.pdf (160.97 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01125239 , version 1 (01-01-2021)

Identifiants

Citer

Alain Billionnet, Sourour Elloumi. Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem. Mathematical Programming Computation, 2007, 109 (1), pp.55-68. ⟨10.1007/s10107-005-0637-9⟩. ⟨hal-01125239⟩
270 Consultations
654 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More