The Capacitated m Two Node Survivable Star Problem

Abstract

The  problem  addressed  in  this  paper  attempts  to  efficiently  solve  a  network  design
with redundant connections, often used by telephone operators and internet services. This network
connects customers with one master node and sets some rules that shape its construction, such as
number of customers, number of components and types of links, in order to meet operational needs
and technical constraints. We propose a combinatorial optimization problem called CmTNSSP (Ca-
pacitated m Two-Node-Survivable Star Problem), a relaxation of CmRSP (Capacitated m Ring Star
Problem). In this variant of CmRSP the rings are not constrained to be cycles; instead, they can be
two node connected components. The contributions of this paper are (a) introduction and definition
of a new problem (b) the specification of a mathematical programming model of the problem to be
treated, and (c) the approximate resolution thereof through a GRASP metaheuristic, which alter-
nates local searches that obtain incrementally better solutions, and exact resolution local searches
based on mathematical programming models, particularly Integer Linear Programming ones. Com-
putational  results  obtained  by  developed  algorithms  show  robustness  and  competitiveness  when compared to results of the literature relative to benchmark instances.  Likewise, the experiments
show the relevance of considering the specific variant of the problem studied in this work.

Keywords: Topological Network Design, Survivability, Greedy Randomized Adaptive Search Pro-
cedure (GRASP), Variable Neighborhood Search (VNS), Metaheuristics.