A new upper bound for the 0-1 quadratic knapsack problem |
| |
| Affiliation: | 1. Universidad Autónoma de Madrid, Spain;2. Universidad Complutense de Madrid, Spain;3. Group for Research on Innovation, Productivity and Competitiveness (GRIPICO), Spain;1. UCO-IMA, Université Bretagne Loire, LARIS EA7315, Angers, France;2. Université François-Rabelais de Tours, CNRS, LI EA 6300, ROOT ERL CNRS 6305, Tours, France;3. Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montreal, Canada;4. Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montreal, Canada |
| |
| Abstract: | The 0-1 quadratic knapsack problem (QKP) consists in maximizing a positive quadratic pseudo-Boolean function subject to a linear capacity constraint. We present in this paper a new method, based on Lagrangian decomposition, for computing an upper bound of QKP. We report computational experiments which demonstrate the sharpness of the bound (relative error very often less than 1%) for large size instances (up to 500 variables). |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
