Dynamic Multidimensional Knapsack Problem benchmark datasets

Abstract

With increasing research on solving Dynamic Optimization Problems (DOPs), many metaheuristic algorithms and their adaptations have been proposed to solve them. However, from currently existing research results, it is hard to evaluate the algorithm performance in a repeatable way for combinatorial DOPs due to the fact that each research work has created its own version of a dynamic problem dataset using stochastic methods. Up to date, there are no combinatorial DOP benchmarks with replicable qualities. This work introduces a non-stochastic consistent Dynamic Multidimensional Knapsack Problem (Dynamic MKP) dataset generation method that is also extensible to solve the research replicability problem. Using this method, generated and published 1405 Dynamic MKP benchmark datasets using existing famous static MKP benchmark instances as the initial state. Then the datasets are quantitatively and qualitatively analyzed. Furthermore, 445 datasets have the optimal result found of each state using a linear solver. The optimal results and result scores are included with published datasets.

Keywords

• Dynamic MKP
• benchmark datasets
• discrete dynamic optimization
• non-stochastic dataset generation