Metraipolis › archive › dc_364a8bf170ec

Simultaneous Group-Envelope Bounds for $Γ$-Robust Multiple-Choice Knapsack Problems — arXiv:2608.08861

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.08861
License (as archived)
CC0-1.0
Archived
2026-10-19T09:05:26.676Z
SHA-256 of the archived text
41fae4544efc419021e7436d99d5cc3808cb9c4bd7ac7789779793c68d5402be
Stable URL of this page
https://metraipolis.com/documento/dc_364a8bf170ec

How to cite

Simultaneous Group-Envelope Bounds for $Γ$-Robust Multiple-Choice Knapsack Problems — arXiv:2608.08861 — arXiv (en), https://arxiv.org/abs/2608.08861 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_364a8bf170ec (Metraipolis archive dc_364a8bf170ec, sha256 41fae4544efc419021e7436d99d5cc3808cb9c4bd7ac7789779793c68d5402be)
BibTeX
@misc{dc364a8bf170ec,
  title = {Simultaneous Group-Envelope Bounds for $Γ$-Robust Multiple-Choice Knapsack Problems — arXiv:2608.08861},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.08861},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_364a8bf170ec; sha256 41fae4544efc419021e7436d99d5cc3808cb9c4bd7ac7789779793c68d5402be},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.08861. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-11 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2608.08861 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T09:03:32.065Z dalla pagina https://arxiv.org/catchup/math.OC/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).