Exploring the Impact of Local Operator Configurations in the Multi-Demand Multidimensional Knapsack Problem

Abstract

The Multi-demand Multidimensional Knapsack Problem (MDMKP) is a challenging combinatorial task due to its capacity and demand constraints. Local search operators play a key role in metaheuristics when navigating such complex solution spaces, yet their impact on MDMKP performance has received limited attention. In this work, we investigate four local operator configurations—Add, Drop, Swap, and All Operator—within the Whale Optimization Algorithm framework. Our approach integrates these operators to broaden search coverage and refine candidate solutions. This design aims to enhance solution quality by balancing exploration and exploitation across multiple dimensions of the MDMKP. Experimental results on benchmark instances with different sizes (n=100,250, and 500) show that the All Operator configuration consistently achieves better maximum and average values. In large-scale instances (n = 500), the “All Operator” configuration achieves an average maximum value of 107,967, which is approximately 1.4% higher than the 106,490 achieved by the “Add Operator” and about 0.2% higher than the 107,771 obtained by the “Swap Operator”, while significantly outperforming the “Drop Operator” (average maximum of 99,164). Statistical tests confirm its advantage over the other configurations, suggesting that combining multiple local operators can significantly strengthen performance in high-dimensional and constraint-heavy settings like the MDMKP.

Keywords

• combinatorial optimization
• machine learning
• metaheuristics
• multi-demand multidimensional knapsack problem