Centre d'Etude et De Recherche en Informatique et Communications (EA4629) |
|
A branch-and-bound algorithm to solve large scale integer quadratic multidimensional knapsack problem
[QST07a] A branch-and-bound algorithm to solve large scale integer quadratic multidimensional knapsack problem
Conférence Internationale avec comité de lecture : SOFSEM'07, Harrachov, République Tchèque, January 2007, Vol. 4362, pp.456-464, Series LNCS 4362,
motcle:
Résumé:
The separable quadratic multi-knapsack problem (QMKP) consists in maximizing a concave separable quadratic integer (non pure binary) function subject to m linear capacity constrainsts. In this paper we develop a branch-and-bound algorithm to solve (QMKP) to optimality. This method is based on the computation of a tight upper bound for (QMKP) wich is derived from a linearization and a surrogate relaxation. Our branch-and-bound also incorporates pre-processing procedures. The computational performance of our branch-andèbound is copared to that of three exact methods: a branch-and-bound algorithm developed by Djerdjour et al. (1988), a 0-1 linearization ethod originally applied to the separable quadratic knapsack problem with a single constraint that we extend to the case of m constraints, a standard branch-and-bound algorithm (Cplex 9.0 quadratic optimization). Our branch-and-bound clearly outperforms other methods for large instances (up to 2000 variables and constraints).
Equipe:
oc
| @inproceedings { | |||
| QST07a, | |||
| title | = | "{A branch-and-bound algorithm to solve large scale integer quadratic multidimensional knapsack problem}", | |
| author | = | " D. Quadri and E. Soutif and P. Tolla ", | |
| booktitle | = | "{SOFSEM'07, Harrachov, République Tchèque}", | |
| year | = | 2007, | |
| month | = | "January", | |
| series | = | "LNCS 4362", | |
| volume | = | 4362, | |
| pages | = | "456-464", | |
| } | |||
Agenda
 Suivre le laboratoire
|
ContactsCNAM-CEDRIC ENSIIE-CEDRIC |