Authors: Hanafi, Saïd
Lazić, Jasmina
Mladenović, Nenad 
Wilbaut, Christophe
Crévits, Igor
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: New hybrid matheuristics for solving the multidimensional knapsack problem
Journal: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume: 6373 LNCS
First page: 118
Last page: 132
Conference: 7th International Workshop on Hybrid Metaheuristics, HM 2010; Vienna; Austria; 1 October 2010 through 2 October 2010
Issue Date: 22-Nov-2010
Rank: M23
ISBN: 978-3-642-16053-0
ISSN: 0302-9743
DOI: 10.1007/978-3-642-16054-7_9
In this paper we propose new hybrid methods for solving the multidimensional knapsack problem. They can be viewed as matheuristics that combine mathematical programming with the variable neighbourhood decomposition search heuristic. In each iteration a relaxation of the problem is solved to guide the generation of the neighbourhoods. Then the problem is enriched with a pseudo-cut to produce a sequence of not only lower, but also upper bounds of the problem, so that integrality gap is reduced. The results obtained on two sets of the large scale multidimensional knapsack problem instances are comparable with the current state-of-the-art heuristics. Moreover, a few best known results are reported for some large, long-studied instances.
Keywords: Decomposition | Integer Programming | Matheuristics | Multidimensional Knapsack Problem | Variable Neighbourhood Search
Publisher: Springer Link

Show full item record


checked on May 21, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.