Complexity of column generation in network design with path-based survivability mechanisms

DOI10.1002/net.20484zbMath1241.90091OpenAlexW1971589960MaRDI QIDQ2892152

Sebastian Orlowski, Michał Pióro

Publication date: 18 June 2012

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20484

zbMATH Keywords

computational complexitysurvivable network designmixed-integer programingcolumn/path generation

Mathematics Subject Classification ID

Mixed integer programming (90C11)

Related Items

Survivable network design with shared-protection routing ⋮ Energy-aware survivable networks ⋮ A robust optimization model for affine/quadratic flow thinning: A traffic protection mechanism for networks with variable link capacity ⋮ An efficient approach to optimization of semi‐stable routing in multicommodity flow networks ⋮ Path generation for affine flow thinning ⋮ Optimizing Flow Thinning Protection in Multicommodity Networks with Variable Link Capacity ⋮ Resilient capacity-aware routing ⋮ Complexity of a classical flow restoration problem

Uses Software

• CPLEX

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The directed subgraph homeomorphism problem
• The ellipsoid method and its consequences in combinatorial optimization
• Assigning spare capacities in mesh survivable networks
• Network synthesis under survivability constraints
• Approximation algorithms and hardness results for labeled connectivity problems
• On the complexity of resilient network design
• Disjoint paths in a network
• On Linear Characterizations of Combinatorial Optimization Problems
• Shortest Path Problems with Resource Constraints