A Column Generation Approach via Lagrangian Decomposition for the Multidimensional Multiple-Choice Knapsack Problem

The Multidimensional Multiple-Choice Knapsack Problem (MMCKP) is a complex combinatorial optimization problem that extends the classic knapsack problem by requiring exactly one item to be selected from several disjoint sets while respecting multiple resource constraints (Cacchiani et al., 2022). Given its applications in chip multiprocessor runtime resource management and global routing of wiring in circuits, finding high-quality solutions and tight dual bounds is a critical challenge. This paper presents a decomposition-based exact framework that reformulates the MMCKP using Lagrangian decomposition. This reformulation results in a model with an exponential number of variables, which we manage using Column Generation, that represent feasible configurations for individual resources. The primary challenge involves ensuring that these independent resource selections agree on a single set of items (Voss et al., 2016). In our approach, we relax these consistency constraints in the master problem via Lagrangian relaxation and the pricing subproblems are reduced to one-dimensional multiple-choice knapsack problems, which can be solved efficiently via dynamic programming. To mitigate the common convergence issues associated with column generation, such as dual degeneracy and the "tailing-off" effect, we discuss and evaluate several algorithmic enhancements. These include reduced-cost variable fixing based on initial primal heuristics, the use of dual-optimal inequalities to stabilize the master problem, and a dual heuristic to accelerate convergence of the subgradient method. Finally, we present preliminary results on benchmark instances to assess the scalability of this framework against traditional compact formulations for the MMCKP.