Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut

DOI10.1007/s10107-005-0576-5zbMath1085.90009OpenAlexW2089135840MaRDI QIDQ2583145

Pierre Pesneau, S. Thomas McCormick, Ali Ridha Mahjoub, Bernard Fortz

Publication date: 13 January 2006

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

Full work available at URL: https://doi.org/10.1007/s10107-005-0576-5

zbMATH Keywords

branch-and-cut algorithmnetwork design problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items

Survivability in hierarchical telecommunications networks, Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation, Hierarchical survivable network design problems, A branch-and-cut algorithm for two-level survivable network design problems, The \(k\) edge-disjoint 3-hop-constrained paths polytope, A Flexible, Natural Formulation for the Network Design Problem with Vulnerability Constraints, Stochastic survivable network design problems: theory and practice, On the \(k\) edge-disjoint 2-hop-constrained paths polytope, A decomposition algorithm for the ring spur assignment problem, On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem, Critical extreme points of the 2-edge connected spanning subgraph polytope, Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut, Rapid prototyping of optimization algorithms using COIN-OR: a case study involving the cutting-stock problem

Uses Software

• SYMPHONY

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Separating from the dominant of the spanning tree polytope
• Two-edge connected spanning subgraphs and polyhedra
• Two-connected networks with rings of bounded cardinality
• Polyhedral results for two-connected networks with bounded rings
• On two-connected subgraph polytopes
• \(k\)-edge connected polyhedra on series-parallel graphs
• Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut
• Separation of Partition Inequalities
• Very Simple Methods for All Pairs Network Flow Analysis
• Optimal attack and reinforcement of a network
• A new approach to the maximum-flow problem
• Multi-Terminal Network Flows
• The k-Edge-Connected Spanning Subgraph Polyhedron
• Solving the Two-Connected Network with Bounded Meshes Problem
• The complexity of finding maximum disjoint paths with length constraints
• Design of Survivable Networks: A survey