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

A ring star in a graph is a subgraph that can be decomposed into a cycle (or ring) and a set of edges with exactly one vertex in the cycle. In the minimum ring-star problem (mrsp) the cost of a ring star is given by the sum of the costs of its edges, which vary, depending on whether the edge is part of the ring or not. The goal is to find a ring-star spanning subgraph minimizing the sum of all ring and assignment costs. In this paper we show that the mrsp can be reduced to a minimum (constrained) Steiner arborescence problem on a layered graph. This reduction is used to introduce a new integer programming formulation for the mrsp. We prove that the dual bound generated by the linear relaxation of this formulation always dominates the one provided by an early model from the literature. Based on our new formulation, we developed a branch-and-cut algorithm for the mrsp. On the primal side, we devised a grasp heuristic to generate good upper bounds for the problem. Computational tests with these algorithms were conducted on a benchmark of public domain. In these experiments both our exact and heuristics algorithms had excellent performances, noticeably in dealing with instances whose optimal solution has few vertices in the ring. In addition, we also investigate the minimum spanning caterpillar problem (mscp) which has the same input as the mrsp and admits feasible solutions that can be viewed as ring stars with paths in the place of rings. We present an easy reduction of the mscp to the mrsp, which makes it possible to solve to optimality instances of the former problem too. Experiments carried out with the mscp revealed that our branch-and-cut algorithm is capable to solve to optimality instances with up to 200 vertices in reasonable time.