Advancing Kernel Search for Multidimensional Multiple-Choice Knapsack Problems via Resource Relaxation

We propose a novel adaptation of the Kernel Search (KS) framework to the Multidimensional Multiple-Choice Knapsack Problem (MMKP), inspired by the original work by Angelelli, Mansini, and Speranza (2010) and its recent two-phase variant applied to the same problem by Lamanna, Mansini, and Zanotti (2022). The key idea behind the new method is to exploit the insights obtained by incrementally relaxing the multidimensional knapsack constraints, slightly increasing their resource availability, to discover new high-quality (possibly infeasible for the original problem) integer solutions. More precisely, we use the information provided by each resource relaxation (represented by the solution to the corresponding continuous relaxation, reduced-cost coefficients, and integer solutions) to identify promising variables likely to be positive in the optimal solution of the original problem. Such knowledge allows us to construct an informative kernel set and a series of buckets on which KS iteratively solves reduced MILPs. Whenever a new best integer solution is found, variable fixing is applied to set the variables to their optimal values. This possibly reduces the search space and creates a new restricted problem, allowing the process to be restarted iteratively. This approach demonstrates great potential in narrowing the relevant subset of variables for the MILP solution while preserving quality. Our preliminary computational results confirm that the method is able to find near-optimal solutions while significantly reducing solution times on benchmark MMKP instances (Mansi et al., 2013). This adaptation opens up new directions in the development of matheuristic frameworks in combinatorial optimization.