Title: First-level tabu search approach for solving the multiple-choice multidimensional knapsack problem

Authors: Chaitr S. Hiremath; Raymond R. Hill

Addresses: Accenture Services Pvt. Ltd., Infinity Park, Malad (East), Mumbai – 400097, India ' Air Force Institute of Technology, 2950 Hobson Way, Bld 641, Suite 201, Dayton, OH 45433, USA

Abstract: We apply tabu search to the multiple-choice multidimensional knapsack problem. An initial solution involves a simple greedy heuristic. A neighbourhood is generated and a move is selected based on the best feasible neighbouring solution. The search continues for a fixed number of iterations and tabu search structures are used to improve the search process. We study the problem structure of available, benchmark, test problem instances and develop a new, more diverse set of test problem instances whose results better generalise to practice than do results obtained using existing test problems. We report the results of testing our tabu search approach versus existing solution approaches as applied to the available and our new test problem instances. The computational results show that our proposed approach performs comparably or better than the legacy heuristic approaches and clearly demonstrates that test problems affects how well results generalise to practice.

Keywords: optimisation; metaheuristics; multiple-choice tabu search; multidimensional knapsack problem; empirical analysis.

DOI: 10.1504/IJMHEUR.2013.054150

International Journal of Metaheuristics, 2013 Vol.2 No.2, pp.174 - 199

Received: 24 Aug 2012
Accepted: 25 Feb 2013

Published online: 05 Jul 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article