Two‐node‐connected star problem

• Published date: 01 March 2018
• Author: Franco Robledo,Pablo Romero,Rodrigo Recoba,Omar Viera
• DOI: http://doi.org/10.1111/itor.12362
• Date: 01 March 2018

Intl. Trans. in Op. Res. 25 (2018) 523–543

DOI: 10.1111/itor.12362

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Two-node-connected star problem

Rodrigo Recoba, Franco Robledo, Pablo Romero and Omar Viera

Facultad de Ingenier´

ıa, Departamento de Investigaci´

on Operativa, Instituto de Computaci´

on, Universidad de la Rep´

ublica,

Julio Herrera y Reissig 565, Montevideo, Uruguay

E-mail: recoba@fing.edu.uy [Recoba]; frobledo@fing.edu.uy [Robledo];promero@fing.edu.uy [Romero];

viera@fing.edu.uy [Viera]

Received 28 September 2015; receivedin revised form 19 September 2016; accepted 20 September 2016

Abstract

In this study, a two-node-connected star problem (2NCSP) is introduced. We are given a simple graph

and internal and external costs for each link of the graph. The goal is to find the minimum-cost spanning

subgraph, where the core is two-node-connected and the remaining external nodes are connected to the

core. First, we show that the 2NCSP belongs to the class of NP-hard computational problems. Therefore,

a greedy randomized adaptive search procedure (GRASP) heuristic is developed, enriched with a variable

neighborhood descent (VND). The neighborhood structures include exact integer linear programmingmodels

to find the best paths and two-node-connected replacements, as well as a shaking operation in order to

prevent being trapped in a local minima. The ring star problem(RSP) represents a relevant model in network

optimization, where the core is a ring instead of an arbitrary two-node-connected graph. We contrast our

GRASP/VND methodology with a previous referencework on the RSP in order to highlight the effectiveness

of our heuristic. The heuristic is competitive, and the best results produced for several instances so far are

under study. In this study, a discussion of the results and trends for future work are provided.

Keywords:two-node-connected star problem; ring star problem; GRASP; computational complexity

1. Introduction

Traditionally, availability has been a major cause of concern in telephonic services. A tree provides

availability and it can be efficiently designed (Kruskal, 1956), but it is not robust under single point

failures. Terminal nodes must be connected by one or more paths, while intermediate Steiner nodes

provide support in the infrastructure and path diversity. Computational complexity theory shows

that it is hard to find a minimum-cost Steiner tree (Karp, 1972). Robledo Amoza (2005) provides

applications on wide area network design in his thesis.

Survivability aspects should be considered when the system is exposed to potential failures, such

as in fiber optic communication. See the authoritative book by Stoer (1993) for classical results

C

2016 The Authors.

International Transactionsin Operational Research C

2016 International Federation of OperationalResearch Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

524 R. Recoba et al. / Intl. Trans. in Op. Res. 25 (2018) 523–543

Fig. 1. Example where Monma graph is cheaperthan a Hamiltonian tour.

in survivable network design, and Kerivin and Mahjoub (2005) for a related survey. A network

is two-node-connected, if it is still connected under an arbitrary single-node deletion. For cost-

effective reasons, network design considers two-node-connected topologies to provide robustness

under single point of failures. A foundational result is provided by Monma et al. (1990), who study

the Minimum-Weight Two-Connected Spanning Problem (MW2CSP), where the goal is to find the

minimum-cost two-connected spanning subgraph, given a weighted metric graph. They formally

prove that there are better solutions than rings in specific scenarios. Nevertheless, the cost of the

best ring cannot exceed the best solution by more than one-third. Consider Fig. 1 as a toy example.

In a complete graph K5with five nodes, assume the unit costs in the links shown in Fig. 1, but in

other links the unit cost is 10. All links with unit cost jointly build a two-node-connected graph

M, called Monma graph, and has an unit cost c(M)=6. However, every ring must use at least

one expensive link and a minimum-cost ring Cof unit cost c(C)=14. In this example, observe

that c(C)/c(M)>4/3, and the costs do not meet the triangle inequality (i.e., the metric graph

hypothesis does not hold).

The ring star problem (RSP), is introduced by Labb´

e et al. (1999), is based on fiber optic network

design. It is a generalization of the Hamilton tour, where some terminals may be directly connected

to the ring (the term star stands for those leaf nodes connected to the ring). Formally, we are given

agraphG=(V,E∪A),whereErepresents undirected links with connection costs {ce}e∈Eand

Arepresents (directed) arcs with assignment costs {de}e∈A. There is a distinguished node v1∈V,

called depot. The goal is to design a spanning subgraph G=(V,C∪T),C⊆Ebeing a cycle that

includes the depot v1,andT⊆Adirectly connected by arcs outgoing from the cycle, such that the

global cost c(G)=e∈Cce+e∈Tdeis minimized.

The RSP belongs to the NP-hard class and exact solutions are available for special in-

stances (Kedad-Sidhoum and Nguyen, 2010). It has a wide range of applications, including com-

munication networks, logistics, location of garbage containers, and transportation.For that reason,

several prior works address the RSP using both exact and approximation methods. Since the lit-

erature in RSP is vast, here we will cite the closest works useful for the understanding of this

paper.

In 2004, Labb´

e et al., for the first time, designed an exact branch-and-cut algorithm to solve

TSPLIB instances with even 200 nodes (Labb´

e et al., 2004). As far as we know, this is the first exact

method available in the literature. The authors include three classes of TSPLIB instances for their

study. In most instances, they provide the optimal solution. In our experimental analysis, we will

provide details of the first problemclass (Class I), which we will use as a reference. Dias et al. (2006)

present a greedy randomized adaptivesearch procedure (GRASP) metaheuristic to address the RSP

(Naji-Azimi et al., 2012). Randomization is added during the local search phase, where the best

C

2016 The Authors.

International Transactionsin Operational Research C

2016 International Federation of OperationalResearch Societies