The Ring Star Problem: Polyhedral analysis and exact algorithm

DOI10.1002/NET.10114MaRDI QIDQ4474293zbMATH OpenOpenAlexFDO

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

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

telecommunicationsbranch and cutmedian cycle

Mathematics Subject Classification ID

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

Recommendations

• An exact algorithm for solving the ring star problem
• Multiple depot ring star problem: a polyhedral study and an exact algorithm
• The Capacitated m-Ring-Star Problem
• The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm
• A branch-and-cut algorithm for the ring spur assignment problem

Cites work

• scientific article; zbMATH DE number 1803762 (Why is no real title available?)
• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• Location-Allocation Problems
• On the \(p\)-median polytope
• On the facial structure of set packing polyhedra
• Optimizing a ring-based private line telecommunication network using tabu search
• TSPLIB—A Traveling Salesman Problem Library
• The Circuit Polytope: Facets
• The Covering Tour Problem
• The median tour and maximal covering tour problems: Formulations and heuristics
• Variable neighborhood tabu search and its application to the median cycle problem.

Cited in

(68)

• A generic branch-and-cut algorithm for multiobjective optimization problems: application to the multilabel traveling salesman problem
• Column Generation Algorithms for the Capacitated m-Ring-Star Problem
• A branch-and-cut for the Non-Disjointm-Ring-Star Problem
• Metaheuristics and cooperative approaches for the bi-objective ring star problem
• Branch‐and‐cut algorithms for the ‐arborescence star problem
• Facet-inducing inequalities with acyclic supports for the caterpillar-packing polytope
• The single-vehicle two-echelon one-commodity pickup and delivery problem
• A unifying framework for selective routing problems
• Continuous maximal covering location problems with interconnected facilities
• An exact algorithm for solving the ring star problem
• The tree of hubs location problem
• Survivability in hierarchical telecommunications networks
• Optimal capacitated ring trees
• The caterpillar-packing polytope
• A heuristic procedure for the capacitated m-ring-star problem
• Multiperiod location-routing with decoupled time scales
• Models for a Steiner multi-ring network design problem with revenues
• New pricing strategies and an effective exact solution framework for profit-oriented ring arborescence problems
• An integer linear programming based heuristic for the capacitated \(m\)-ring-star problem
• A branch-and-cut algorithm for the plant-cycle location problem
• Tight bounds from a path based formulation for the tree of hub location problem
• General network design: a unified view of combined location and network design problems
• Securely connected facility location in metric graphs
• Corrigendum to ``An efficient evolutionary algorithm for the ring star problem
• The caterpillar-packing polytope
• A decomposition algorithm for the ring spur assignment problem
• Exact algorithms for budgeted prize-collecting covering subgraph problems
• The bi-objective insular traveling salesman problem with maritime and ground transportation costs
• The capacitated directed cycle hub location and routing problem under congestion
• The periodic vehicle routing problem with driver consistency
• MEALS: a multiobjective evolutionary algorithm with local search for solving the bi-objective ring star problem
• The ring tree facility location problem
• The tree-star problem: a formulation and a branch-and-cut algorithm
• Heuristic algorithms for the multi-depot ring-star problem
• An Efficient Heuristic for the Ring Star Problem
• 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 ring-star problem: a new integer programming formulation and a branch-and-cut algorithm
• Steiner networks with unicyclic connected components
• A branch-and-price algorithm for the ring-tree facility location problem
• A survivable variant of the ring star problem
• Minimum-weight subgraphs with unicyclic components and a lower-bounded girth
• Algorithms for the metric ring star problem with fixed edge-cost ratio
• A branch-and-cut algorithm for two-level survivable network design problems
• The attractive traveling salesman problem
• The capacitated m two node survivable star problem
• Formulations and algorithms for the simple cycle problem
• Pricing strategies for capacitated ring-star problems based on dynamic programming algorithms
• A branch-and-cut algorithm for the ring spur assignment problem
• Exact and heuristic approaches for the cycle hub location problem
• A parallel variable neighborhood search for solving covering salesman problem
• A covering traveling salesman problem with profit in the last mile delivery
• Upper and lower bounding procedures for the minimum caterpillar spanning problem
• Survivable two-fault-tolerant ring star problem
• A general cut-generating strategy for the caterpillar-packing polytope
• Towards optimizing the deployment of optical access networks
• Configuration‐based approach for topological problems in the design of wireless sensor networks
• The p-arborescence star problem: formulations and exact solution approaches
• A tailored Benders decomposition approach for last-mile delivery with autonomous robots
• Networks with unicyclic connected components and without short cycles
• Multiple depot ring star problem: a polyhedral study and an exact algorithm
• A new formulation and an exact approach for the many-to-many hub location-routing problem
• Spatial coverage in routing and path planning problems
• A variable neighborhood search and its application to a ring star problem generalization
• An integer programming-based local search for the covering salesman problem
• A resilient variant of the ring star problem
• Modeling and solving the two-level generalized median tour problem
• An efficient evolutionary algorithm for the ring star problem

Describes a project that uses

Uses Software

• ABACUS
• TSPLIB

This page was built for publication: The Ring Star Problem: Polyhedral analysis and exact algorithm

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