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

DOI10.1016/J.DAM.2023.10.018MaRDI QIDQ6180695zbMATH OpenOpenAlexFDO

Authors Marc Goerigk, Stefan Lendl, Lasse Wulf

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

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

Abstract: We study the computational complexity of multi-stage robust optimization problems. Such problems are formulated with alternating min/max quantifiers and therefore naturally fall into a higher stage of the polynomial hierarchy. Despite this, almost no hardness results with respect to the polynomial hierarchy are known. In this work, we examine the hardness of robust two-stage adjustable and robust recoverable optimization with budgeted uncertainty sets. Our main technical contribution is the introduction of a technique tailored to prove $Sigm{a}_3^p$-hardness of such problems. We highlight a difference between continuous and discrete budgeted uncertainty: In the discrete case, indeed a wide range of problems becomes complete for the third stage of the polynomial hierarchy; in particular, this applies to the TSP, independent set, and vertex cover problems. However, in the continuous case this does not happen and problems remain in the first stage of the hierarchy. Finally, if we allow the uncertainty to not only affect the objective, but also multiple constraints, then this distinction disappears and even in the continuous case we encounter hardness for the third stage of the hierarchy. This shows that even robust problems which are already NP-complete can still exhibit a significant computational difference between column-wise and row-wise uncertainty.

Recommendations

• Two-stage robust optimization problems with two-stage uncertainty
• Multistage robust discrete optimization via quantified integer programming
• On the complexity of min-max-min robustness with two alternatives and budgeted uncertainty
• Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty
• Robust two-stage combinatorial optimization problems under discrete demand uncertainties and consistent selection constraints

Cites work

• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A generic optimization framework for resilient systems
• A note on \(\Sigma_2^p\)-completeness of a robust binary linear program with binary uncertainty set
• A survey of adjustable robust optimization
• A unified framework for stochastic optimization
• Adjustable robust solutions of uncertain linear programs
• Bilevel knapsack with interdiction constraints
• Complete sets and the polynomial-time hierarchy
• Complexity of the multilevel critical node problem
• Computational Complexity
• Constructing uncertainty sets for robust linear optimization
• Investigating the recoverable robust single machine scheduling problem under interval uncertainty
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• Min-max-min robust combinatorial optimization
• Multistage robust discrete optimization via quantified integer programming
• On recoverable and two-stage robust selection problems with budgeted uncertainty
• On the approximability of robust spanning tree problems
• On the complexity of quantified integer programming
• Pinpointing the complexity of the interval min-max regret knapsack problem
• Recoverable robust representatives selection problems with discrete budgeted uncertainty
• Recoverable robust shortest path problems
• Robust discrete optimization and network flows
• Robust min-max regret covering problems
• Robust multistage optimization with decision-dependent uncertainty
• Robust optimization
• Robust optimization-methodology and applications
• Robust recoverable and two-stage selection problems
• Solving two-stage robust optimization problems using a column-and-constraint generation method
• The Price of Robustness
• The computational complexity of integer programming with alternations
• The concept of recoverable robustness, linear programming recovery, and railway applications
• The ellipsoid method and its consequences in combinatorial optimization
• The polynomial-time hierarchy
• The trouble with the second quantifier
• \(K\)-adaptability in two-stage robust binary programming

Cited in

(1)

• Recoverable robust shortest path problem under interval budgeted uncertainty representations

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6180695)