The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm

DOI10.1016/J.DAM.2011.01.015MaRDI QIDQ643033zbMATH OpenOpenAlexFDO

Authors L. Simonetti, Y. Frota, Cid Carvalho de Souza

Publication date 27 October 2011

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2011.01.015

zbMATH Keywords

integer programmingbranch-and-cut algorithmcaterpillar treesring-star problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Integer programming (90C10)

Recommendations

• An exact algorithm for solving the ring star problem
• An integer linear programming formulation and branch-and-cut algorithm for the capacitated \(m\)-ring-star problem
• The Capacitated m-Ring-Star Problem
• Algorithms for the ring star problem
• The Ring Star Problem: Polyhedral analysis and exact algorithm

Cites work

• scientific article; zbMATH DE number 1375584 (Why is no real title available?)
• scientific article; zbMATH DE number 2064406 (Why is no real title available?)
• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• A dual ascent approach for steiner tree problems on a directed graph
• Algorithms and Computation
• Optimizing a ring-based private line telecommunication network using tabu search
• Solving Steiner tree problems in graphs to optimality
• TSPLIB—A Traveling Salesman Problem Library
• The Capacitated m-Ring-Star Problem
• The Circuit Polytope: Facets
• The Ring Star Problem: Polyhedral analysis and exact algorithm

Cited in

(17)

• A branch-and-cut for the Non-Disjointm-Ring-Star Problem
• The Ring Star Problem: Polyhedral analysis and exact algorithm
• An exact algorithm for solving the ring star problem
• A heuristic procedure for the capacitated \(m\)-ring-star problem
• Corrigendum to ``An efficient evolutionary algorithm for the ring star problem
• The capacitated directed cycle hub location and routing problem under congestion
• 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
• A survivable variant of the ring star problem
• Algorithms for the metric ring star problem with fixed edge-cost ratio
• 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
• A branch-and-cut-and-price approach for the capacitated \(m\)-ring-star problem
• Spatial coverage in routing and path planning problems
• Algorithms for the ring star problem
• An efficient evolutionary algorithm for the ring star problem

Describes a project that uses

Uses Software

• SteinLib
• TSPLIB

This page was built for publication: The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm

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