Robust network optimization under polyhedral demand uncertainty is \(NP\)-hard

DOI10.1016/j.dam.2009.09.025zbMath1185.90213OpenAlexW2134200749MaRDI QIDQ968181

Michel Minoux

Publication date: 5 May 2010

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

Full work available at URL: https://doi.org/10.1016/j.dam.2009.09.025

zbMATH Keywords

network flowsrobust optimizationmulticommodity flowsnetwork optimizationpolyhedral uncertainty

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items

The robust network loading problem with dynamic routing ⋮ Tractable approximations to a robust capacity assignment model in telecommunications under demand uncertainty ⋮ A robust optimization model for distribution network design under a mixed integer set of scenarios ⋮ On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows ⋮ Affine routing for robust network design ⋮ On 2-stage robust LP with RHS uncertainty: complexity results and applications ⋮ The maximum flow problem of uncertain network ⋮ Scenario based robust line balancing: Computational complexity ⋮ A comparison of routing sets for robust network design ⋮ Multipolar robust optimization ⋮ \(k\)-adaptive routing for the robust network loading problem ⋮ A comparison of different routing schemes for the robust network loading problem: polyhedral results and computation ⋮ On the approximability of robust network design ⋮ Two-stage robust LP with ellipsoidal right-hand side uncertainty is NP-hard ⋮ Recent advances in robust optimization: an overview ⋮ Multi-service multi-facility network design under uncertainty ⋮ Robust capacity assignment solutions for telecommunications networks with uncertain demands

Cites Work

• Unnamed Item
• On 2-stage robust LP with RHS uncertainty: complexity results and applications
• A theorem on flows in networks
• Routing of uncertain traffic demands
• On robust maximum flow with polyhedral uncertainty sets
• Combinatorial approaches to multiflow problems
• Partitioning procedures for solving mixed-variables programming problems
• The ellipsoid method and its consequences in combinatorial optimization
• A robustness approach to uncapacitated network design problems
• Robust solutions of uncertain linear programs
• Robust discrete optimization and its applications
• Robust discrete optimization and network flows
• Discrete cost multicommodity network optimization problems and exact solution methods
• Robust optimization-methodology and applications
• Applying Robust Optimization to Capacity Expansion of One Location in Telecommunications with Demand Uncertainty
• Two-Stage Robust Network Flow and Design Under Demand Uncertainty
• An approach to robust network design in telecommunications
• The Price of Robustness
• On the Existence of a Feasible Flow in a Stochastic Transportation Network
• Two-Processor Scheduling with Start-Times and Deadlines
• Robust Optimization for Power Systems Capacity Expansion under Uncertainty
• Robust capacity expansion of network flows