The Ring Star Problem: Polyhedral analysis and exact algorithm

DOI10.1002/net.10114zbMath1053.90021OpenAlexW2133241632MaRDI QIDQ4474293

Martine Labbé, Juan-José Salazar-González, Inmaculada Rodríguez-Martín, Gilbert Laporte

Publication date: 4 August 2004

Published in: Networks (Search for Journal in Brave)

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

zbMATH Keywords

branch and cut telecommunications median cycle

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Communication networks in operations research (90B18) Paths and cycles (05C38)

Related Items

The periodic vehicle routing problem with driver consistency, Survivability in hierarchical telecommunications networks, Optimal capacitated ring trees, Tight bounds from a path based formulation for the tree of hub location problem, The \(p\)-arborescence star problem: formulations and exact solution approaches, Models for a Steiner multi-ring network design problem with revenues, Exact algorithms for budgeted prize-collecting covering subgraph problems, MEALS: a multiobjective evolutionary algorithm with local search for solving the bi-objective ring star problem, The tree-star problem: a formulation and a branch-and-cut algorithm, The traveling purchaser problem, with multiple stacks and deliveries: a branch-and-cut approach, Single string planning problem arising in liner shipping industries: a heuristic approach, The bi-objective insular traveling salesman problem with maritime and ground transportation costs, A branch-and-cut algorithm for two-level survivable network design problems, Metaheuristics and cooperative approaches for the bi-objective ring star problem, A branch‐and‐cut algorithm for the ring spur assignment problem, Minimum‐weight subgraphs with unicyclic components and a lower‐bounded girth, Continuous maximal covering location problems with interconnected facilities, General network design: a unified view of combined location and network design problems, A heuristic procedure for the capacitated \(m\)-ring-star problem, Pricing strategies for capacitated ring-star problems based on dynamic programming algorithms, Exact and heuristic approaches for the cycle hub location problem, Branch‐and‐cut algorithms for the ‐arborescence star problem, Configuration‐based approach for topological problems in the design of wireless sensor networks, New pricing strategies and an effective exact solution framework for profit-oriented ring arborescence problems, Column Generation Algorithms for the Capacitated m-Ring-Star Problem, A survivable variant of the ring star problem, An integer linear programming based heuristic for the capacitated \(m\)-ring-star problem, Multiperiod location-routing with decoupled time scales, The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm, The caterpillar-packing polytope, An exact algorithm for solving the ring star problem, The caterpillar-packing polytope, Multiple depot ring star problem: a polyhedral study and an exact algorithm, A decomposition algorithm for the ring spur assignment problem, An integer programming-based local search for the covering salesman problem, Unnamed Item, Unnamed Item, The single-vehicle two-echelon one-commodity pickup and delivery problem, The capacitated directed cycle hub location and routing problem under congestion, A new formulation and an exact approach for the many-to-many hub location-routing problem, Towards optimizing the deployment of optical access networks, A Generic Branch-and-Cut Algorithm for Multiobjective Optimization Problems: Application to the Multilabel Traveling Salesman Problem, Algorithms for the metric ring star problem with fixed edge-cost ratio, Securely Connected Facility Location in Metric Graphs, A parallel variable neighborhood search for solving covering salesman problem, A covering traveling salesman problem with profit in the last mile delivery, The capacitated m two node survivable star problem, Upper and lower bounding procedures for the minimum caterpillar spanning problem, The tree of hubs location problem, A tailored Benders decomposition approach for last-mile delivery with autonomous robots, The attractive traveling salesman problem, Heuristic algorithms for the multi-depot ring-star problem, Facet-inducing inequalities with acyclic supports for the caterpillar-packing polytope, Spatial coverage in routing and path planning problems, An efficient evolutionary algorithm for the ring star problem

Uses Software

Cites Work