Simultaneous Group-Envelope Bounds for $Γ$-Robust Multiple-Choice Knapsack Problems

Abstract

Many robust planning problems are solved by checking a family of ordinary optimization problems, one for each uncertainty threshold. Repeatedly building and solving those relaxations can dominate runtime. We show that, when a decision chooses exactly one option from each group, the entire threshold family of multiple-choice knapsack relaxations can instead be bounded together. A cancellation removes threshold-specific baselines and reduces each group's contribution to two simple envelopes. After sorting, one multiplier is evaluated across all thresholds in time linear in their number and nearly linear in the number of options. The resulting interval bound is valid, matches the ordinary relaxation on a single feasible threshold, and is at least as strong as the matched group-clique comparator. A certified one-dimensional search controls multiplier error, while exact checks resolve numerically ambiguous feasibility and comparison cases. In an otherwise identical adaptive search, the method wins all 60 instance-level median comparisons and achieves a 2.37-fold geometric-mean speedup. Additional ablations, independent linear-program checks, and nine instances transformed from a published archive test the mechanism beyond the internal generator. A separate integer audit shows the boundary: faster relaxation bounds need not help when integer search dominates.

Disclosure

“available at https://github.com/eric939/simultaneous-group-envelop e-mckp. The evidence directory contains the serialized protocol, per-phase environments, raw CSV files, JSON summaries, and the SHA-256 artifact manifest. Acknowledgments OpenAI ChatGPT and Codex assisted with drafting, editing, code generation, and computational and mathematical auditing. The author reviewed and verified the work and assumes full responsibility. A Comparator and exact-integration implementation The”

PDF page 16

Classification

Drafting limited passages

Multiplier

5

Verified

2026-08-23T05:06:17.064839Z

Structural counts