A branch-and-cut algorithm for the ring spur assignment problem

DOI10.1002/NET.21495MaRDI QIDQ5326781zbMATH OpenOpenAlexFDO

Authors Paula Carroll, Bernard Fortz, Martine Labbé, Seán McGarraghy

Publication date 6 August 2013

Published in Networks (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10197/9428

zbMATH Keywords

branch-and-cut algorithmIP formulationNP-hardness proofsurvivable network design

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Communication networks in operations research (90B18) Integer programming (90C10)

Recommendations

• The ring spur assignment problem: new formulation, valid inequalities and a branch-and-cut approach
• Improved formulations for the ring spur assignment problem
• A decomposition algorithm for the ring spur assignment problem
• The Capacitated m-Ring-Star Problem
• The Ring Star Problem: Polyhedral analysis and exact algorithm

Cites work

• A branch-and-cut-and-price approach for the capacitated \(m\)-ring-star problem
• A heuristic procedure for the capacitated m-ring-star problem
• A simple min-cut algorithm
• Combinatorial optimization. Theory and algorithms.
• Generalized Subtour Elimination Constraints and Connectivity Constraints
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems
• Improved formulations for the ring spur assignment problem
• On the asymmetric representatives formulation for the vertex coloring problem
• Polyhedral and Computational Investigations for Designing Communication Networks with High Survivability Requirements
• Polyhedral results for two-connected networks with bounded rings
• Solving the Two-Connected Network with Bounded Meshes Problem
• SONET/SDH ring assignment with capacity constraints
• The Capacitated m-Ring-Star Problem
• The Ring Star Problem: Polyhedral analysis and exact algorithm
• The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut
• Two-connected networks with rings of bounded cardinality

Cited in

(7)

• The ring spur assignment problem: new formulation, valid inequalities and a branch-and-cut approach
• A branch-and-price algorithm for the ring-tree facility location problem
• Models for a Steiner multi-ring network design problem with revenues
• Improved formulations for the ring spur assignment problem
• The Ring Star Problem: Polyhedral analysis and exact algorithm
• A decomposition algorithm for the ring spur assignment problem
• Min–max optimization of node‐targeted attacks in service networks

Describes a project that uses

Uses Software

• SONET

This page was built for publication: A branch-and-cut algorithm for the ring spur assignment problem

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