← 研踪 PaperTrailarXiv:2210.11132 · v2
A Search-Based Algorithm for Multistage Robust Discrete Linear Optimization and its Implementation
首次提交 2022-10-20 17:49
版本更新 2026-10-27 17:28
雷达观测 2026-10-29 00:35
摘要
Robust optimization models that allow decisions to adapt to newly revealed information remain computationally challenging and are often limited to two decision stages or are addressed heuristically or via approximation schemes. This challenge is further amplified when uncertainty sets depend on earlier decisions. Conventional approaches to such problems often require problem-specific reformulations and tailored algorithms, highlighting the need for an exact model-and-run approach. We address this gap by presenting an algorithmic framework for solving multistage robust discrete linear optimization problems. This exact approach adapts and integrates ideas from game-tree search, quantified conflict-driven clause learning, and integer linear programming to explore the minimax tree and is implemented in the open-source solver Yasol. The solver supports discrete decision variables across multiple stages, discrete uncertainty sets with polyhedral or decision-dependent structure, and mixed-integer recourse in the final stage. It can be used as a standalone executable or through a C++ library interface, allowing it to serve as a reference solver for exact methods in multistage robust discrete linear optimization. In an extensive computational study, we demonstrate the capabilities of our solver. The results show competitive performance against a reference approach from the literature for a protection-interdiction problem, as well as strong performance on bilevel benchmark instances. For a multistage cutting-stock problem, we demonstrate the substantial loss in solution quality that can arise from neglecting the multistage structure and show that our solver significantly outperforms decision-rule approximations in terms of computational efficiency while certifying the true multistage optimum.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-10-27 17:28 · 最新观测版本
A Search-Based Algorithm for Multistage Robust Discrete Linear Optimization and its Implementation
Robust optimization models that allow decisions to adapt to newly revealed information remain computationally challenging and are often limited to two decision stages or are addressed heuristically or via approximation schemes. This challenge is further amplified when uncertainty sets depend on earlier decisions. Conventional approaches to such problems often require problem-specific reformulations and tailored algorithms, highlighting the need for an exact model-and-run approach. We address this gap by presenting an algorithmic framework for solving multistage robust discrete linear optimization problems. This exact approach adapts and integrates ideas from game-tree search, quantified conflict-driven clause learning, and integer linear programming to explore the minimax tree and is implemented in the open-source solver Yasol. The solver supports discrete decision variables across multiple stages, discrete uncertainty sets with polyhedral or decision-dependent structure, and mixed-integer recourse in the final stage. It can be used as a standalone executable or through a C++ library interface, allowing it to serve as a reference solver for exact methods in multistage robust discrete linear optimization. In an extensive computational study, we demonstrate the capabilities of our solver. The results show competitive performance against a reference approach from the literature for a protection-interdiction problem, as well as strong performance on bilevel benchmark instances. For a multistage cutting-stock problem, we demonstrate the substantial loss in solution quality that can arise from neglecting the multistage structure and show that our solver significantly outperforms decision-rule approximations in terms of computational efficiency while certifying the true multistage optimum.
查看此版本解读 →查看此版本原文 ↗