|
 
|
[BEL08a] Linear Reformulations of Integer Quadratic Programs
Conférence Internationale avec comité de lecture : MCO'08, 2nd international conference on Modelling, Computation and Optimization in Information Systems and Management Sciences, September 2008, pp.43-51, Series LNCS, Metz, France, (DOI: ISBN 978-3-540-87476-8)Mots clés: -Integer programming, quadratic programming, linear reformulations, Experiments
Résumé:
- Let (QP) be an integer quadratic program that consists in minimizing a quadratic function subject to linear constraints. In this paper, we present several linearizations of (QP).
Many linearization methods for the quadratic 0-1 programs are known. A natural approach when considering (QP) is to reformulate it into a quadratic 0-1 program. However, this method, that we denote BBL(Binary Binary Linearization), leads to a quadratic program with a large number of variables and constraints.
Our new approach, BIL(Binary Integer Linearization), consists in reformulating (QP) into a particular quadratic integer program where each quadratic term is the product of an integer variable by a 0-1 variable. The obtained integer linear program is significantly smaller than in the BBL approach.
Each reformulation leads to an integer linear program that we improve by adding valid inequalities. Finally, we get 4 different programs that we compare from the computational point of view.
Equipe:
oc
BibTeX
| @inproceedings { | |||
| BEL08a, | |||
| title | = | "{Linear Reformulations of Integer Quadratic Programs}", | |
| author | = | " A. Billionnet and S. Elloumi and A. Lambert ", | |
| booktitle | = | "{MCO'08, 2nd international conference on Modelling, Computation and Optimization in Information Systems and Management Sciences}", | |
| year | = | 2008, | |
| edition | = | "I", | |
| month | = | "September", | |
| series | = | "LNCS", | |
| issue | = | 14, | |
| pages | = | "43-51", | |
| address | = | "Metz, France", | |
| doi | = | "ISBN 978-3-540-87476-8", | |
| } | |||
