An efficient hybrid heuristic method for the 0-1 exact k-item quadratic knapsack problem

摘要: The 0-1 exact k-item quadratic knapsack problem (E - kQKP) consists of maximizing a function subject to two linear constraints: the first one is classical capacity constraint; second an equality cardinality constraint on number items in knapsack. Most instances this NP-hard with more than forty variables cannot be solved within hour by commercial software such as CPLEX 12.1. We propose therefore fast and efficient heuristic method which produces both good lower upper bounds value reasonable time. Specifically, it integrates primal semidefinite programming reduction phase surrogate dual heuristic. A large computational experiments over randomly generated up 200 validates relevance produced our hybrid heuristic, yields known optima (and prove optimality) 90% (resp. 76%) 100 seconds average.