|
 
|
[QS10] A roof linearization algorithm to obtain a tight upper bound for integer nonseparable quadratic programming
Conférence Internationale avec comité de lecture : ISCO'10, Int. Symp. on Combinatorial Optimization, March 2010, pp.271-278, Series Electronic Notes in Discrete Mathematics, 36, Hammamet, Tunisie, (DOI: 10.1016/j.endm.2010.05.035)Mots clés: -
Résumé:
We study in this paper a general case of integer quadratic multi-knapsack
problem (QMKP) where the objective function is non separable. An upper
bound method is proposed for (QMKP) which is computed via two steps.
The rst stage aims to rewrite (QMKP) into an equivalent mixed integer
quadratic program (QPxy) where the objective function is separable, using
Gauss decomposition of the quadratic terms matrix. We then suggest an
original technique, we call roof linearization, to linearize (QPxy) so as to obtain a mixed linear program which optimal value provides an upper bound for (QPxy) and consequently for (QMKP). Preliminary computational ex-
periments are conducted so as to assess that the proposed algorithm provides a tight upper bound in fast CPU times. Our method is compared with the LP-relaxation of (QMKP) and the LP-relaxation of (QPxy).
Equipe:
oc
Collaboration:
LIA
BibTeX
| @inproceedings { | |||
| QS10, | |||
| title | = | "{A roof linearization algorithm to obtain a tight upper bound for integer nonseparable quadratic programming}", | |
| author | = | " D. Quadri and E. Soutil ", | |
| booktitle | = | "{ISCO'10, Int. Symp. on Combinatorial Optimization}", | |
| year | = | 2010, | |
| month | = | "March", | |
| series | = | "Electronic Notes in Discrete Mathematics, 36", | |
| pages | = | "271-278", | |
| address | = | "Hammamet, Tunisie", | |
| doi | = | "10.1016/j.endm.2010.05.035", | |
| } | |||
