Single-commodity robust network design with finite and hose demand sets

DOI10.1007/s10107-016-0991-9zbMath1338.90466OpenAlexW2182031487MaRDI QIDQ291071

Daniel R. Schmidt, Frauke Liers, Valentina Cacchiani, Andrea Lodi, Michael Jünger

Publication date: 6 June 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: http://e-archive.informatik.uni-koeln.de/771/1/techreport.pdf

zbMATH Keywords

branch-and-cutcut-set inequalitiespolyhedral demand uncertaintyrobust network designseparation under uncertainty

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items

Network design in scarce data environment using moment-based distributionally robust optimization, Generalized hose uncertainty in single-commodity robust network design, Robust minimum cost flow problem under consistent flow constraints, Robust optimal discrete arc sizing for tree-shaped potential networks, Robust flows with adaptive mitigation, Robust transshipment problem under consistent flow constraints, On the robustness of potential-based flow networks, Robust two-stage combinatorial optimization problems under discrete demand uncertainties and consistent selection constraints, A comparison of different routing schemes for the robust network loading problem: polyhedral results and computation, Designing networks with resiliency to edge failures using two-stage robust optimization

Uses Software

• SNDlib
• ABACUS
• PORTA

Cites Work

• Unnamed Item
• Single-commodity robust network design problem: complexity, instances and heuristic solutions
• The convex hull of two core capacitated network design problems
• A theorem on flows in networks
• Routing of uncertain traffic demands
• Partitioning procedures for solving mixed-variables programming problems
• Minimum cost capacity installation for multicommodity network flows
• Robust solutions of uncertain linear programs
• On implementing the push-relabel method for the maximum flow problem
• Easy and difficult objective functions for max cut
• Robust discrete optimization and network flows
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• On capacitated network design cut-set polyhedra
• The robust network loading problem with dynamic routing
• Embedding {0, ½}-Cuts in a Branch-and-Cut Framework: A Computational Study
• On cut-based inequalities for capacitated network design polyhedra
• An Exact Algorithm for Robust Network Design
• Emergence of Scaling in Random Networks
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Models and Algorithms for Robust Network Design with Several Traffic Scenarios
• Maximal Flow Through a Network
• An Application of Generalized Linear Programming to Network Flows
• Provisioning virtual private networks under traffic uncertainty
• Hardness of robust network design
• A new approach to the maximum-flow problem
• Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria
• Optimum Synthesis of a Network with Non-Simultaneous Multicommodity Flow Requirements
• Designing Least-Cost Nonblocking Broadband Networks
• An exact algorithm for the min-cost network containment problem
• The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization
• Modeling and Solving the Two-Facility Capacitated Network Loading Problem
• Network Design Using Cut Inequalities
• Reducibility among Combinatorial Problems
• Robust solutions for network design under transportation cost and demand uncertainty
• k-Partition-based facets of the network design problem
• Synthesis of a Communication Network
• Capacitated Network Design—Polyhedral Structure and Computation
• Integer Programming and Combinatorial Optimization