2239. An Expansion-Based Approach for Multistage Robust Discrete Linear Programs
Invited abstract in session WB-2: Robust Optimization, stream Discrete and Combinatorial Optimization.
Wednesday, 10:45-12:15Room: H4
Authors (first author is the speaker)
| 1. | Michael Hartisch
|
| Data Science, Friedrich-Alexander-Universität Erlangen-Nürnberg |
Abstract
In robust optimization, decision makers hedge against uncertainty by optimizing over worst-case scenarios—yet general-purpose frameworks for problems with more than two decision stages remain scarce. We introduce an expansion-based solver for multistage robust discrete linear programs. Leveraging the semantics of Quantified Integer Programming (QIP)—which extends Quantified Boolean Formulas with integer variables and linear constraints—we employ Counterexample-Guided Abstraction Refinement (CEGAR) on the scenario tree to resolve the underlying feasibility subproblems, iteratively refining only those branches that are crucial. To solve optimization problems, this is wrapped in a binary-search scheme over a linear objective function. Our solver outperforms existing search-based QIP methods on certain benchmarks and even delivers performance gains over leading expansion-based QBF solvers on specific instances.
Keywords
- Robust Optimization
- Integer Programming
- Constraint Programming
Status: accepted
Back to the list of papers