Adaptive perturbed neighbourhood search for the expanding capacity multiple-choice knapsack problem

Abstract

In this paper, we develop a perturbed reactive-based neighbourhood search algorithm for the expanding constraint multiple-choice knapsack problem. It combines reactive tabu search with some specific neighbourhood search strategies to approximately solve the problem. The tests were conducted on randomly generated instances and executed in comparable benchmark scenarios to those of the literature. The results outperform those of the Cplex solver and demonstrate the high quality of the two approach versions.

Keywords:

• combinatorial optimization
• integer programming
• knapsack
• multiple-choice
• expanding
• metaheuristics

Acknowledgements

The author would like to thank Prof. Takeo Yamada and M. Byungjun You for their valuable suggestions and insightful discussions to help improving the paper. Many thanks to anonymous referees for their helpful comments and suggestions contributing to improving the presentation and the contents of the paper.