Verifying new instances of the multidemand multidimensional knapsack problem with instance space analysis

The optimization literature contains numerous studies defining a problem and showing a state-of-the-art implementation of a solution method. These studies may involve an empirical evaluation of the solution methods but assume the current collection of test instances is sufficient. This paper is concerned with instance generation methods for the multidemand multidimensional knapsack problem. We use instance space analysis to characterize the landscape of existing instances and validate the novelty of new instances. We discuss gaps present within the current instance space landscape and fill them with three new sets of instances. We find feasibility issues within instance generation methods and address them through a primal problem instance generator (PPIG). The instance generator is capable of producing feasible and diverse instances by directly controlling the problem features. PPIG contributes to the previous collections of instances and is validated through instance space analysis.

Automated summary

This paper discusses instance generation methods for the multidemand multidimensional knapsack problem and introduces a primal problem instance generator (PPIG) to address feasibility issues in current instance generation methods.