On the complexity of robust multi-stage problems with discrete recourse

DOI10.1016/j.dam.2023.10.018arXiv2209.01011OpenAlexW4388580578MaRDI QIDQ6180695

Marc Goerigk, Lasse Wulf, Stefan Lendl

Publication date: 2 January 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2209.01011

zbMATH Keywords

combinatorial optimizationrobust optimizationpolynomial hierarchymulti-stage optimizationrobust recoverable optimizationrobust adjustable optimization

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Robustness in mathematical programming (90C17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pinpointing the complexity of the interval min-max regret knapsack problem
• Min-max-min robust combinatorial optimization
• On the approximability of robust spanning tree problems
• Investigating the recoverable robust single machine scheduling problem under interval uncertainty
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• The ellipsoid method and its consequences in combinatorial optimization
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• Robust discrete optimization and network flows
• Adjustable robust solutions of uncertain linear programs
• On recoverable and two-stage robust selection problems with budgeted uncertainty
• A unified framework for stochastic optimization
• A survey of adjustable robust optimization
• Robust optimization-methodology and applications
• The trouble with the second quantifier
• Robust multistage optimization with decision-dependent uncertainty
• Complexity of the multilevel critical node problem
• Recoverable robust representatives selection problems with discrete budgeted uncertainty
• Robust min-max regret covering problems
• Robust recoverable and two-stage selection problems
• Solving two-stage robust optimization problems using a column-and-constraint generation method
• A note on \(\Sigma_2^p\)-completeness of a robust binary linear program with binary uncertainty set
• Multistage robust discrete optimization via quantified integer programming
• Recoverable robust shortest path problems
• Constructing Uncertainty Sets for Robust Linear Optimization
• Bilevel Knapsack with Interdiction Constraints
• K-Adaptability in Two-Stage Robust Binary Programming
• The Price of Robustness
• The Concept of Recoverable Robustness, Linear Programming Recovery, and Railway Applications
• The Computational Complexity of Integer Programming with Alternations
• On the Complexity of Quantified Integer Programming
• Computational Complexity
• A generic optimization framework for resilient systems

This page was built for publication: On the complexity of robust multi-stage problems with discrete recourse