A new branch-and-cut approach for the generalized regenerator location problem

Abstract

In optical networks, a signal can only travel a maximum distance (called optical reach) before its quality deteriorates, needing regenerations by installing regenerators at network nodes. Such an optical reach is an important property of a transmission system, which is a necessary ingredient for enabling optical bypass and thus significantly affects optical network design. In this paper, we study the generalized regenerator location problem (GRLP) where we are given a set S of candidate locations for regenerator placement and a set T of network nodes required to communicate with each other. The GRLP is to find a minimal number of network nodes for regenerator placement, such that for each node pair in T, there exists a path of which no subpath without internal regenerators has a length greater than the given optical reach. Starting with an existing set covering formulation of the problem, we first study the facial structure of the associated polytope. Making use of these polyhedral results, we then present a new branch-and-cut solution approach to solve the GRLP to optimality. With benchmark instances and newly generated instances, we finally evaluate our approach and compare it with an existing method. Computational results demonstrate efficacy of our approach.

1 Introduction

As telecommunication networks face increasing bandwidth demand and diminishing fiber availability, telecommunication service providers are moving towards a crucial milestone in network evolution: the optical network (Colombo and Trubian 2014). Based on the emergence of the optical layer in transport networks, an optical network is able to provide higher capacity and reduce costs for new applications such as the internet, video and multimedia interaction, and advanced digital services. An optical network is composed of fiber-optic cables that are the primary communication medium for converting data and transmitting data as light pulses between sender and receiver nodes. In the last decade, optical network design has attracted extensive attention of research works, including research on network architectures, control and management, protection and survivability (Borne et al. 2006; Chen et al. 2010). Regarding optical network design, the geographical extent of optical signal transmission is an important issue. Optical signals always undergo degradation as they are transmitted along a fiber. That is, an optical signal can travel a maximum distance before its quality degrades to a level that requires the signal to be regenerated, where regeneration occurs in the electronic domain. In the field of telecommunication, such a maximum distance is also referred as the “optical reach”, ranging from 500 to 2000 miles (Simmons 2006). Regeneration cleans up or regenerates the optical signal, by reamplifying, reshaping, and retiming it, which is referred to as the “3R” regeneration (Simmons 2008).

Typically, such regenerators are very expensive (e.g., $160K) and the regenerator cost is per wavelength (Mertzios et al. 2012). Therefore, it is worth minimizing the total number of regenerators in optical networks. This leads to the regenerator location problem (RLP) that deals with a constraint on the geographical extent of signal transmission in optical network design. The RLP can be defined as follows: Given an optical network and a maximum distance $d_{max}$ (optical reach) that a signal can travel, determine the minimum number of network nodes for regenerator placement, such that for each node pair there exists a path of which no subpath, without regenerators at internal nodes, has a length greater than the distance limit $d_{max}$ (Sen et al. 2008; Yetginer and Karasan 2003; Gouveia et al. 2003). In the computer science literature, the RLP is also referred to as regenerator placement problem (RPP) (Mertzios et al. 2012).

Due to certain practical considerations, it may not be possible to install regenerators at certain nodes of the network. Furthermore, from a maintenance perspective, it may be beneficial to limit the number of locations where regeneration equipment is deployed (Simmons 2008). This additional design constraint leads to a more general regenerator location problem, the generalized regenerator location problem (GRLP), first introduced by Chen et al. (2015). In comparison with the RLP, the significant features of the GRLP are that not all network nodes can be used for regenerator placement and not all node pairs require communicating with each other. In other words, we have a subset of candidate network nodes for regenerator placement and a subset of network nodes that must communicate with each other. The GRLP can be defined as follows:

Definition 1

GRLP: Suppose we are given an optical network, a set S of candidate locations for regenerator placement (s-nodes), a set T of nodes (t-nodes) requiring to communicate with each other, and an optical reach $d_{max}$ for signal travel. The GRLP is to determine a minimal number of network nodes from S for regenerator placement, such that for each node pair in T, there exists a path connecting them of which no subpath without internal regenerators has a length greater than the distance limit $d_{max}$.

Figure 1 gives an example of the GRLP. In this example, a signal can travel a maximum distance of 210. We can place regenerators at nodes 3, 4 or 5. Nodes 1, 2, 6, and 7 must communicate with each other. It can be easily verified that the optimal solution is to place one regenerator at node 3. This regenerator placement ensures the communication between nodes 1, 2, 6, and 7.

Fig. 1

Example of the GRLP

In this paper, we focus on the GRLP that turns out to be significantly more challenging than the RLP (Chen et al. 2015). As an extension of the RLP, Chen et al. (2015) introduced the GRLP and designed solution approaches for it. Since the RLP is a special case of the GRLP and known to be ${\mathcal {NP}}$-hard (Sen et al. 2008; Chen et al. 2010), the GRLP is also ${\mathcal {NP}}$-hard. For related works on the RLP, please refer to literature review in Li and Aneja (2017), Gendron et al. (2014), and Buchanan et al. (2015). We give here a brief review of related work for the GRLP.

In the literature, the only works on the GRLP include Chen et al. (2015) and our preliminary study (Li and Aneja 2014). Since the GRLP is ${\mathcal {NP}}$-hard, Chen et al. (2015) first proposed two construction heuristics and a local search procedure. The authors then used the connections between the node-weighted directed Steiner forest problem and the GRLP to present a natural formulation and two extended formulations for the GRLP. The authors compared the strength of three formulations and developed a branch-and-cut (B&C) method using a formulation on node variables. Computational results on 300 instances showed that this exact approach could easily solve instances with up to 200 nodes to optimality, and the two heuristics also reached high-quality solutions to large scale instances.

In this paper, we study the associated polyhedral structure, starting with an existing set covering formulation, develop a new efficient branch-and-cut approach, and carry out a series of computational experiments to evaluate the proposed approach. We first study the polyhedral structure of the polytope of the convex hull of all feasible solutions. We present necessary and sufficient conditions for a set-covering inequality to be a facet-defining inequality (FDI) and discuss a method of lifting a non-facet-defining inequality to one or a set of stronger inequalities. We further develop necessary and sufficient conditions for such a “lifted inequality” to be an FDI. These facet results are extensions of our recent work for the RLP (Li and Aneja 2017). Following the facet results, we then develop a new B&C approach for solving the GRLP to optimality. The new B&C approach includes preprocessing and efficient separation methods. We finally evaluate our proposed approach using 300 benchmark instances from the literature and 90 newly generated large-scale instances. Computational results in comparison with other alternative method indicate that our proposed approach is efficient and effective exact algorithm for the GRLP. Our approach extends our ability to solve large instances of the GRLP.

The remainder of this paper is organized as follows. In Sect. 2, we discuss the set covering formulation for the GRLP. In Sect. 3, we study the facial structure of the above mentioned polytope. In Sect. 4, we highlight our new B&C solution approach. In Sect. 5, we present heuristics for generating feasible solutions. In Sect. 6, we report computational results of the proposed method. We finally conclude this paper in Sect. 7.

2 Mathematical formulation of the GRLP

In this section, we introduce the existing set covering formulation for the GRLP. With this formulation, we then study the facial structure of the polytope in Sect. 3, and develop a new branch-and-cut approach to optimally solve the GRLP in Sect. 4.

2.1 Preliminaries

The GRLP is defined over an optical network by an undirected graph $O=(N,F)$, where $N=\{1, 2, \ldots , n\}$ denotes the set of n nodes, and F is the set of all available edges. With each edge $\{i,j\}\in F$, we associate a distance $d_{ij}$. Let $S\subset N$ be the set of candidate locations where regenerators can be deployed, and $T\subset N$ be the set of nodes that must communicate with each other. A maximum distance limit of $d_{max}$ (called the optical reach) defines how far an optical signal can travel before its quality deteriorates and regeneration is needed. Given graph $O=(N,F)$, set S and set T, we can formally define the GRLP as follows:

Determine a minimum cardinality subset $L\subset S$ of regenerator equipped nodes such that for every node pair in T, there exists a path with no sub-path of distance greater than $d_{max}$ without regenerators placed on its internal nodes (internal nodes do not include the end-nodes of the sub-path).

As in Sen et al. (2008), Chen et al. (2010, (2015) and Li and Aneja (2017), we define the formulation on a transformed graph, called the reachability graph $G=(N, E)$ that is derived from the optical network O. We create the reachability graph G as follows. The “all-pairs shortest path algorithm” is first applied to graph O. For every pair of nodes i and j in N, an edge $\{i,j\}$ is then kept in E only if the shortest distance $w_{ij}$ between nodes i and j in O is no more than $d_{max}$. That is, we have $E=\{\{i,j\}\in N^2: w_{ij}\le d_{max}\}$. If every pair of nodes in T is connected by an edge in E, then clearly no regenerators are required. Otherwise, every pair of not-connected nodes require at least one regenerator to communicate with each other.

With such a transformed graph G, the GRLP is to determine a minimum cardinality subset $L\subset S$ of regenerator equipped nodes such that for every not-connected node pair in T, there exists a path in G such that all its internal nodes are regenerators equipped. Hereafter, we denote each not-directly-connected (NDC) node pair in T as $\{i, j\}$. Let $\Pi$ be the set of all NDC node pairs; i.e., $\Pi =\{\{i,j\}: i,j\in T, \{i,j\}\notin E\}$.

We refer to nodes in S as s-nodes, and nodes in T as t-nodes. In the reachability graph, we call any maximally connected component consisting of only s-nodes as an S-component (Chen et al. 2015). Without loss of generality, we can assume that the node set N has the following property: $N=S\cup T, S\cap T\ne \emptyset , S, T\ne \emptyset$ (for proof, see Chen et al. 2015).

Let $n_s$ be the number of S-components in the reachability graph G and $\Lambda _i$ be the ith S-component. Let $\Lambda$ be the set of all S-components; i.e., $\Lambda =\{\Lambda _i: i=1, 2, \ldots , n_s\}$. If a node j is adjacent to at least one s-node in $\Lambda _i$, then we define $\Lambda _i(j)$ which is to equal 1, and 0, otherwise. Define ${\mathcal {N}}(i, j)=\{k: \Lambda _k(i)= \Lambda _k(j)=1, k=1, 2, \ldots , n_s\}$. For each s-node, define $N(s)=\{i: i\in T, \{i, s\}\in E\}$.

2.1.1 New procedure for GRLP feasibility checking

Since our proposed approach makes repeated calls for checking of feasibility of reduced graphs, it is important that this task is done as efficiently as possible. Chen et al. (2015) present a method that checks the feasibility of a GRLP instance in $O(|T|^2\cdot |S|)$ time. Here we propose a more efficient checking approach that can be done in $O(|T|^2 + |N| + |E|)$ time. For t-nodes, define a $|T|\times |T|$ symmetric matrix Z of connectivity. If node i can be connected to node j by some regenerator placement in a GRLP instance, $z_{ij}=1$, and 0, otherwise. We initialize all non-diagonal entries to zeros, and set $z_{ij}=1$ if there is an edge between nodes i and j in graph G. Recall that determining the connected components of an undirected graph can be done in $O(|N| + |E|)$ time (Reingold et al. 1977). Suppose we implement this method to find S-components in graph G. Starting with one s-node, this method employs the depth-first search technique to determine connected components of s-nodes. While exploring neighboring s-nodes of one component, we also record t-nodes connected to this S-component, and use these t-nodes to update z values. Suppose there are three nodes, $t_1$, $t_2$, and $t_3$ connected to one S-component. Obviously, these three t-nodes can communicate with each other. That is, we set $z_{t_1 t_2}=z_{t_2 t_1}=z_{t_1 t_3}=z_{t_3 t_1}=z_{t_2 t_3}=z_{t_3 t_2}=1$. If at the end of the approach, all non-diagonal entries of Z are all 1 s, then the GRLP instance is feasible. Otherwise, it is infeasible. Therefore, the feasibility checking of a GRLP instance can be done in $O(|N| + |E|)$ time plus $O(|T|^2)$ time for examining matrix Z.

A similar procedure is also implemented to validate a facet defining inequality and the feasibility of an integer solution in Sect. 4.

2.1.2 Disconnecting set of nodes (DSN)

Li and Aneja (2017), Rahman et al. (2015), and Rahman (2012) used the idea of a DSN to present the formulation for the RLP. Here we use the similar idea to give the formulation for the GRLP.

For any subset $A\subset N$, define G(A) to be the subgraph of G induced by the node set A. That is, $G(A)=(A,E(A))$, where E(A) contains only edges of E with both ends in A.

Let $D\subset S$ be defined as a “Disconnecting Set of Nodes”, if $G(N\backslash D)$ “disconnects” at least one pair of not directly connected t-nodes in T. That is, there exists at least one pair of nodes $\{i, j\}\in T$, $\{i,j\}\notin E$ such that there is no S-path (path using only S-nodes) between i and j in $G(N\backslash D)$. In the context of the GRLP, we refer to DSN as T-DSN since it disconnects t-node pairs. Let D be a minimal T-DSN if no proper subset of D is a T-DSN. Figure 2 gives an example of T-DSNs. In this instance, we have $S=\{1, 2, 3, 4, 5\}$ and $T=\{6, 7, 8, 9\}$. Set $\{1, 2, 3\}$ and $\{1, 2\}$ are both T-DSNs, but not minimal T-DSNs.

Fig. 2

Example of T-DSNs

2.2 Set covering formulation

Let $\Omega$ be the set of all minimal T-DSNs. With each node $i\in S$, we associate a binary variable $x_{i}$ that equals 1 if node i is used for regenerator placement, and 0, otherwise. We introduce the set covering formulation (SCF) for the GRLP, which was first proposed by Chen et al. (2015).

$$\begin{aligned}&(\mathbf{SCF} )\quad \min \quad Z(x)=\sum _{i\in S}x_{i} \end{aligned}$$

(1)

$$\begin{aligned}&\text {subject to } \sum _{i\in D} x_{i}\ge 1\;\; \forall D\in \Omega , \end{aligned}$$

(2)

$$\begin{aligned}&\qquad x_{i}\in \{0,1\}\;\;\forall i\in S. \end{aligned}$$

(3)

Let polytope ${\mathcal {P}}$ be the convex hull of all feasible solutions to the GRLP. Clearly ${\mathcal {P}}$ is full dimensional because $\mathbf {1,}$ the |S|-vector of all 1’s and |S|-vectors $\{\mathbf {1-} e_i, i=1,\ldots , |S|\}$ are all affinely independent. Hereafter, we assume that any considered T-DSN D is minimal because a non-minimal T-DSN cannot correspond to an FDI. With formulation SCF, we present some facet results in the next section.

3 Facet results

In this section, we present facet results relating to the polyhedral structure of the convex hull of all feasible solutions to the GRLP. Note that these polyhedral results are extensions of our results for the RLP (Li and Aneja 2017). But we must point out that these facet results are specific for the GRLP and not the same as in our RLP paper. In Sect. 6, we will show that the extended polyhedral results significantly improve the computational performance of our proposed B&C approach in comparison to the results reported in the literature.

Consider a T-DSN D. For each node $i\in D$, consider $G(\{N\backslash D\}\cup \{i\})$, the induced graph of node set $\{N\backslash D\cup \{i\}\}$, generated by removing from graph G all nodes in $D\backslash \{i\}$ and all edges incident to nodes $j\in D\backslash \{i\}$. Define $\Phi _{i}$ to be the set of s-nodes in this induced graph, each one of which when removed makes the problem infeasible. Let $C=\bigcap _{i\in D}\Phi _{i}$. Note that the way we have defined the set C in this paper is different and much more difficult to compute than in our RLP paper (Li and Aneja 2017).

In the following, we present the main facet results without proofs. The detailed proofs are given in the “Appendix”.

Theorem 1

$\sum _{i\in D} x_{i}\ge 1$ is an FDI if and only if $C=\emptyset$.

The following results are used to lift a non-facet-defining inequality to one or a set of stronger inequalities. We further develop necessary and sufficient conditions for such a “lifted inequality” to be an FDI.

Lemma 1

If $C\ne \emptyset$ for a given T-DSN D, then $\sum _{i\in D}x_{i}+x_{j}\ge 2$ is a valid inequality for each $j\in C.$

Suppose $C\ne \emptyset$. Consider a node $j\in C.$ We want to identify necessary conditions under which the valid inequality $\sum _{i\in D}x_{i}+x_{j}\ge 2$ is facet defining. For each node $i\in S,$ consider $G(N\backslash \{i\})$, the subgraph obtained by removing from G node i and all the edges incident to node i. Define $\Psi _{i}$ to be the set of s-nodes in $G(N\backslash \{i\})$, each one of which when removed individually makes the problem infeasible.

Lemma 2

For a node $j\in C$, $\sum _{i\in D}x_{i}+x_{j}\ge 2$ to be an FDI, it is necessary that $|D\cap \Psi _{j}|\le 2.$

Lemma 3

For $\sum _{i\in D}x_{i}+x_{j}\ge 2$ to be an FDI, it is necessary that $|\{D\cup \{j\}\}\cap \Psi _{t}|\le 2,$ for all $t\in C\backslash \{j\}.$

The conditions of Lemmas 3 and 4 are sufficient for the inequality to be an FDI. This is given by the following theorem.

Theorem 2

For a $j\in C,~\sum _{i\in D}x_{i}+x_{j}\ge 2$ is an FDI if conditions of Lemmas 3 and 4 are satisfied.

If for some $j\in C,~\sum _{i\in D}x_{i}+x_{j}\ge 2$ is not an FDI, then it can be easily lifted, following the following two lemmas.

Lemma 4

Suppose $j\in C,$ and $|D\cap \Psi _{j}|=p\ge 3.$ Then $\sum _{i\in D}x_{i}+(p-1)x_{j}\ge p$ is a lifted valid inequality.

Lemma 5

Suppose $j\in C,$ and $|\{D\cup \{j\}\}\cap \Psi _{t}|=p\ge 3,$ for a $t\in C\backslash \{j\}.$ Then $\sum _{i\in D }x_{i}+x_j+(p-1)x_{t}\ge p$ is a lifted valid inequality.

4 New branch-and-cut approach

In this section, we present a new branch-and-cut (B&C) approach using the set covering formulation and facet results in Sect. 3. This new B&C approach includes preprocessing procedure, separation procedure, and pruning and speeding-up routines.

4.1 General framework and implementation

CPLEX 12.4 is selected as a framework for implementing the B&C approach (ILOG 2012). CPLEX is run with mixed integer programming (MIP) emphasis parameter set to “balance optimality and feasibility”. The default cut routines in CPLEX are terminated, and only our separation method is performed to identify valid inequalities. Other parameters are left at their default values, unless otherwise stated.

4.2 Preprocessing procedure

We present some results allowing us to develop a preprocessing procedure to set values of some binary variables and reduce problem size. For each NDC node pair $\{i, j\}$, let $Q_{ij}$ be the set of paths from i to j in G such that all the internal nodes are s-nodes.

Lemma 6

Consider one NDC node pair $\{i,j\}$. If there exists only one path in $Q_{ij}$, the internal nodes of this path must be equipped with regenerators.

The following result generalizes the fourth preprocessing step in Chen et al. (2015).

Lemma 7

Consider one S-component $\Lambda _i$ and one NDC node pair $\{s, t\}$ that is connected to only $\Lambda _i$. Find the cut-vertices of graph H spanned by nodes in $\Lambda _i\bigcup \{s, t\}$. Take one cut-vertex $i^*$ of graph H. If nodes s and t are separated by removing $i^*$ from H, then we must place a regenerator on node $i^*$ in the optimal solution.

Proof

The proof is straightforward from the definition of cut-vertex in a graph. $\square$

Figure 3 presents examples of preprocessing in Lemma 7. In (a) of Fig. 3, we must put a regenerator at node 1 to support the communication between nodes 3 and 4. In (b) of Fig. 3, one regenerator must be placed on node 5 to ensure the communication between 8 and 9.

Fig. 3

Examples of Preprocessing in Lemma 7

Following Lemmas 6 and 7, we can immediately set some binary variables equal to one in the optimal solution. Let ${\widetilde{B}}$ be the set of nodes, at which we must put regenerators following Lemmas 6 and 7. We now present the third preprocessing procedure.

Lemma 8

Determine the connected components of graph K spanned by nodes in ${\widetilde{B}}$. We can remove one NDC node pair $\{s, t\}$ from $\Pi$, if nodes s and t are both connected to some component W of graph K.

Proof

Consider one connected component W of graph. Since nodes in W must be regenerator nodes in the optimal solution, any NDC node pair $\{s, t\}$ is always connected if both nodes s and t are connected at least to one node in W. Such kind of NDC node pairs can be removed from $\Pi$. This completes our proof. $\square$

4.3 Starting formulation

We enumerate a few simple T-DSNs to initialize the starting formulation. For each NDC node pair $\{i, j\}$, we generate a simple T-DSN as $D= \{k\in S: \{i, k\}, \{j, k\}\in E\}$. After removing duplicate elements, we use these T-DSNs to generate constraints in (2), and thus initialize formulation SCF.

4.4 Separation method for identifying valid inequalities

We now discuss how to identify violated cuts in the B&C approach. Because the set covering formulation contains an exponential number of constraints, it is not practical to include all these constraints in the starting formulation. Alternatively, the starting formulation includes only a few constraints (refer to Sect. 4.3), and valid inequalities (cutting planes) are identified based on the solution ${\overline{x}}$ to each node linear programming (LP) of the branch and bound (B&B) search tree.

In our B&C approach, the separation problem is to find a T-DSN D, if one exists, such that

$$\begin{aligned} \sum _{i\in D}{\overline{x}}_{i}<1. \end{aligned}$$

Hereafter, we refer to such a D as a valid T-DSN.

We present a minimum-cut based approach to solve the separation problem. The underlying idea is that, as we will show below, there is a one-to-one correspondence between a cut in a capacitated reachability graph and a valid T-DSN. As a result, solving the separation problem reduces to one of finding a proper minimum cut. Note that the separation of T-DSN inequalities using maximum flows follows from the max-flow min-cut theorem (Ford and Fulkerson 1974), which was also used in Chen et al. (2015), Fügenschuh and Fügenschuh (2008), Fischetti et al. (2014), Álvarez-Miranda et al. (2013), and Li and Aneja (2017). In our B&C approach, the separation method is always implemented to identify a most violated valid inequality with minimum cardinality. At every B&B enumeration node, we repeat the separation method until no violated inequality is found.

We now detail the separation method and its implementation. In Sect. 4.4.1, we first present the separation method, which can be applied to either fractional, or integer LP solution ${\overline{x}}$. In Sect. 4.4.2, we then present three speeding-up strategies for implementing this separation method.

4.4.1 Separation method

The separation method is shown in Algorithm 1. CAP$_m$ denotes the value of most-violated inequality, which is initialized to 0.99999. The value of CAP$_m$ is updated during the course of the separation method.

Recall that nodes of an NDC node pair $\{i, j\}$ can communicate with each other, if and only if we place regenerators on some s-nodes in the same S-components to which nodes i and j both belong. Consider an example in (a) of Fig. 4. Node 7 cannot communicate with node 8 unless some node in $\{2, 3\}$ or $\{4, 5\}$ is equipped with regenerator. Using this observation, we let the separation method work on the common S-components, to which two t-nodes are connected. For each NDC node pair $\{s,t\}$, we first define a new capacitated reachability digraph $G_{st}=(N_{st}, A_{st})$. Node set $N_{st}$ and arc set $A_{st}$ are defined as:

$$\begin{aligned} \begin{array}{l} N_{st} = \bigcup \limits _{k\in {\mathcal {N}}(s,t)} N^k_{st} , \\ A_{st} = \bigcup \limits _{k\in {\mathcal {N}}(s,t)} A^k_{st},\\ \end{array} \end{aligned}$$

where set $N^k_{st}$ is defined as $N^k_{st}=\Lambda _k \bigcup \{s,t\}$. Define $A^k_{st}$ as $\{(i,i'): i\in \Lambda _k\}\bigcup \{(s,j): j \in \Lambda _k, \{s, j\}\in E\} \bigcup \{(i', t): i\in S_k, \{i,t\}\in E\}$. Refer to $G^k_{st}$ as a subgraph induced by component $k \in {\mathcal {N}}(s,t)$, i.e., $G^k_{st} = (N^k_{st},A^k_{st})$. Arc capacities are calculated as $c_{ii'}={\overline{x}}_i, \forall i\in \Lambda _k, \forall k\in {\mathcal {N}}(s, t)$, and $c_{pq}=\infty$ for other arcs (p, q). Figure 4(b) presents an example of creating the capacitated reachability digraph associated with NDC node pair $\{6, 7\}$ in Fig. 4(a). In this example, only two S-components $\{1\}$ and $\{2, 3\}$ are associated with NDC node pair $\{6, 7\}$.

Fig. 4

Capacitated Reachability Digraph Associated with NDC Node Pair $\{6,7\}$

In graph $G_{st}$, let $[\Gamma _{st}, {\overline{\Gamma }}_{st}]$ be a cut separating nodes s and t such that $s \in \Gamma _{st}$, $t\in {\overline{\Gamma }}_{st}$, and ${\overline{\Gamma }}_{st}=N_{st}\backslash \Gamma _{st}$. Obviously, every cut $[\Gamma _{st}, {\overline{\Gamma }}_{st}]$ composed of arcs $(i, i')$ defines an T-DSN $D=\{i\in S: i\in \Gamma _{st}, i'\in {\overline{\Gamma }}_{st}\}$ because removal of nodes in D will disconnect at least node pair $\{s, t\}$. To illustrate, consider graph $G_{67}$ in (b) of Fig. 4. Cut $[\Gamma _{67}, N_{67}\backslash \Gamma _{67}]$ with $\Gamma _{67}=\{1, 2, 6\}$ and ${\overline{\Gamma }}_{67}=\{1', 2', 3, 3', 7\}$ defines a T-DSN $D=\{1, 2\}$. This one-to-one correspondence implies that the separation problem of finding a valid T-DSN can also be done by solving a series of minimum cut problems in graph $G_{st}$. Any cut $[\Gamma _{st}, {\overline{\Gamma }}_{st}]$ with $s\in \Gamma _{st}$ and $t\in {\overline{\Gamma }}_{st}$ is referred to as an s-t cut. We refer to the problem of finding the minimum s-t cut as minimum s-t cut problem. Let $\hbox {CAP}_{{st}}$ be the capacity of the s-t cut and $D_{st}$ be its corresponding valid T-DSN.

In our B&C approach, the minimum cut based separation method is established based on Lemma 9.

Lemma 9

Suppose we create a capacitated reachability graph $G_{st}$ for NDC node pair $\{s, t\}$, and solve the minimum s-t cut problem in graph $G_{st}$. Then, the returned minimum s-t cut $[\Gamma _{st}, {\overline{\Gamma }}_{st}]$ defines a valid T-DSN $D_{st}$ if and only if the capacity of this cut is less than one.

Proof

First consider the “only if” part of this lemma. Suppose the cut defines a valid T-DSN D. If the cut capacity is greater than, or equal to one, then the possible T-DSN D must have $\sum _{i\in D} {\overline{x}}_i \ge 1$. This contradicts the given assumption.

Now consider the “if” part. Recall that capacities of arcs except for $(i, i')$ are $\infty$. Therefore, the minimum s-t cut only includes arcs $(i, i')$, if its cut capacity is less than one. Let R be the set of such arcs and define $D=\{i\in N: (i, i') \in R\}$. Clearly, D is a T-DSN. That is, the minimum s-t cut defines a valid T-DSN D with $\sum _{i\in D} {\overline{x}}_i < 1$. $\square$

Further, we present below a necessary condition for a solution being feasible to a GRLP instance.

Lemma 10

Consider a GRLP instance. If a binary solution x is feasible, then for every NDC node pair $\{s, t\}\in \Pi$, any cut separating s and t in $G_{st}$ has a capacity of at least 1.

Proof

Suppose for some NDC node pair $\{i, j\}$, we have a cut $[\Gamma , {\overline{\Gamma }}]$ with a capacity of less than 1. Note that any valid minimum cut $[\Gamma , {\overline{\Gamma }}]$ only includes arc of $(i, i')$. Because x is binary, this cut must have a capacity of zero. We thus get an T-DSN D with $\sum _{i\in D} x_i =0 < 1$. That is, constraints (2) are violated. This contradicts the given condition: x is feasible and thus completes our proof. $\square$

Following the above two lemmas, we implement the separation method in the B&C approach as follows (also refer to Algorithm 1). For each NDC node pair $\{s, t\}$, we iteratively implement the separation method by solving a series of maximum flow problems, each one of which is defined over subgraph $G^k_{st}$. In subgraph $G^k_{st}$, let $[\Gamma ^k_{st}, {\overline{\Gamma }}^k_{st}]$ be a cut separating nodes s and t such that $s \in \Gamma ^k_{st}$, $t\in {\overline{\Gamma }}^k_{st}$, and ${\overline{\Gamma }}^k_{st}=N^k_{st}\backslash \Gamma ^k_{st}$, and CAP$^k_{st}$ be the cut capacity. In addition, define $D^k_{st}$ to be the valid T-DSN derived from cut $[\Gamma ^k_{st}, {\overline{\Gamma }}^k_{st}]$.

Obviously, we have

$$\begin{aligned} \begin{array}{cl} \Gamma _{st} &{}= \bigcup \limits _{k\in {\mathcal {N}}(s,t)} \Gamma ^k_{st}, \\ {\overline{\Gamma }}_{st} &{} = \bigcup \limits _{k\in {\mathcal {N}}(s,t)} {\overline{\Gamma }}^k_{st},\\ \text {CAP}_{st}&{} = \sum \limits _{k\in {\mathcal {N}}(s,t)} \text {CAP}^k_{st}. \end{array} \end{aligned}$$

If the capacity of the returned cut $[\Gamma _{ij}, {\overline{\Gamma }}_{ij}]$ is less than one, we then have a valid T-DSN $D_{ij}=\{s\in S: s\in \Gamma _{ij}, s'\in {\overline{\Gamma }}_{ij}\}$ and a violated valid inequality as

$$\begin{aligned} \sum _{s\in \Gamma _{ij}: s'\in {\overline{\Gamma }}_{ij}} x_s\ge 1. \end{aligned}$$

(4)

Note that in Algorithm 1, we are able to terminate the separation routine earlier if the intermediate $\hbox {CAP}_{{st}}$ is greater than CAP$_m$ (it is updated in the separation routine, see Algorithm 1). Each minimum i-j cut problem in graph $G^k_{ij}$ is solved using the the pseudoflow algorithm of complexity $O(|A^k_{ij}||N^k_{ij}|\log (|N^k_{ij}|))$ (Hochbaum 2008). Therefore, the running time of separation method without lifting procedure is $O(|\Pi ^*||\Lambda ||S|(|S|+|E|)\log (|S|))$ in the worst case. In Sect. 4.4.2, we will introduce other speeding-up strategies for the separation method.

We then validate whether a valid T-DSN D is an FDI and implement the lifting procedure (see Algorithm 2). That is, we should check if the intersection $C = \cap _{i\in D}\Phi _i =\emptyset$. Following the proof in Sect. 3, for each node $i_j\in D$, we first create graph $G_{i_j}=(N_{i_j}, E_{i_j}, S_{i_j})$ with node set $N_{i_j}$, edge set $E_{i_j}$, and s-node set $S_{i_j}= S\backslash D \cup \{i_j\}$. We then check whether removal of each node in $S_{i_j}$ makes the GRLP instance infeasible and identify $\Phi _{i_j}$. In Algorithm 2, we use a speeding-up strategy to determine the intersection C. Suppose $D=\{i_1, i_2, \ldots , i_k\}$ is not an FDI. This means that $C\ne \emptyset$. Therefore to determine $\Phi _i$, we only need to examine each s-node in $S\backslash D$. Furthermore, we have $C\subset \Phi _{i_j}\cap \Phi _{i_{j+1}}$. Hence, to determine $\Phi _{i_{j+1}}$, we can reduce our search to the examination of s-nodes in $\Phi _{i_j}$, instead of in $S\backslash D\cup \{i_{j+1}\}$. For detailed implementation, refer to Algorithm 2. We add violated cuts in the following two cases:

(1) Case 1: $C=\emptyset$. In this case, we add an FDI to the node LP and resolve it again.

(2) Case 2: $C\ne \emptyset$. In this case, D does not define an FDI. For each node $j\in C$, we add to the node LP one lifted inequality:

$$\begin{aligned} \sum _{i\in D} x_i + x_j \ge 2, \end{aligned}$$

if conditions of Lemmas 2 and 3 are satisfied. Otherwise, if condition of Lemma 2 is not satisfied, based on Lemma 5, we can add the lifted inequality:

$$\begin{aligned} \sum _{i\in D} x_i + (p-1)x_j \ge p, \end{aligned}$$

where $p=|D\cap \Psi _{j}|$. If condition in Lemma 4 is not satisfied, we can add the lifted inequality stated in Lemma 6.

$$\begin{aligned} \sum _{i\in D} x_i + x_j+(p-1)x_{k^*} \ge p, \end{aligned}$$

where $p=|\{D\cup \{j\}\}\cap \Psi _{k^*}|$ for a selected $k^*\in C\backslash \{ j\}$.

4.4.2 Implementation strategies for the separation method

We next present some speeding-up strategies for implementation of the separation method.

Given subgraph $G^k_{st}$, we determine the maximum capacity path from source s to sink t. Let $\text {C}^k_{st}$ be the returned path capacity. We now introduce the first speeding-up strategy.

Lemma 11

We need to consider one NDC node pair $\{s, t\}$ in the separation problem, if $\text {C}^k_{st} < CAP _m, \forall k\in {\mathcal {N}}(s, t)$, and $\sum _{k\in {\mathcal {N}}(s, t)} \text {C}^k_{st} < CAP _m$.

Proof

Following the definition of the maximum capacity path problem, $C^k_{st}$ gives a lower bound on the maximum flow from s to t in subgraph $G^k_{st}$, and $\sum _{k\in {\mathcal {N}}(s, t)}C^k_{st}$ gives a lower bound on maximum flow from s to t in subgraph $G_{st}$. We thus need not consider node pair $\{s, t\}$, if $\text {C}^k_{st} \ge \text {CAP}_m, \forall k\in {\mathcal {N}}(s, t)$, or $\sum _{k\in {\mathcal {N}}(s, t)}\text {C}^k_{st} \ge \text {CAP}_m$. $\square$

Using Lemma 11, we may be able to reduce the number of minimum cut problems, which need to be solved in the separation routine to determine initial $\Pi ^*$ in Algorithm 1.

Given one S-component $\Lambda _k$, t-node i, and an LP relaxation solution ${\overline{x}}$, let $X^k_i=\{j: j\in \Lambda _k, \{i, j\}\in E, {\overline{x}}_j > 0\}$. Further define $X_i = \bigcup _{k=1, 2, \ldots , n_s} X^k_i$.

Lemma 12

Suppose we have NDC node pair $\{i, j\}$ with $CAP ^k_{ij} \} CAP _m$. Then NDC node pair $\{s, t\}$ with $\Lambda _k(s)=\Lambda _k(t)=1$ can be removed from $\Pi ^*$, if $X^k_i \subseteq X^k_s$ and $X^k_j \subseteq X^k_t$.

Proof

Consider one node pair $\{s, t\}$ connected to component $\Lambda _k$. If $X^k_i \subseteq X^k_s$ and $X^k_j \subseteq X^k_t$, then capacity $\text {CAP}^k_{st}$ is at least equal to $\text {CAP}^k_{ij}$ (greater than CAP$_m$). Therefore, it is impossible to find a valid most-violated T-DSN from $\{s, t\}$, which thus can be removed from $\Pi ^*$. $\square$

Based on Lemma 12, we present Procedure UpdatePi1, which is used in Algorithm 1.

Lemma 13

Consider one NDC node pair $\{i, j\}$ and subset $\overline{{\mathcal {N}}} (i, j) \subseteq {\mathcal {N}}(i, j)$. Suppose intermediate cut capacity $CAP _{ij} = \sum _{k\in \overline{{\mathcal {N}}} (i, j)} CAP ^k_{ij}> CAP _m$. An NDC node pair $\{s, t\}$ can be removed from $\Pi ^*$, if $X^k_i \subseteq X^k_s$ and $X^k_j \subseteq X^k_t, \forall k\in \overline{{\mathcal {N}}} (i, j)$.

Proof

Condition $X^k_i \subseteq X^k_s$ and $X^k_j \subseteq X^k_t, \forall k\in \overline{{\mathcal {N}}} (i, j)$ implies that cut capacity $\hbox {CAP}_{{st}}$ is greater than, or equal to $\hbox {CAP}_{{ij}}$. Therefore, we cannot find a desirable T-DSN from node pair $\{s, t\}$, which thus can be removed from $\Pi ^*$. $\square$

Lemma 13 leads to Procedure UpdatePi2 in Algorithm 1.

To illustrate these two speeding-up strategies, we present an example in Fig. 5. This is a nine-node network with two S-components (for simplification, we mark connectivity between t-nodes and s-nodes, and do not mark connectivity between s-nodes). Nodes numbered 10 and 11 are only connected to $\Lambda _1$. Other t nodes are both connected to two components. Suppose we have ${\overline{x}}_1>0, {\overline{x}}_2> 0, {\overline{x}}_4>0, {\overline{x}}_5>0, {\overline{x}}_6>0, {\overline{x}}_8>0$, and ${\overline{x}}_9>0$. If $\text {CAP}^1_{10,11} > \text {CAP}_m$, one may observe that any cut for $\{12, 13\}$ must have a capacity greater than $\text {CAP}^1_{10,11}$ and the separation for $\{12, 13\}$ can terminate. Further if $\text {CAP}_{12,11} > \text {CAP}_m$, we terminate separation for $\{14, 11\}$ and $\{14, 13\}$.

Fig. 5

Example of Speeding-up Strategies for the Separation Method

4.5 Pruning, speeding-up and early termination rules

We finally present pruning and speeding-up rules to improve the overall computational performance of our B&C approach.

For each variable $x_i$, let $x^+_i$ and $x^-_i$ be its upper and lower bounds. At node h of the B&B enumeration tree, let ${\widehat{U}}_1=\{s\in S: x^-_s = 1\}$, ${\widehat{U}}_2=\{s\in S: x^+_s = 0\}$, and ${\widehat{U}}_3=S\backslash {\widehat{U}}_2$. Set ${\widehat{U}}_1$ includes nodes equipped with regenerators, and ${\widehat{U}}_3$ is the set of all candidate regenerator nodes. Construct a binary solution $x^*(h)=(x^*_1, x^*_2, \ldots , x^*_{|S|})$ such that $x^*_i=0, \forall i\in {\widehat{U}}_2$ and $x^*_i=1, \forall i\in {\widehat{U}}_3$. Let ${\overline{Z}}$ and LB(h) be respectively the objective value of the best incumbent and LP subproblem at node h.

Lemma 14

Node h can be pruned from the B&B search tree if

$$\begin{aligned} LB(h) > {\overline{Z}}-1. \end{aligned}$$

Proof

The formulation shows that every feasible solution should have an integer objective value. If $LB(h) > {\overline{Z}}-1$, there is no possibility to find better incumbent at child nodes of the current node h. Therefore, we should prune this node. $\square$

Without proof, we present the second pruning rule:

Lemma 15

Consider one node h in the B&B search tree and construct binary solution $x^*(h)$. Node h can be pruned from the B&B search tree if solution $x^*(h)$ is infeasible for the GRLP instance under consideration.

Using the following result, we may further fix the values of some variables, even if node h cannot be fathomed from the search tree.

Lemma 16

Given node h that cannot be fathomed according to Lemma 15, define a restricted graph $G(h)=(V(h), E(h))$ with node set $V(h)= N\backslash {\widehat{U}}_2$ and edge set $E(h)=\{\{i,j\}\in E: i, j\in V(h)\}$. We can fix lower bound of variable $x_i$ equal to one at node h, if removal of s-node i from graph G(h) makes the GRLP instance infeasible.

Proof

Graph G(h) excludes every s-node i of which variable $x_i$ has been branched to zero. Every feasible integer solution found at child nodes of the current node h can only use nodes in ${\widehat{U}}_3$ as candidate regenerators. Therefore, if removal of some node i from graph G(h) makes instance infeasible, we must deploy one regenerator at this node. That is, set the lower bound of $x_i$ to one.

$\square$

As a result of Lemma 16, we present another pruning rule in the following lemma:

Lemma 17

At node h in the B&B search tree, let ${\mathcal {Q}}(h)$ be the set of variables that can be fixed to one in Lemma 16. Node h can be fathomed if

$$\begin{aligned} |{\mathcal {Q}}(h)| + |{\widehat{U}}_1| \ge {\overline{Z}}. \end{aligned}$$

Proof

It follows from Lemma 16 that every feasible solution must have an objective value greater than $|{\mathcal {Q}}(h)| + |{\widehat{U}}_1|$. If this value is not less than the upper bound ${\overline{Z}}$ on the objective value, then it is impossible to find better integer solution at any child node of the current node h, which thus can be pruned from the search tree. $\square$

In our approach, we implement the above strategies when depth of node h in the B&B search tree is greater than 0.40|S| and node h is created by down branching.

We now present an early termination rule of our B&C approach. At node h in the enumeration tree, let UB and LB be the objective value of the best incumbent and the best known bound of all remaining open nodes, respectively. The B&C approach optimally solves an instance and can be terminated earlier if $UB- LB < 1$ at any node in the B&B search tree.

5 Heuristics

It is a common choice to supply an initial integer solution to the B&C approach. A starting incumbent might eliminate some parts of the solution space and thus accelerate the overall process. We present below the two heuristics to generate feasible solutions: enumeration based heuristic and shortest path based heuristic. Since these two heuristics work fast, we implemented both of them and chose the best returned solution as the starting incumbent. Before detailing these two heuristics, we first list some notation as follows.

• $d_i$: degree of s-node i; i.e., the number of t-nodes adjacent to node i in G.

• $p_i$: p-degree of s-node i; i.e., the number of NDC node pairs that can be connected when we deploy one regenerator at node i.

• L: set of regenerator nodes.

• V(i): set of explored adjacent t-nodes; i.e., the adjacent t-nodes of s-node i that are    also adjacent to some node $j\in L$.

• U(i): set of unexplored adjacent t-nodes; i.e., $U(i)=N(i)\backslash V(i)$.

• #NDC: number of NDC node pairs that can be connected using regenerators in L.

• $L_m$: set of regenerator nodes associated with the best solution.

• $\Upsilon$: set of NDC node pairs being connected by the current regenerators.

• $P_{ij}$: shortest path with source i and sink j in G.

• $W(P_{ij})$: set of internal nodes of path $P_{ij}$.

5.1 Enumeration based heuristic

Algorithm 5 gives the outline of the enumeration-based heuristic. It is a pseudo-greedy method that iteratively selects an s-node with maximum p-degree to place one regenerator until all NDC node pairs can communicate with each other. It works as follows. At the beginning, we initialize $p_i$ to be $C_{d_i}^2=d_i(d_i-1)/2$ and update values of $p_i$ during the course of solution generation. Consider one s-node i that is selected as a candidate regenerator. It may fall into one of the following two cases:

Case 1: Node i is not connected to any s-node in L. If i becomes regenerator, it may connect three parts of NDC node pairs: (a) $\Pi _1 =\{\{j, k\}\in \Pi ^*: j\in V(i), k\in U(i)\}$ (e.g., $\Pi ^*$ is the set of NDC node pairs after the preprocessing procedure is implemented); (b) $\Pi _2 = \{\{j, k\}\in \Pi ^*: j, k\in U(i)\}$; and (c) $\Pi _3 = \{\{j, k\}\in \Pi ^*: j, k\in V(i), \text {\{j, k\}{} is still not connected}\}$. We approximately calculate $p_i$ as

$$\begin{aligned} p_i = r_1 |U(i)|(|U(i)| -1)/2 + r_2 |U(i)| |V(i)| + r_3 |\Pi _3|, \end{aligned}$$

where $r_1$, $r_2$ and $r_3$ denote the relative importance of three parts in guiding regenerator selection; i.e., $r_1+r_2+r_3=1$.

Case 2: Node i and some s-nodes in L form a connected component. Define $Q(i)= V(i) \cup \{V(j): j\in L, \{i, j\}\in E\}$. If we place one regenerator at node i, we may connect three parts of NDC node pairs: (a) $\Pi _1 =\{\{j, k\}\in \Pi ^*: j\in Q(i), k\in U(i)\}$; (b) $\Pi _2 = \{\{j, k\}\in \Pi ^*: j, k\in U(i)\}$; and (c) $\Pi _3 = \{\{j, k\}\in \Pi ^*: j, k\in Q(i), \text {\{j, k\}{} is still not connected}\}$. Then $p_i$ is approximately calculated as

$$\begin{aligned} p_i = r_1 |U(i)|(|U(i)| -1)/2 + r_2 |U(i)| |Q(i)| + r_3(|\Pi _3|. \end{aligned}$$

In Algorithm 5, we define ${\hat{S}}=\{{\hat{S}}_1, {\hat{S}}_2, \ldots , {\hat{S}}_{|S|}\}$ that makes it easily to store the connected components of L and thus update values of $p_i$ very quickly. Following the feasibility checking in Sect. 2.1.1, we know the running time of calculating #NDC is at most $O(|N|+|E|+ |T|^2 )$. The running time of calculating V(i) is O(|E||S|) in the worst case. Therefore, the enumeration-based heuristic takes $O(n^4)$ time in the worst case. In our implementation, we set $r_1=0.05$, $r_2=0.37$ and $r_3=0.58$. Our results show Algorithm 5 was able to generate initial integer solutions within 200 s for all 300 considered benchmark instances.

5.2 Shortest path based heuristic

We next present the shortest path based heuristic, which is shown in Algorithm 6. The underlying idea is that in graph G, we need to construct a path with minimum number of internal s-nodes to link each NDC node pair $\{i, j\}$. This can be accomplished by solving at most one shortest path problem for each NDC node pair. We first create a directed graph ${\widetilde{G}}=(N, {\widetilde{A}}, {\widetilde{C}})$ with arc set ${\widetilde{A}}=\{(i,j), (j, i): \{i, j\}\in E\}$. The cost function ${\widetilde{C}}$ is initialized as ${\widetilde{c}}_{ij}=1, \forall (i, j)\in {\widetilde{A}}$ and updated during the course of solution. Then determining a minimum number of s-nodes to connect NDC node pair $\{i, j\}$ reduces to solving a shortest path problem with i and j being source and sink nodes, respectively. Once an s-node j is set as a regenerator node, we prefer to use it in subsequent path construction. This can be done by setting to zero costs of all arcs entering node j. Data structure in Algorithm 5 is also used in Algorithm 6 to update the value of #NDC and $\Upsilon$.

Because Algorithm 6 works quite fast, we ran it $t_{max}$ (e.g., 100) times in our implementation. Dijkstra’s algorithm is implemented to solve the shortest path problem, defined for each NDC node pair $<i, j>$ (Ahuja et al. 1993). In the worst case, we need to solve one shortest path problem for each NDC node pair in $\Pi$. The running time of Dijkstra’s Algorithm is $O(n^2)$. Therefore, the shortest path based heuristic runs in $O(t_{max}|\Pi |n^2)$ time.

5.3 Hybrid implementation strategy of heuristics

Our preliminary computational results show that neither of two heuristics could find better solutions across all test instances. To get a good starting incumbent, we thus propose a hybrid implementation strategy of heuristics. The underlying idea is that we first implement the enumeration based heuristic until the percentage of NDC node pairs being connected reaches a given threshold $\eta$. Then the shortest path based heuristic is invoked if there still exist NDC node pairs, which have not been connected by the current regenerator placement. The percentage of connected NDC node pairs is calculated as #NDC/$|\Pi ^*|$. In our experiments, we respectively implemented this hybrid strategy with $\eta =0$(only shortest path based heuristic is implemented), 0.5, 0.9 and 1 (only the enumeration based heuristic is invoked), and chose the best solution as the incumbent.

6 Experimental evaluation

We next empirically evaluate the proposed B&C approach. The algorithm was implemented in C language and computational experiments were carried out on a PC with Intel CPU 3.1 GHz and 4 GB RAM. In all of the experiments, we report the computational time in seconds.

6.1 Test methods

To demonstrate effectiveness and efficiency of our approach, we compare it with one exact algorithm available in the literature. The methods in the comparison study are listed in Table 1. As one may observe, our test computer is older than that in Chen et al. (2015).

Table 1 Testing methods

6.2 Test instances

Test instances used in our experiments include benchmark instances and newly generated instances.

6.2.1 Benchmark instances

Chen et al. (2015) have generated two sets of 300 instances with random networks and the number of nodes ranging from 50 to 500. The solution difficulty of each instance is controlled by two parameters: n and $p\in [0, 1]$ representing the percentage of s-nodes among n network nodes. With these 300 benchmark instances, we report on our experience with the proposed approach.

Chen et al. (2015) have generated two sets of 300 instances. Set 1 consists of 150 small instances with up to 150 nodes. Set 2 includes large scale instances with the number of nodes ranging from 175 to 500. Ten instances have been generated for each pair of n and $p\in \{25\%, 50\%, 75\%\}$. For detailed data generation method, please refer to Sect. 6.1 of Chen et al. (2015).

6.2.2 Newly large instances

To examine the performance of our approach, we further generate new larger instances (Set 3). For this purpose, we implemented the method in Chen et al. (2015) to generate new instances. Set 3 contains 90 instances with $n\in \{600, 800, 1000\}$ and $p\in \{25\%, 50\%, 75\%\}$. For each pair of n and p, we generated ten instances. Table 2 gives characteristics of new instances. For instances in each group, #SCom and |NDC| respectively represent the average numbers of S-components and NDC node pairs.

Table 2 Characteristics of newly large instances

For each instance, we set a running time limit of 1 h. The same time limit is also used for the algorithm in Chen et al. (2015). The computational results of BC$\_$CLR are directly taken from the original paper, since our approach is implemented on an older computation platform.

6.3 Comparison results on instances in set 1

With 150 instances in Set 1, we first evaluate our B&C approach by comparing it with the one developed by Chen et al. (2015). Table 3 summarizes the computational results. For each pair of n and p, each row of Table 3 aggregates results from ten instances. We report the following performance measures:

• #fix: the average number of variables fixed in the preprocessing procedure.

• LB$_r$: the LP-relaxation values obtained at the root node.

• NR: the average number of regenerators returned by algorithms on termination.

• LB: the best known bound of all of the remaining open nodes in a B&B tree at termination, which is the best-known lower bound on the optimal solution value of each instance.

• Gap(%): the relative objective gap between the best node value (LB) and the objective value of the best integer solution at termination of the B&C approach. If one instance is solved to provable optimality within the time limit, the corresponding Gap is equal to zero.

• CPUs: the average computing time required to solve ten instances in each group. If one instance is not optimally solved within the time limit, we set the computational time to 3600 s.

• #Opt: the number of instances that were optimally solved within the time limit.

Table 3 Comparison results on GRLP instances in Set 1

We first discuss the performance of preprocessing procedure. Chen et al. (2015) have stated that their preprocessing procedure could not fix any regenerator. The results show that our preprocessing procedure could fix some variables. Of the 150 instances, the preprocessing procedure helped in 38 instances, e.g., fixing 226 variables. But the number of regenerators fixed decreases with the number of network nodes.

We next compare the lower bounds obtained at the root node of the B&B tree. The results in Table 3 show that the lower bounds after adding lifted cuts are, most of time, better than those returned by the formulation in Chen et al. (2015). These lifted inequalities significantly improve the lower bounds. On average, our lower bounds reach an increase of 14.46%.

We finally discuss algorithmic performance comparison. The computational results in Table 3 show that NBC managed to solve all these 150 instances. Of 150 instances of this group, BC_CLR solved all but one to provable optimality. The two B&C approaches provide optimality certificates for essentially similar instances. Despite that, NBC performed much faster than BC_CLR, as the new B&C approach required less computing time to optimally solve these 150 instances. Such an improvement, we believe, is because of effects of lifted cuts derived in our separation scheme. Lifted stronger cuts sped up the algorithm.

Table 4 Comparison results on GRLP instances in set 2

6.4 Comparison results on instances in set 2

In this section, we further examine the behavior of our approach on the large scale instances in Set 2. Table 4 reports the comparison results. Because the preprocessing procedure only fixed regenerators on two instances in Set 2, we do not include “#fix” in Table 4.

Of 150 instances of this group, BC_CLR reached optimal solutions in 47 instances with the time limit of 3600 s. As one may observe from the results in Table 4, NBC managed to optimally solve 114 of the 150 tested instances. Our approach significantly extended the ability in solving large GRLP instances. When we focus on those instances that two algorithms could solve optimally, NBC is much faster. Whereas BC_CLR could solve only four 300-node instances, NBC was able to solve fifteen 400-node and nine 500-node instances, respectively. For the instances that were not solved by BC_CLR, NBC always obtained better integer solutions and lower bounds at termination. The is explained by the strength of lifted procedures in NBC, which sped up the solution process and thus improved the overall performance.

To summarize, our computational experiments based on benchmark instances show that our B&C approach is more competitive than other available branch-and-cut algorithm in the literature, and better overall results are obtained.

6.5 Computational results for newly large instances in set 3

We finally examine the behavior of our approach on large scale instances in Set 3. NBC was implemented to solve 90 instances. The same time limit of 1 h is used. The computational results are reported in Table 5.

Table 5 Computational results for newly large instances in set 3

As the problem size increases, instances become more challenging, which is indicated by the gap between the upper and lower bounds at NBC’s termination (see Gap in Table 5). Of 90 large-scale instances, NBC produced optimal solutions in 15. We further found that in some cases, the branch-and-cut approach was unable to solve the LP relaxation at the root node in less than an hour. In 67 instances, the NBC did not proceed beyond the root node within the 1-h time limit.

7 Conclusions

Optical reach defines the maximum distance an optical signal can travel before it degrades to a level that necessitates that it be cleaned up, or regenerated. It is an important property of a transmission system, which is a necessary ingredient for enabling optical bypass and thus significantly affects optical network design. In this paper, we study the generalized location problem that deals with a constraint on the geographical extent of signal transmission in optical network design. The GRLP has been shown to be ${\mathcal {NP}}$-hard and is a more general and challenging regenerator location problem. With an existing set covering formulation, we study the polyhedral structure of the convex hull of all feasible solutions and derive necessary and sufficient conditions on constraints being FDIs. As a result, we propose a method for lifting a non-facet-defining inequality to a stronger one. We also derive conditions for a lifted inequality to be an FDI, and show how to further lift them. With facet results and set covering formulation, we present a new branch-and-cut approach. With 300 benchmark instances and 90 newly generated large instances, we finally conduct a series of computational experiments to evaluate our proposed approach. The computational results show that our branch-and-cut algorithm is a competitive exact method, significantly outperforming the existing exact method in the literature.

Appendix

1.1 Proof of Theorem 1

We first prove the “if” part of this theorem by exhibiting a set of |S| feasible affinely independent vectors that satisfy $\sum _{i\in D}x_{i}\ge 1$ as an equality. Since the hyperplane $\sum _{i\in D}x_{i}=1$ does not contain the origin, any set of affinely independent vectors on it are also linearly independent. Thus we will produce |S| feasible linearly independent vectors that satisfy $\sum _{i\in D}x_{i}=1$. We thus assume that $C=\emptyset$. Suppose $|D|=k$. Take a node $i\in D$. Since D is minimal by assumption, removal of all the nodes in $D\backslash \{i\}$ from G does not make the problem infeasible. That is, putting a regenerator at each of the nodes in $(\{N\backslash D\}\cup \{i\})$ provides a feasible solution to the GRLP. Further, for each $i\in D$, create an |S|-vector $x^{i}$ such that

$$\begin{aligned} x_{r}^{i}=\left\{ \begin{array}{cl} 0, &{}\quad \forall r\in D\backslash \{i\}, \\ 1, &{}\quad {\text {otherwise.}} \end{array} \right. \end{aligned}$$

Each of these k vectors corresponds to a feasible solution and satisfies $\sum _{i\in D}x_{i}=1$. Rearranging the variables so that k variables corresponding to D appear first, the $|S|\times k$ submatrix of these k columns can be written as $\left[ \begin{array}{c} I_{1} \\ \mathbf {1}_{1} \end{array} \right]$, where $I_{1}$ is a $k\times k$ identity matrix, and $\mathbf {1} _{1}$ is a $(|S|-k)\times k$ matrix of all 1’s. Clearly these k vectors are linearly independent. Consider, now, a s-node $j\notin D$. Suppose we do not allow a regenerator to be placed at this node. By assumption of the theorem, there is some $i\in D$ such that $j\notin \Phi _{i}$. Create an |S|-vector $x^{j}$:

$$\begin{aligned} x_{r}^{j}=\left\{ \begin{array}{cl} 0, &{}\quad \forall r\in D\cup \{j\}\backslash \{i\}, \\ 1, &{}\quad {\text {otherwise.}} \end{array} \right. \end{aligned}$$

It is easy to verify that these $|S|-k$ vectors $\{x^{j},j\in S\backslash D\}$ are feasible solutions and satisfy $\sum _{i\in D}x_{i}=1$. The $S\times (|S|-k)$ submatrix of these $|S|-k$ columns can be written as

$$\begin{aligned}\left[ \begin{array}{c} A \\ \mathbf {1}_{2}-I_{2} \end{array} \right] , \end{aligned}$$

where $\mathbf {1}_{2}$ is a $(|S|-k)\times (|S|-k)$ matrix of all 1’s, and $I_{2}$ is an identity matrix. It is easy to see that $\mathbf {1}_{2}-I_{2}$ is a non-singular matrix, and the columns of this submatrix thus are linearly independent. Combining these two submatrices we get an $|S|\times |S|$ non-singular matrix $\left[ \begin{array}{cc} I_{1} &{}\quad A \\ \mathbf {1}_{1} &{}\quad \mathbf {1}_{2}-I_{2} \end{array} \right] .$ These |S| columns correspond to feasible solutions that lie on the hyperplane $\sum _{i\in D}x_{i}=1.$ This proves the “if” part of the theorem.

We now prove the “only if” part of the theorem. Suppose $C\ne \emptyset ,$ and $j\in C.$ Thus there is a node $j\in S\backslash D$ such that removal of node j from G makes the problem infeasible. Hence to obtain a feasible solution, we must put a regenerator at node j. That is, $x_{j}=1$ for every feasible solution that satisfies $\sum _{i\in D}x_{i}=1.$ Hence $\sum _{i\in D}x_{i}\ge 1$ cannot be an FDI. This completes our proof. $\square$

1.2 Proof of Lemma 1

If $x_{j}=1$, then the above inequality reduces to a valid inequality: $\sum _{i\in D}x_{i}\ge 1.$ Suppose $x_{j}=0$. Then, as we observed in the proof of Theorem 1, we cannot find a feasible solution if we place regenerator at only one node of D. That is, $\sum _{i\in D}x_{i}+x_j\ge 2$ is a valid inequality for each $j\in C.$ $\square$

1.3 Proof of Lemma 2

Suppose $|D\cap \Psi _{j}|\ge 3$ and we set $x_{j}=0.$ That is, if we do not place a regenerator at node j,  or equivalently we remove from G node j and all edges incident to it, then there are at least three nodes in D each one of which when removed makes the problem infeasible. Hence to obtain a feasible solution each one of these must be equipped with a regenerator. This means that any feasible solution that satisfies $\sum _{i\in D}x_{i}+x_{j}=2$ must lie on the hyperplane $x_{j}=1,$ and $\sum _{i\in D}x_{i}+x_{j}\ge 2,$ therefore, cannot be an FDI. $\square$

1.4 Proof of Lemma 3

We can prove this result, using similar arguments in proof of Lemma 2. $\square$

1.5 Proof of Theorem 2

Given conditions of the theorem, we exhibit |S| linearly independent feasible solutions each one of which satisfies: $\sum _{r\in D}x_{r}+x_{j}=2$. Assume $|D|=k.$ First, for each $i\in D,$ create an |S|-vector $x^{i}$ as follows:

$$\begin{aligned} x_{r}^{i}=\left\{ \begin{array}{ll} 0,&{}\quad \forall r\in D\backslash \{i\}, \\ 1, &{}\quad {\text {otherwise.}} \end{array} \right. \end{aligned}$$

As argued in Theorem 1, each one of these k linearly independent vectors corresponds to a feasible solution and satisfies, for each $i\in D,$ $\sum _{r\in D}x_{r}^{i}+x_{j}^{i}=2.$ Now we create a desired vector $x^{j}$ as follows. First we set $x_{j}^{j}=0,$ and $x_{r}^{j}=1$ for all $r\in S\backslash \{D\cup \{j\}\}.$ Next we set $x_{r}^{j}=1$ for all $r\in D\cap \Psi _{j}.$ By assumption of Lemma 3, $|D\cap \Psi _{j}|\le 2.$ If $|D\cap \Psi _{j}|\ne 2,$ then pick arbitrarily $2-|D\cap \Psi _{j}|$ nodes from $D\backslash \Psi _{j}$ and reset their corresponding x-value to 1. This ensures that $x^{j}$ is a feasible vector and $\sum _{r\in D}x_{r}^{j}=2,$ and hence $\sum _{r\in D}x_{r}^{j}+x_{j}^{j}=2.$ Consider now the $|S|\times (k+1)$ submatrix of these $(k+1)$ feasible solutions written as

$$\begin{aligned} \left[ \begin{array}{cc} I_{1} &{}\quad a \\ 1 &{}\quad 0 \\ \mathbf {1} &{} \mathbf {1} \end{array} \right] , \end{aligned}$$

where the top k rows contain a $k\times k$ identity matrix $I_{1}$. Column a is a k-column with 1 at two places and 0 elsewhere, and corresponds to the k elements of D. Next row corresponds to node j,  and the remaining rows contain all 1’s. As in our Theorem 1, $\mathbf {1}$ is a matrix of all 1’s. Clearly, these $(k+1)$ columns are linearly independent.

Next we create $|S|-(k+1)$ linearly independent vectors, one for each node in $S\backslash \{D\cup \{j\}\},$ which correspond to feasible solutions and satisfy $\sum _{r\in D}x_{r}+x_{j}=2.$ Consider first any node $t\in S\backslash \{D\cup C\}.$ Since $t\notin C$, by definition of C,  there exists a node $i\in D$ such that $t\notin \Phi _{i}.$ Create an |S|-vector $x^{t}$ such that $x_{r}^{t}=0$ for all r in $\{D\cup \{t\}\}\backslash \{i\},$ and 1, otherwise. It is easy to see that $x^{t}$ corresponds to a feasible solution that satisfies $\sum _{r\in D}x_{r}^{t}+x_{j}^{t}=2.$ Construct in this manner $|S\backslash \{D\cup C\}|$ feasible solutions. Finally, consider a node $t\in C\backslash \{j\}.$ We construct a feasible solution vector $x^{t}$ as follows. Its construction is very similar to that of $x^{j}.$ We first set $x_{t}^{t}=0$, and $x_{r}^{t}=1$ for all $r\in S\backslash \{D\cup \{j,t\}\}.$ Recall that by assumptions of Lemma 4, $|\{D\cup \{j\}\}\cap \Psi _{t}|\le 2.$ So we set $x_{r}^{t}=1$ for all $r\in \{D\cup \{j\}\}\cap \Psi _{t}.$ Select arbitrarily any $2-|\{D\cup \{j\}\}\cap \Psi _{t}|$ nodes of $\{D\cup \{j\}\}\backslash \Psi _{t}$ and set the corresponding x-values to 1. All other nodes of D are assigned an x -value of 0. This ensures that $x^{t}$ is a feasible solution and satisfies $\sum _{r\in D}x_{r}^{t}+x_{j}^{t}=2.$ We thus construct $|C\backslash \{j\}|$ solutions in this manner. The submatrix of these $|S|-(k+1)$ vectors, obtained above, can be written as

$$\begin{aligned} \left[ \begin{array}{c} A \\ b \\ \mathbf {1}_{2}-I \end{array} \right] , \end{aligned}$$

where $\mathbf {1}_{2}$ is a $(|S|-k+1)\times (|S|-k+1)$ non-singular matrix of all $1^{\prime }s.$ Concatenating these two submatrices, we get an $|S|\times |S|$ non-singular matrix:

$$\begin{aligned} \left[ \begin{array}{cc} I_{1} &{}\quad a \\ 1 &{}\quad 0 \\ \mathbf {1} &{}\quad \mathbf {1} \end{array} \begin{array}{c} A \\ b \\ \mathbf {1}_{2}-I \end{array} \right] , \end{aligned}$$

and the columns of this matrix provide |S| feasible solutions $\{x^{i},i=1,\ldots , |S|\}$, each one of which lies on the hyperplane $\sum _{r\in D}x_{r}+x_{j}=2.$ This completes our proof. $\square$

1.6 Proof of Lemma 4

If $p\ge 3,$ then condition of Lemma 3 is not satisfied, and $\sum _{i\in D}x_{i}+x_{j}\ge 2$ is not an FDI. First note that $\sum _{i\in D}x_{i}+x_{j}\ge 2$ is implied by $\sum _{i\in D} x_{i}+(p-1)x_{j}\ge p,$ since adding a trivial valid constraint “$(2-p)x_{j}\ge 2-p''$ to this inequality results in $\sum _{i\in D }x_{i}+x_{j}\ge 2.$ Now to show the validity of the stated inequality, suppose $x_{j}=0.$ The inequality reduces it to $\sum _{i\in D}x_{i}\ge p,$ which is a valid inequality since to get a feasible solution with $x_{j}=0$, we must have at least p nodes of D installed with regenerators. If $x_{j}=1$ then the above inequality reduces to the valid inequality $\sum _{i\in D}x_{i}\ge 1.$ $\square$

1.7 Proof of Lemma 5

If $p\ge 3,$ then condition of Lemma 4 is not satisfied, and $\sum _{i\in D}x_{i}+x_{j}\ge 2$ is not an FDI. Again, as argued in Lemma 4, inequality $\sum _{i\in D}x_{i}+x_{j}\ge 2$ is implied by $\sum _{i\in D}x_{i}+x_j+(p-2)x_{t}\ge p$. To show its validity, suppose $x_{t}=0.$ The inequality then reduces to $\sum _{i\in D}x_{i}+x_j\ge p,$ which is a valid inequality since to get a feasible solution with $x_{t}=0$, we must have at least p nodes of $D\cup \{j\}\}$ installed with regenerators. If $x_{t}=1$ then the above inequality reduces to the valid inequality $\sum _{i\in D}x_{i}+x_j\ge 2.$ $\square$