Title: Simple population-based metaheuristics for the multiple demand multiple-choice multidimensional knapsack problem

Authors: Dylan Gaspar; Yun Lu; Myung Soon Song; Francis J. Vasko

Addresses: Department of Mathematics, Kutztown University, Kutztown, PA 19530, USA ' Department of Mathematics, Kutztown University, Kutztown, PA 19530, USA ' Department of Mathematics, Kutztown University, Kutztown, PA 19530, USA ' Department of Mathematics, Kutztown University, Kutztown, PA 19530, USA

Abstract: The multiple-demand, multiple-choice, multi-dimensional knapsack problem (MDMMKP), defined by Lamine et al. (2012), is a generalisation of the classic 0-1 knapsack problem. The MDMMKP can easily be shown to be NP-hard. As usual, the objective of the MDMMKP is to maximise the value of objects placed in one knapsack. In this case, there are three categories of constraints. The constraints are multiple demand constraints, multiple-choice constraints, and multiple dimensional constraints. To our knowledge, there are no published solution methods designed to solve the MDMMKP, i.e., methods designed to handle all three categories of constraints in the same problem. In this paper, we develop several simple population-based metaheuristics that are founded on the teaching-learning-based optimisation (TLBO) metaheuristic (Rao et al., 2011) and the Jaya metaheuristic (Rao, 2016). It is important to note that both TLBO and Jaya were originally developed for continuous nonlinear engineering design problems. To test the performance of these metaheuristics, we will use 810 MDMMKP problem instances recently defined by Lu and Vasko (2019). The empirical results will be examined using statistical analyses.

Keywords: multi-demand; multiple-choice; multi-dimensional knapsack problem; MDMMKP; Jaya metaheuristic; teaching-learning based optimisation metaheuristic; population-based metaheuristics; hybrid metaheuristics.

DOI: 10.1504/IJMHEUR.2020.111600

International Journal of Metaheuristics, 2020 Vol.7 No.4, pp.330 - 351

Received: 12 Aug 2019
Accepted: 22 Jan 2020
Published online: 03 Dec 2020 *

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