|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||Abstract:||
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 Apr 14, 2021
checked on Apr 15, 2021
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.