Pesquisa Operacional | |
An efficient hybrid heuristic method for the 0-1 exact k-item quadratic knapsack problem | |
Lucas Létocart2  Marie-christine Plateau1  Gérard Plateau2  | |
[1] ,Université Paris 13Villetaneuse,France | |
关键词: quadratic programming; 0-1 knapsack; quadratic convex reformulation; semidefinite programming; surrogate duality; hybridization; experiments; | |
DOI : 10.1590/S0101-74382014000100005 | |
来源: SciELO | |
【 摘 要 】
The 0-1 exact k-item quadratic knapsack problem (E - kQKP) consists of maximizing a quadratic function subject to two linear constraints: the first one is the classical linear capacity constraint; the second one is an equality cardinality constraint on the number of items in the knapsack. Most instances of this NP-hard problem with more than forty variables cannot be solved within one hour by a commercial software such as CPLEX 12.1. We propose therefore a fast and efficient heuristic method which produces both good lower and upper bounds on the value of the problem in reasonable time. Specifically, it integrates a primal heuristic and a semidefinite programming reduction phase within a surrogate dual heuristic. A large computational experiments over randomly generated instances with up to 200 variables validates the relevance of the bounds produced by our hybrid dual heuristic, which yields known optima (and prove optimality) in 90% (resp. 76%) within 100 seconds on the average.
【 授权许可】
CC BY
All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO202103040084112ZK.pdf | 1179KB | download |