A hybrid Lagrangian‐decomposition algorithm for the large‐scale selective multiple‐choice knapsack problem
- 28 September 2026
- journal article
- research article
- Published by Wiley in International Transactions in Operational Research
Abstract
Decomposition is a natural route to scalability for the selective multiple‐choice knapsack problem (Selective‐MCKP), an NP‐hard variant arising in resource allocation with over 100,000 decision classes, where solving the global mixed‐integer program is prohibitive. The natural parallel heuristic partitions the classes across workers with an equal budget share each, ignoring the heterogeneous profit‐cost structure across partitions and leaving substantial profit unclaimed. We quantify this loss with a partition‐optimal baseline and introduce the hybrid Lagrangian‐decomposition algorithm (HLD), which keeps the parallel partition structure but replaces the equal split with a data‐driven allocation guided by Lagrangian dual prices. On a Selective‐MCKP benchmark spanning 1000, 10,000, and 100,000 decision classes across four profit‐cost correlation regimes, HLD is essentially optimal against the HiGHS open‐source reference up to 10,000 classes (paired median gap below 0.1%). For 100,000 classes, where the reference solver no longer finishes, HLD gains a paired median of +17.19% over partition‐optimal across 2046 instances. Results are fixed‐time: under a 60‐second budget HLD times out on 81.14% of these instances, and the median gain grows by +141.85% at 300 seconds. The contribution is specific: HLD recovers equal‐split allocation loss rather than beating every heuristic, since at the largest scale an instantaneous greedy can outscore a single timed‐out HLD solve. A released guarded wrapper returns the better of partition‐optimal and HLD, removing the downside on homogeneous instances while keeping every win. All baselines are open source, and the benchmark, calibrated configuration, and analysis pipeline are released openly.Keywords
This publication has 37 references indexed in Scilit:
- Survey on Lagrangian relaxation for MILP: importance, challenges, historical review, recent advancements, and opportunitiesAnnals of Operations Research, 2023
- Analysis of Divide-and-Conquer strategies for the 0–1 minimization knapsack problemJournal of Combinatorial Optimization, 2020
- A multi-criteria approach to approximate solution of multiple-choice knapsack problemComputational Optimization and Applications, 2018
- Parallelizing the dual revised simplex methodMathematical Programming Computation, 2017
- A Multi Criteria Knapsack Solution to Optimise Natural Resource Management Project Selection2009
- Greedy algorithm for the general multidimensional knapsack problemAnnals of Operations Research, 2006
- The Multiple-Choice Knapsack Problem2004
- Lagrangean relaxationTOP, 2003
- Knapsack Problems1998
- A class of generalized greedy algorithms for the multi-knapsack problemDiscrete Applied Mathematics, 1993