Robust network optimization under polyhedral demand uncertainty is NP-hard

DOI10.1016/J.DAM.2009.09.025zbMATH Open1185.90213OpenAlexW2134200749MaRDI QIDQ968181FDOQ968181

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 optimizationnetwork optimizationmulticommodity flowspolyhedral uncertainty

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (20)

• Robust optimization model for a dynamic network design problem under demand uncertainty
• Robust capacity assignment solutions for telecommunications networks with uncertain demands
• \(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
• Multi-service multi-facility network design under uncertainty
• Multipolar robust optimization
• Scenario based robust line balancing: Computational complexity
• On the approximability of robust network design
• Robust Metric Inequalities for Network Loading Under Demand Uncertainty
• Recent advances in robust optimization: an overview
• Tractable approximations to a robust capacity assignment model in telecommunications under demand uncertainty
• A comparison of routing sets for robust network design
• Two-stage robust LP with ellipsoidal right-hand side uncertainty is NP-hard
• On 2-stage robust LP with RHS uncertainty: complexity results and applications
• A robust optimization model for distribution network design under a mixed integer set of scenarios
• A Hybrid Polyhedral Uncertainty Model for the Robust Network Loading Problem
• Affine routing for robust network design
• The robust network loading problem with dynamic routing
• The maximum flow problem of uncertain network
• On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows

   Recommendations

• Hardness of robust network design 👍 👎
• Approximability of robust network design 👍 👎
• On robust maximum flow with polyhedral uncertainty sets 👍 👎
• Robust Two-Stage Network Problems 👍 👎
• Two-Stage Robust Network Flow and Design Under Demand Uncertainty 👍 👎

This page was built for publication: Robust network optimization under polyhedral demand uncertainty is \(NP\)-hard

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