Relax-and-Explore Kernel Search for Multidimensional Multiple-Choice Knapsack Problems

We introduce the Relax-and-Explore Kernel Search (REKS), a novel matheuristic framework for the Multidimensional Multiple-choice Knapsack Problem (MMKP), addressing key limitations of classical Kernel Search (KS) methods. REKS overcomes the strong dependence on Linear Programming (LP) relaxation and sensitivity to bucket size by employing a controlled-relaxation mechanism: it identifies highly promising variables by solving a sequence of restricted Mixed-Integer Linear Programs (MILPs) with incrementally relaxed resource constraints. Furthermore, REKS incorporates a robust incremental bucket-exploration strategy that dynamically enlarges subproblems during the search, mitigating the traditional reliance on a fixed bucket size and enhancing robustness. These core components are integrated into a multi-policy parallel search scheme for strong diversification and intensification. REKS constitutes a general matheuristic framework adaptable to a broad class of MILP problems. Extensive computational evidence on standard MMKP benchmarks demonstrates the effectiveness of REKS, matching or improving upon the best-known solutions for many long-standing open instances, confirming its status as a uniquely powerful performer in this domain