Relax-and-Explore Kernel Search for the Multidimensional Multiple-Choice Knapsack Problem

We propose Relax-and-Explore Kernel Search (REKS), a novel matheuristic for the Multidimensional Multiple-Choice Knapsack Problem (MMKP). While the MMKP is a well-known combinatorial problem, existing methods often suffer from a heavy reliance on Linear Programming (LP) relaxations and high sensitivity to parameter tuning. Building upon the original Kernel Search (KS) framework (Angelelli et al., 2010) and its two-phase variants (Lamanna et al., 2022), REKS introduces a more robust approach to variable selection and subproblem exploration. The core of the methodology is a controlled-relaxation mechanism that identifies promising variables by solving a sequence of MILPs with incrementally relaxed resource constraints. By slightly increasing resource availability, the algorithm uncovers high-quality integer solutions (generally infeasible for the original problem) that provide a more informative set of variables for the initial kernel set than standard LP reduced costs. This is paired with an incremental bucket-exploration strategy, which dynamically enlarges subproblems during the search to mitigate the traditional KS dependence on fixed bucket sizes. Additionally, a multi-policy parallel search scheme is employed to balance intensification and diversification through varying kernel-update rules. Extensive computational results on standard benchmark instances (Mansi et al., 2013) demonstrate that REKS outperforms state-of-the-art heuristics. The algorithm matched or improved the best-known solutions in most instances and established itself as the unique best performer in a significant number of cases. These results confirm that REKS is a robust and highly effective framework capable of delivering near-optimal solutions for complex MILP problems while substantially reducing overall solution times.