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

DOI10.1016/J.DAM.2023.10.018arXiv2209.01011OpenAlexW4388580578MaRDI QIDQ6180695FDOQ6180695

Authors: Marc Goerigk, Stefan Lendl, Lasse Wulf 

Publication date: 2 January 2024

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

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.

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)

Cites Work

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

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)