# Heuristics for Synthesizing Robust Networks with a Diameter Constraint

Authors: Harsha Nagarajan; Peng Wei; Sivakumar Rathinam; Dengfeng Sun
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Robustness of a network in the presence of node or link failures plays an important role in the design of the network. A key factor that quantifies this robustness is the algebraic connectivity of the network. In this paper, the authors address the problem of finding a network that maximizes the algebraic connectivity of the network while ensuring that the length of the shortest path joining any two nodes in the network is within a given bound. This paper presentsk-opt and tabu search heuristics for finding feasible solutions for this network synthesis problem. Computational results are also presented to corroborate the performance of the proposed algorithms.


---

## Body

## 1. Introduction

This paper addresses the problem of finding a network that maximizes the algebraic connectivity of the network while ensuring that the length of the shortest path joining any two nodes in the network is within a given bound. This problem is a simpler version of a system realization problem that arises in several applications including biomedicine, mechanical systems, and the design of Very Large Scale Integrated (VLSI) circuits [1]. We are mainly interested in addressing this problem as it arises in the coordination of Unmanned Aerial Vehicles (UAVs) and in the design of transportation systems.Several UAV applications require a mobile ad hoc network (MANET) to be deployed to facilitate the exchange of information between the vehicles in the network. Each vehicle represents a node in the MANET and the communication links between the vehicles represent the edges in the MANET. The basic problem here is to synthesize a collection of communication links in the MANET so that all the vehicles can communicate with each other, the number of links on a communication path between any two vehicles is at most equal to a given number, and the MANET iswell connected. Algebraic connectivity serves as a measure of well connectedness of a network and can be used to identify good network topologies.The algebraic connectivity of a network is defined as the second, smallest eigenvalue of the Laplacian matrix associated with the network. In applications where a node or a link (an edge) can randomly fail, algebraic connectivity is specifically considered to be a superior measure of connectivity compared to some of the other well-known measures such as the node or edge connectivity. Node (edge) connectivity specifies the minimum number of nodes (edges) that must be removed for the network to be disconnected. The node and the edge connectivity of any spanning tree connecting all the nodes is equal to 1. Therefore, measures such as the node or edge connectivity cannot distinguish between a spanning tree, that is, a star versus a spanning tree, that is, a Hamiltonian path. However, star networks are considered to be more robust towards any random failures of nodes or edges than a Hamiltonian path. Algebraic connectivity serves as a better measure in these cases because the algebraic connectivity of a star network is much greater than the algebraic connectivity of a Hamiltonian path.In addition to UAV applications, algebraic connectivity has also been used as a measure of well connectedness in the design of transportation networks. For example, an air transportation network consists of airports and flight routes between airport pairs [2]. Usually, an undirected graph is used to describe an air transportation network [3–6] where the set of nodes represents all the airports and the set of edges represents all the flight routes. The topology or the structure of this network plays a vital role in determining the average time spent by the flights in the air and at airports, the average number of flights waiting in queues over all the airports, and the average number of hops or legs in a passenger’s itinerary. The network also needs to be robust towards unpredictable node or link failures that may happen due to airline budget cuts, weather hazards, and economic policies. There are several studies [4, 7–9] that have aimed to relate the performance of an air transportation network in terms of delays and failures (as mentioned above) with the topology or the structure of the transportation network. The overall approach here is that if a specific topology of structure is better, then one can develop the required mathematical tools to design a transportation network with the desired topology. Specifically, the authors in [4, 7–9] have shown that one of the factors that characterizes the performance of a network is its algebraic connectivity. The authors in [4] have demonstrated that an air transportation network for the United States with a higher algebraic connectivity exhibited superior performance in terms of average flight times, delays, queue length, and the distance traveled by the passengers. In order to restrict the number of legs or stops incurred by the passengers as they travel, it is important to synthesize a network with additional constraints that limit the number of edges present in the path joining any two nodes in the network.In this paper, we restrict our attention to networks that are spanning trees. We consider the basic mathematical problem of synthesizing a spanning tree that maximizes the algebraic connectivity of the spanning tree subject to a limit on the diameter of the tree. The diameter of a tree is defined as the number of edges present in the longest path connecting any two nodes in the tree. Henceforth, we will refer to this problem as the algebraic connectivity problem. It is well known that this problem is NP-Hard [10]. Finding an optimal solution to this problem seems to be very difficult even for a network with 8 or 9 nodes [1, 11]. For n nodes, the number of distinct spanning trees available to connect all the nodes is nn-2; therefore, for 8 nodes, there are 262144 combinatorial possibilities. As finding an optimal solution seems to be very challenging, we focus on developing good heuristics in this paper.The algebraic connectivity problem has received scant attention in the literature. In [12], the authors consider an unweighted version of the algebraic connectivity problem with no connectivity constraints. In [1], the authors explain the importance of this problem in the context of several applications and present an optimal algorithm to solve the problem with no connectivity constraints. In [13], Wei and Sun study a simpler variant of this optimization problem which aims to add k additional edges to strengthen the network. In [11], the authors solve the algebraic connectivity problem in the context of UAV applications. The following are the contributions of this paper.(i)
We develop heuristics based onk-opt and tabu search methods to find good feasible solutions to the problem.(ii)
We present computational results to corroborate the performance of the proposed algorithms. These results indicate that the 3-opt heuristic performed the best among the proposed heuristics while the 2-opt heuristic provided a good trade-off between finding good solutions and the required computation time.The rest of the paper is organized as follows. In Section2, we formulate the problem. Local search heuristics like k-opt and tabu search are presented in Sections 3 and 4, respectively. In Section 5, we evaluate the performance of our algorithms via simulations. Section 6 concludes this paper.


## 2. Problem Formulation

Consider an undirected graphG:=(V;E) with V denoting all the n nodes and E representing all the edges in the graph. Each edge in the graph is associated with a weight which acts as a proxy to the likeliness of the edge to fail [14]. An edge is assigned a larger weight if the edge is a stronger link and is not likely to fail; on the other hand, an edge is assigned a relatively smaller weight if the edge is more likely to fail. Let we represent the edge weight associated with the edge e∈E. For any edge e∈E, let xe represent a binary variable that specifies if edge e is present in the chosen network or not; xe=1 if e is chosen and xe=0 otherwise. Let the incidence vector, x∈{0,1}|E|, denote the entire network with the component xe corresponding to e∈E. Let ci denote the ith column of the identity matrix In of size |V|=n. If the nodes i and j are connected using edge e, let Le=we(ci-cj)⊗(ci-cj) where ⊗ represents the tensor product. Using this notation, the Laplacian [4, 12, 15] of the chosen network may be defined as follows:
(1)L(x)=∑e∈ExeLe.Letλ2(L(x)) denote the algebraic connectivity of the chosen network. To simplify the problem, we restrict our search for optimal networks from the set of all the spanning trees. A spanning tree connects all the nodes in the network and contains exactly |V|-1 edges. As stated by Fiedler in [15], a graph is connected if and only if the algebraic connectivity of the graph is greater than zero. Therefore, the algebraic connectivity of any spanning tree will be greater than zero and the algebraic connectivity of any disconnected graph will be equal to zero. Hence, the problem of choosing a spanning tree while maximizing its algebraic connectivity can be posed as follows:
(2)maximizexλ2(L(x)),
subject to(3a)∑e∈Exe=|V|-1,(3b)x∈{0,1}|E|,(3c)δij(x)≤D∀i,j∈V,where δij(x) denotes the number of edges in the shortest path joining any two nodes i and j in the network represented by x and D is the limit on the diameter of the network. Using the results in [1, 4, 12], the above problem can be formulated as a non-linear program with the diameter constraint as follows:
(4)γ*=maximizex,γγ,
subject to(5a)L(x)⪰γ(In-e0⊗e0),(5b)∑e∈E‍xe=|V|-1,(5c)x∈{0,1}|E|,(5d)δij(x)≤D∀i,j∈V,where e0 is the normalized eigenvector corresponding to the first eigenvalue of x, and for any two square matrices A,B with the same dimensions, A⪰B if and only if A-B is a positive semidefinite matrix.


## 3.k-opt Heuristic

k-opt heuristics were initially proposed for solving routing problems in [16]. In this heuristic, a feasible spanning tree is first generated by choosing any star graph with one of the vertices having a degree equal to |V|-1. Then, a new spanning tree in a local neighborhood of the current, feasible solution is chosen such that the new solution is feasible and has a larger algebraic connectivity. This procedure is iterated until a better spanning tree cannot be found.Suppose𝒯1 and 𝒯2 are two feasible solutions for the algebraic connectivity problem. Then, 𝒯2 is said to be in the k-exchange neighborhood of 𝒯1 if 𝒯2 can be obtained by replacing k edges in 𝒯1. In a k-opt exchange, we find a (new) feasible solution in the k-exchange neighborhood of the current solution and replace the current solution with this new solution if the algebraic connectivity of the new solution is larger than the algebraic connectivity of the current solution. In summary, a k-opt heuristic starts with an initial feasible solution and iteratively applies a k-opt exchange until no improvements can be made.There are two main steps in thisk-opt exchange: choosing a collection of k edges to remove from the current solution and then reconnecting the resulting, disjoint components with a new collection of k edges. Clearly, there are several combinations of k edges that can be removed from (or added to) a given solution. Therefore, choosing an efficient procedure for the deletion and addition of edges is critical for developing a relatively fast algorithm. In the following subsections, we provide procedures for implementing these steps.


### 3.1. Selecting a Collection ofk-Edge Combinations to Delete

The basic idea here is to list all the possible combinations ofk-edges that can be deleted from the current feasible solution, assign a value for each combination, rank the combinations based on these values, and then choose a subset of these combinations for further processing. We assign a value to a combination of edges by first asking the following basic question: which are the k edges that need to be deleted from the current solution 𝒯0 so that 𝒯0 (possibly) incurs the smallest reduction in the algebraic connectivity? To answer this question, let 𝒯0∖{e} denote the graph obtained by deleting an edge e from the graph 𝒯0 and let the Laplacian of the graph, 𝒯0∖{e}, be denoted by L(𝒯0-e). By variational characterization, we have the following inequality:(6a)λ2(L(𝒯0-e))≤v′L(𝒯0-e)v∀v∈𝒱(6b)=v′L(𝒯0)v-v′Lev∀v∈𝒱(6c)=v′L(𝒯0)v-we(vi-vj)2∀v∈𝒱,where 𝒱∶={v:∑i‍vi=0,∥v∥=1}, we is the weight of edge e=(i,j), and vi represents the ith component of the vector v. One may observe from the above inequality that by choosing an edge with a minimum value of we(vi-vj)2, the upper bound on the algebraic connectivity of the graph, 𝒯0∖{e}, is kept as high as possible. Also, we numerically observed that we(vi-vj)2 was kept to a minimum by choosing v as the eigenvector corresponding to the maximum eigenvalue of L(𝒯0). Hence, for any combination of k edges denoted by S, we assign a value given by ∑e=(i,j)∈S‍we(vi-vj)2. Then, we rank all the combinations based on the increasing values and choose a subset of these combinations that corresponds to the lowest values. In this work, the fraction of combinations that is considered for deletion is specified through a parameter called the edge deletion factor. The edge deletion factor is defined as the ratio of the number of k-edge combinations considered for deletion to the maximum number of possible k-edge combinations (i.e., (n-1k)). We will discuss more about this factor later in the simulations section.


### 3.2. Selecting a Collection ofk-Edge Combinations to Add

In the case of spanning trees, after removingk edges, we are guaranteed to have a graph 𝒯~0 with exactly k+1 connected components {C1,C2,C3,…,Ck+1}; therefore, by suitably adding a collection of k edges connecting all the k+1 components in 𝒯~0, one is guaranteed to obtain a spanning tree, 𝒯1. Also, we add these edges while ensuring that the resulting tree satisfies the diameter constraints. The new feasible solution 𝒯1 is considered for replacing 𝒯0 if it has a larger algebraic connectivity than 𝒯0.As in the edge-deletion procedure, checking for every addition ofk edges may be computationally intensive for large instances. Therefore, we develop another edge ranking procedure for adding edges as follows. Let 𝒯~0∪{e} denote the graph obtained by adding an edge e=(i,j) to the graph 𝒯~0 and let the Laplacian of the graph, 𝒯~0∪{e}, be denoted by L(𝒯~0+e). By variational characterization, we have the following inequality:(7a)λ2(L(𝒯~0+e))≤v′L(𝒯~0+e)v∀v∈𝒱(7b)=v′L(𝒯~0)v+v′Lev∀v∈𝒱(7c)=v′L(𝒯~0)v+we(vi-vj)2∀v∈𝒱.One may observe from the aforementioned inequality that by choosing an edge with a maximum value ofwe(vi-vj)2, the upper bound on the algebraic connectivity of the graph 𝒯~0∪{e} is kept as high as possible. Just like the edge deletion step, let v be the eigenvector corresponding to the maximum eigenvalue of L(𝒯~0). Hence, for any combination of k edges denoted by S, we assign a value given by ∑e=(i,j)∈S‍we(vi-vj)2. Then, we rank all the combinations based on decreasing values and choose a subset of these combinations that corresponds to the highest values. The number of combinations that are considered for addition is another parameter and can be specified based on the problem instances.A pseudocode of thek-opt exchange is outlined in Algorithm 1. An illustration of such a procedure on one such pair (k=2) of edges for a spanning tree with 4 nodes is shown in Figure 1. This exchange is iteratively applied on the current solution until no improvements can be made.Algorithm 1:
k-opt exchange.
(1) Input: D (positive integer)
(2)𝒯0← Initial feasible solution satisfying diameter constraints
(3)λ0←λ2(L(𝒯0))
(4)Edel← Subset of k-edge combinations considered for possible deletion as obtained by the edge ranking procedure in
Section 3.1
(5)for each edge combination in Edel  do
(6) Delete the k edges present in the edge combination to obtain connected components C1,C2,C3,…,Ck+1
(7) Eadd← Subset of k-edge combinations considered for possible addition as obtained by the edge ranking procedure
in Section 3.2
(8)  Let 𝒯1 be the spanning tree which is feasible and has the largest connectivity obtained from adding the edges in an
edge combination from Eadd
(9)  if  λ2(L(𝒯1))>λ0  then
(10)𝒯0←𝒯1
(11)λ0←λ2(L(𝒯1))
(12)end if
(13)end for
(14)  Output𝒯0 as the (new) current solutionFigure 1
An example illustrating a 2-opt exchange.


## 3.1. Selecting a Collection ofk-Edge Combinations to Delete

The basic idea here is to list all the possible combinations ofk-edges that can be deleted from the current feasible solution, assign a value for each combination, rank the combinations based on these values, and then choose a subset of these combinations for further processing. We assign a value to a combination of edges by first asking the following basic question: which are the k edges that need to be deleted from the current solution 𝒯0 so that 𝒯0 (possibly) incurs the smallest reduction in the algebraic connectivity? To answer this question, let 𝒯0∖{e} denote the graph obtained by deleting an edge e from the graph 𝒯0 and let the Laplacian of the graph, 𝒯0∖{e}, be denoted by L(𝒯0-e). By variational characterization, we have the following inequality:(6a)λ2(L(𝒯0-e))≤v′L(𝒯0-e)v∀v∈𝒱(6b)=v′L(𝒯0)v-v′Lev∀v∈𝒱(6c)=v′L(𝒯0)v-we(vi-vj)2∀v∈𝒱,where 𝒱∶={v:∑i‍vi=0,∥v∥=1}, we is the weight of edge e=(i,j), and vi represents the ith component of the vector v. One may observe from the above inequality that by choosing an edge with a minimum value of we(vi-vj)2, the upper bound on the algebraic connectivity of the graph, 𝒯0∖{e}, is kept as high as possible. Also, we numerically observed that we(vi-vj)2 was kept to a minimum by choosing v as the eigenvector corresponding to the maximum eigenvalue of L(𝒯0). Hence, for any combination of k edges denoted by S, we assign a value given by ∑e=(i,j)∈S‍we(vi-vj)2. Then, we rank all the combinations based on the increasing values and choose a subset of these combinations that corresponds to the lowest values. In this work, the fraction of combinations that is considered for deletion is specified through a parameter called the edge deletion factor. The edge deletion factor is defined as the ratio of the number of k-edge combinations considered for deletion to the maximum number of possible k-edge combinations (i.e., (n-1k)). We will discuss more about this factor later in the simulations section.


## 3.2. Selecting a Collection ofk-Edge Combinations to Add

In the case of spanning trees, after removingk edges, we are guaranteed to have a graph 𝒯~0 with exactly k+1 connected components {C1,C2,C3,…,Ck+1}; therefore, by suitably adding a collection of k edges connecting all the k+1 components in 𝒯~0, one is guaranteed to obtain a spanning tree, 𝒯1. Also, we add these edges while ensuring that the resulting tree satisfies the diameter constraints. The new feasible solution 𝒯1 is considered for replacing 𝒯0 if it has a larger algebraic connectivity than 𝒯0.As in the edge-deletion procedure, checking for every addition ofk edges may be computationally intensive for large instances. Therefore, we develop another edge ranking procedure for adding edges as follows. Let 𝒯~0∪{e} denote the graph obtained by adding an edge e=(i,j) to the graph 𝒯~0 and let the Laplacian of the graph, 𝒯~0∪{e}, be denoted by L(𝒯~0+e). By variational characterization, we have the following inequality:(7a)λ2(L(𝒯~0+e))≤v′L(𝒯~0+e)v∀v∈𝒱(7b)=v′L(𝒯~0)v+v′Lev∀v∈𝒱(7c)=v′L(𝒯~0)v+we(vi-vj)2∀v∈𝒱.One may observe from the aforementioned inequality that by choosing an edge with a maximum value ofwe(vi-vj)2, the upper bound on the algebraic connectivity of the graph 𝒯~0∪{e} is kept as high as possible. Just like the edge deletion step, let v be the eigenvector corresponding to the maximum eigenvalue of L(𝒯~0). Hence, for any combination of k edges denoted by S, we assign a value given by ∑e=(i,j)∈S‍we(vi-vj)2. Then, we rank all the combinations based on decreasing values and choose a subset of these combinations that corresponds to the highest values. The number of combinations that are considered for addition is another parameter and can be specified based on the problem instances.A pseudocode of thek-opt exchange is outlined in Algorithm 1. An illustration of such a procedure on one such pair (k=2) of edges for a spanning tree with 4 nodes is shown in Figure 1. This exchange is iteratively applied on the current solution until no improvements can be made.Algorithm 1:
k-opt exchange.
(1) Input: D (positive integer)
(2)𝒯0← Initial feasible solution satisfying diameter constraints
(3)λ0←λ2(L(𝒯0))
(4)Edel← Subset of k-edge combinations considered for possible deletion as obtained by the edge ranking procedure in
Section 3.1
(5)for each edge combination in Edel  do
(6) Delete the k edges present in the edge combination to obtain connected components C1,C2,C3,…,Ck+1
(7) Eadd← Subset of k-edge combinations considered for possible addition as obtained by the edge ranking procedure
in Section 3.2
(8)  Let 𝒯1 be the spanning tree which is feasible and has the largest connectivity obtained from adding the edges in an
edge combination from Eadd
(9)  if  λ2(L(𝒯1))>λ0  then
(10)𝒯0←𝒯1
(11)λ0←λ2(L(𝒯1))
(12)end if
(13)end for
(14)  Output𝒯0 as the (new) current solutionFigure 1
An example illustrating a 2-opt exchange.


## 4. Tabu Search Heuristic

In this section, we present a tabu search heuristic (Algorithm2) for finding good feasible solutions for the algebraic connectivity problem. Similar to the k-opt heuristic, the tabu search heuristic first starts with a feasible solution s and attempts to construct a candidate feasible solution s′, in the neighborhood of s with a larger algebraic connectivity (we will later explain how we choose the neighborhoods for the tabu search). If the algebraic connectivity of s′ (λ2(s′)) is larger than the best known value (λ2*), s′ is set as the current feasible solution (i.e., s:=s′) and λ2* is updated (steps 9–13 in the algorithm). If the algebraic connectivity of s′ is at most equal to λ2*, s′ is set as the current feasible solution but no updates are made to λ2* (steps 15–19 in the algorithm). The above procedure is then repeated again until the number of iterations reaches a maximum limit.Algorithm 2:Tabu search heuristic.
Lets* be the best optimal solution found by the algorithm and let λ2* be the algebraic connectivity of s*. Let m denote the
number of edges in the initial feasible solution (i.e.,m:=|V|-1). Also, let MaxIterations represent the maximum number
of iterations allowed in the tabu heuristic.
(1) 𝒯0← Initial feasible solution satisfying diameter constraints
(2)s:=𝒯0, λ2*:=λ2(𝒯0), s*:=𝒯0, T is an empty tabu list which can store at most m solutions.
(3)for  i=1 to MaxIterations  do
(4) for  edge ek in s  do
(5)   Construct the set of edges N(s,ek)
(6)  end for
(7)  for  any spanning tree s′ such that s′ contains exactly one edge from each of the sets in {N(s,e1),…,N(s,ek)}  do
(8)   if  s′ is feasible  then
(9)    if  λ2(s′)>λ2*  then
(10)s=s′
(11)T←T⋃{s′}; Tonly stores at mostmsolutions from iterationsi-m+1,…,i-1,i
(12)λ2*=λ2(s), s*=s
(13)     break
(14)else
(15)if  s′ is not in T  then
(16)s=s′
(17)T←T⋃{s′}; Tonly stores at mostmsolutions from iterationsi-m+1,…,i-1,i
(18)      break
(19)end if
(20)end if
(21)end if
(22)end for
(23)if  s≠s′then
(24)   break //The heuristic terminates here if there is no feasible trees′in the neighborhood ofsor if every feasibles′
with a lower algebraic connectivity (<λ2*) is already in the tabu list.
(25)end if
(26)end for
(27) outputλ2* and s*There are two features that makes the tabu search heuristic different from thek-opt heuristic. Firstly, unlike the k-opt heuristic which aims to make an exchange only if a better solution is found, the tabu search allows for the heuristic to move to solutions that may have a smaller algebraic connectivity than the current best solution. Even though there may not be any improvement in the short run, the tabu search heuristic can end up finding better solutions as the number of iterations increases. Secondly, in any iteration, s′ is set as the current feasible solution only if s′ has not been encountered in any of the previous m iterations. This is accomplished by creating a tabu list and storing all the recent m feasible solutions that have been previously considered by the algorithm in this list. Therefore, when the algebraic connectivity of s′ is found to be at most equal to λ2*, s′ is set as the current feasible solution only if s′ is not present in the tabu list.The overall tabu search heuristic is presented in Algorithm2. In the remainder of this subsection, we explain how the local neighborhoods are chosen for the current feasible solution s. Suppose ei is the ith edge in s. Let the edge ei join vertices v1 and v2 in the solution s. Also, define N(s,ei) as the set of all the edges that are incident on v1 or v2 but not present in s. Then, the neighborhood of the current solution s consists of any solution s′ such that there is exactly one edge present in s′ from N(s,ei) for i=1,…,|V|-1.


## 5. Computational Results

Thek-opt and tabu search heuristics were implemented in MATLAB. The bound on the diameter of a feasible tree was set to four (D=4). The diameter of a tree is found by implementing the well-known Floyd-Warshall algorithm [17]. To check for feasibility, we find the diameter of the given tree using the Floyd-Warshall algorithm and verify if this diameter is at most equal to the prescribed bound. For the tabu search heuristic, the size of the tabu search list was set to 20 and the parameter MaxIterations was set to 100.For thek-opt heuristic, we set the edge deletion factor (Section 3.1) to be equal to 0.15 in all the simulations. We chose this value based on the simulation results shown in Figure 2. This figure shows the average algebraic connectivity of the final solution (and the computation time) obtained using the 3-opt heuristic as a function of the edge deletion factor. We observed that there was not much improvement in the quality of the feasible solutions beyond a value of 0.15 (for the edge deletion factor) even for large instances (n=30,40). Hence, we chose 0.15 as the edge deletion factor. Also, we set the number of combinations of edges to be added (Section 3.2) to be at most equal to 5k. For 3-opt, this parameter was set to 125. We chose this value for 3-opt based on the simulation results shown in Figure 3. For 2-opt, this parameter was set to 25 after performing similar simulations.Average values of the algebraic connectivity (a) and computation times (b) obtained as a function of the edge deletion factor using the 3-opt heuristic over ten instances. In these computations, the maximum number of edge combinations considered for addition between any two components was set to 125.
(a)
(b)The average algebraic connectivity (a) and computation times (b) obtained as a function of the maximum number of edge combinations considered for addition between any two components in the 3-opt heuristic over ten instances. In these computations, the edge deletion factor was set to 0.15.
(a)
(b)The semidefinite programming toolboxes (Yalmip and Sedumi) in MATLAB could not solve the proposed formulation (B.1) with the semidefinite and diameter constraints even for instances with 5 nodes primarily due to inefficient memory management. Therefore, Algorithm 3 was implemented to find an optimal solution for instances up to 8 nodes. For more than 8 nodes, the algorithm in the appendix could not find an optimal solution in a reasonable amount of run time. This algorithm was implemented in C++ programming language and the resulting Integer Linear Programs (ILPs) were solved using CPLEX 12.2 with all the solver options set to default. All the developed algorithms were run on a Dell Precision T5500 workstation (Intel Xeon E5630 processor @ 2.53 GHz, 12 GB RAM).Algorithm 3:Synthesizing robust networks with maximum algebraic connectivity subject to diameter constraints.
Let𝔉 be a set of cuts which must be satisfied by any feasible solution
(1)Input: A graph G=(V,E), we, r, D, and a finite number of unit vectors, vi,i=1,…,M
(2)Choose any spanning tree satisfying the diameter constraint as an initial feasible solution, x*
(3)λ^←λ2(L(x*))
(4)loop
(5) 𝔉←∅
(6)  Replace the semi-definite constraint in (B.1) with (viT(L(x))vi)≥λ^(viTI~nvi)∀i=1,…,M, and with additional
constraint, x satisfying 𝔉 and solve the ILP.
(7)  if  the above ILP is infeasible  then
(8)   break loop  {x* is the optimal solution}
(9)  else
(10)x*← solution to the above ILP
(11)γ*←λ2(L(x*))
(12)if  L(x*)⋡γ*(I~n)  then
(13)    Augment𝔉 with a constraint (v*TL(x*)v*)≥γ*(v*TI~nv*) where v* is the eigenvector corresponding to a negative
eigenvalue of L(x*)-γ*I~n.
(14)    Go to step 6.
(15)end if
(16)end if
(17)λ^←λ^+ϵ{let ϵ be a small number}
(18)end loopLet us now compare the deviation of the solutions found by the algorithms with respect to the optimal solution. We define deviation (in %) as((λ2*-λ2heuristic)/λ2*)×100 where λ2heuristic denotes the algebraic connectivity of the solution found by the heuristic and λ2* represents the optimum. The results shown in Table 1 are for 10 random instances generated for networks with 8 nodes. Based on the results in Table 1, we observed that the average run time to obtain an optimal solution was around 371 seconds. Also, it can be seen that the k-opt (k=2,3) and tabu search heuristic found optimal solutions for all problem instances with 8 nodes. Each of the heuristics ran within a fraction of a second for each of the instances with 8 nodes. Instance 1 of Table 1 is pictorially shown in Figure 4.Table 1
Comparison of the deviation of the solutions found by the heuristics for networks with 8 nodes.λ2* is the optimal algebraic connectivity.
No.
Optimal solution
k-opt search (k = 2, 3)
Tabu search
λ
2
*
Time (sec)
λ
2
k
opt
Deviation (%)
λ
2
tabu
Deviation (%)
1
3.9712
180.57
3.9712
0.00
3.9712
0.00
2
4.3101
408.10
4.3101
0.00
4.3101
0.00
3
3.9297
621.85
3.9297
0.00
3.9297
0.00
4
3.5275
216.79
3.5275
0.00
3.5275
0.00
5
3.8753
470.63
3.8753
0.00
3.8753
0.00
6
3.7972
342.14
3.7972
0.00
3.7972
0.00
7
3.7125
377.47
3.7125
0.00
3.7125
0.00
8
3.9205
313.12
3.9205
0.00
3.9205
0.00
9
3.7940
341.84
3.7940
0.00
3.7940
0.00
10
3.8923
316.86
3.8923
0.00
3.8923
0.00
Average
0.00
0.00A network with all possible edges connecting 8 nodes including edge weights is shown in (a). (b) represents the initial feasible solution which is a star graph. (c) represents an optimal network which also happens to be the solution found by the 2-opt, 3-opt, and tabu search methods.
(a)
Complete network
(b)
λ
2
initial = 2.2045
(c)
λ
2
tabu,λ22opt,λ23opt = 3.9712For more than 8 nodes, we used the heuristics to generate feasible solutions for the algebraic connectivity problem. In the remainder of this section, we compare the results from thek-opt and tabu search heuristics. As previously mentioned in the paper, choosing an initial solution for the heuristics is relatively straightforward; we choose a star graph with the largest algebraic connectivity (λ2initial) as an initial feasible solution. A sample initial feasible solution is shown in part (b) of Figure 4.For more than 8 nodes, we inferred the deviation of a solution for an instance by comparing it with the solution obtained by using the 3-opt heuristic for the same instance. Specifically, the deviation of a solution is defined as((λ23opt-λ2heuristic)/λ23opt)×100 where λ23opt is the algebraic connectivity of a solution obtained by using the 3-opt heuristic. For each problem size, the average deviation and computation time obtained for the 10 instances is shown in Table 2. For each of the instances, the solution obtained by the 3-opt heuristic had the largest algebraic connectivity.Table 2
Comparison of 3-opt, 2-opt, and tabu search heuristic solutions for various problem sizes. Here, the deviation was averaged over ten random instances for eachn.
n
3-opt
2-opt
Tabu
Deviation (%)
Time (sec)
Deviation (%)
Time (sec)
Deviation (%)
Time (sec)
10
0
0.29
0.00
0.10
0.00
0.77
15
0
3.06
0.01
0.52
1.52
9.36
20
0
16.32
0.27
1.65
1.78
25.58
25
0
60.38
0.60
3.59
1.88
60.19
30
0
274.93
2.07
12.13
3.12
144.92
35
0
480.15
2.02
37.85
2.77
313.20
40
0
1016.99
5.62
57.28
2.48
3470.71
45
0
2309.60
7.10
116.09
5.10
4272.58
50
0
4219.17
1.38
139.99
3.55
6675.32
55
0
6798.34
6.98
350.83
4.90
8654.29
60
0
8974.46
7.97
505.36
6.06
10049.10From the results in Table2, it is clear that the 2-opt heuristic performed better than the tabu search for medium sized instances (up to 30 nodes). For larger problems (40, 45, 55, and 60 nodes), we observed that the quality of the solutions found by the tabu search was better compared to the 2-opt heuristic. In summary, we observe that the 2-opt heuristic provides a good trade-off between obtaining good feasible solutions and the required computation time. Figure 5 illustrates the solutions obtained using the k-opt and tabu search heuristic for a 40 nodes problem. Also, as shown in Table 3, we observed that the maximum deviation (out of 10 instances) of the 2-opt solutions remained lower than that of tabu search for instances up to 30 nodes. For large instances (35, 40, 45, 55, and 60 nodes), the maximum deviation for tabu search remained lower that that of 2-opt solutions. Overall, the tabu search heuristic performed better than the 2-opt search heuristic for most of the large instances.Table 3
Comparison of maximum deviations computed over ten random instances for eachn for 2-opt and tabu search heuristic.
n
Maximum deviation (%)
2-opt
Tabu
10
0.00
0.00
15
0.08
6.67
20
2.73
10.86
25
4.92
6.36
30
7.56
9.07
35
12.59
7.64
40
17.89
8.91
45
15.41
12.23
50
5.10
8.68
55
17.56
11.47
60
16.92
13.912-opt, 3-opt exchange, and tabu search solutions for a network with 40 nodes whereD=4.
(a)
2-opt exchange,λ22opt=21.4088
(b)
Tabu search,λ2tabu=25.0408
(c)
3-opt search,λ23opt=26.0731


## 6. Conclusions

We studied design methods to maximize the robustness of a network in the presence of diameter constraints. Algebraic connectivity is used to measure the robustness of the network. Our design methods mainly involve the development of heuristics. Our first method, thek-opt heuristic, aims to iteratively search for better solutions by performing an exchange of edges in each iteration. Unlike the k-opt heuristic, our second method (the tabu search heuristic) iteratively moves to solutions that may have a lower algebraic connectivity in the short run but could find better solutions as the number of iterations increases. Computational results suggested that the 3-opt heuristic performed the best while the 2-opt heuristic provided a good trade-off between finding good solutions and the required computation time. There are several future directions for this work. One research direction would be to generalize the network synthesis problem to include more connectivity constraints. Another research direction would be to compare the performance of the developed algorithms in a simulation setting similar to the one in [4] and test the performance in the presence of node or edge failures.



---

*Source: 326963-2014-01-05.xml*