Authors: Hanafi, Saïd
Lazic, Jasmina
Mladenović, Nenad 
Wilbaut, Christophe
Title: Variable neighbourhood decomposition search with bounding for multidimensional knapsack problem
Journal: IFAC Proceedings Volumes (IFAC-PapersOnline)
Volume: 13
Issue: PART 1
First page: 2018
Last page: 2022
Conference: 13th IFAC Symposium on Information Control Problems in Manufacturing, INCOM'09; Moscow; Russian Federation; 3 June 2009 through 5 June 2009
Issue Date: 1-Dec-2009
ISBN: 978-3-902-66143-2
ISSN: 1474-6670
DOI: 10.3182/20090603-3-RU-2001.0502
In this paper we propose a new heuristic for solving multidimensional knapsack problem, based on the variable neighbourhood decomposition search principle. The set of neighbourhoods is generated by exploiting information obtained from a series of relaxations. In each iteration, we add new constraints to the problem in order to produce a sequence of lower and upper bounds around the optimal value, with the goal to reduce the gap between them. General-purpose CPLEX MIP solver is used as a black box for solving subproblems generated during the search process. With this approach, we have managed to obtain promising results on a set of large scale multidimensional knapsack problem instances. The results are comparable with the current state-of-the-art techniques for solving multidimensional knapsack problem.
Keywords: 0-1 mixed integer programming | Combinatorial optimisation | CPLEX | Heuristics | Multidimensional knapsack problem | Variable neighbourhood decomposition search
Publisher: Elsevier

Show full item record


checked on Jun 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.