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

Pesquisa Operacional

Lucas Létocart²  Marie-christine Plateau¹  Gérard Plateau² 

[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