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

AUTOR(ES)

Létocart, Lucas, Plateau, Marie-Christine, Plateau, Gérard

FONTE

Pesqui. Oper.

DATA DE PUBLICAÇÃO

2014-04

RESUMO

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.

Documentos Relacionados

• ALGORITHM RELAX-AND-CUT FOR THE 0-1 QUADRATIC KNAPSACK PROBLEM
• Uso de cortes canonicos no metodo de ramificação local para problemas inteiros 0-1 mistos
• Algoritmos relax-and-cut para problemas de programação inteira 0-1
• Um estudo computacional da busca tabu paramétrica para programação inteira mista 0-1
• PROGRAMAÇÃO HIPERBÓLICA EM VARIÁVEIS 0-1 E OTIMIZAÇÃO DE CONSULTAS A BANCOS DE DADOS BIBLIOGRAFICOS