|
 
|
[BS04a] An exact method based on lagrangian decomposition for the 0-1 quadratic knapsack problem
Revue Internationale avec comité de lecture : Journal European Journal of Operational Research, vol. 157(3), pp. 565-575, 2004
motcle:
Résumé:
The 0-1 quadratic knapsack problem (QKP) consists of maximizing a pseudo-Boolean quadratic function with positive coefficients subject to a linear capacity constraint. We present in this paper a new exact method for solving this problem. This method makes use of the computation of an upper bound for (QKP) using a technique derived from the Lagrangean decomposition methods. The method we use is applied to very large sized problems and allows to find the optimum of problems up to 150 variables whatever their density is and up to 300 variables for problems with medium and low density.
KEY-WORDS: 0-1 quadratic optimization, knapsack, Lagrangean decomposition, computational results, branch and bound.
BibTeX
| @article { | |||
| BS04a, | |||
| title | = | "{An exact method based on lagrangian decomposition for the 0-1 quadratic knapsack problem}", | |
| author | = | "A. Billionnet and E. Soutil", | |
| journal | = | "European Journal of Operational Research", | |
| year | = | 2004, | |
| volume | = | 157, | |
| number | = | 3, | |
| pages | = | "565-575", | |
| } | |||
