A hybrid Lagrangian‐decomposition algorithm for the large‐scale selective multiple‐choice knapsack problem

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.