Constrained Shortest Link-Disjoint Paths Selection: A .
1Constrained Shortest Link-Disjoint Paths Selection:A Network Programming Based ApproachYing Xiao, Student Member, IEEE, Krishnaiyan Thulasiraman, Fellow, IEEE, and Guoliang Xue, SeniorMember, IEEEAbstract— Given a graph G with each link in the graphassociated with two positive weights, cost and delay, we considerthe problem of selecting a set of k link-disjoint paths from anode s to another node t such that the total cost of these pathsis minimum and that the total delay of these paths is not greaterthan a specified bound. This problem, to be called the CSDP(k)problem, can be formulated as an integer linear programming(ILP) problem. Relaxing the integrality constraints results in anupper bounded linear programming problem. We first show thatthe integer relaxations of the CSDP(k) problem and a generalizedversion of this problem to be called the GCSDP(k) problem(in which each path is required to satisfy a specified boundon its delay) both have the same optimal objective value. Inview of this we focus our work on the relaxed form of theCSDP(k) problem called RELAX-CSDP(k). We study RELAXCSDP(k) from the primal perspective using the revised simplexmethod of linear programming. We discuss different issues suchas formulas to identify entering and leaving variables, anticycling strategy, computational time complexity etc., related toan efficient implementation of our approach. We show how toextract from an optimal solution to RELAX-CSDP(k) a set ofk link-disjoint s-t paths which is an approximate solution tothe original CSDP(k) problem. We also derive bounds on thequality of this solution with respect to the optimum. We presentsimulation results that demonstrate that our algorithm is fasterthan currently available approaches. Our simulation results alsoindicate that in most cases the individual delays of the pathsproduced starting from RELAX-CSDP(k) do not deviate in asignificant way from the individual path delay requirements ofthe GCSDP(k) problem.Index Terms— Constrained shortest paths, link-disjoint paths,QoS routing, graph theory, combinatorial optimization, linearprogramming, network optimizationI. I NTRODUCTIONIN this paper we study a discrete optimization problemdefined on graphs or networks (We use the terms ”graph”and ”network” interchangeably). Specifically, we are interestedin selecting a set of paths satisfying certain constraints. Thisproblem is fundamental and arises in several applications. Inthis context we encounter two problems. One of them, calledthe Constrained Shortest Path (CSP) problem, requires thedetermination of a minimum cost path from a source node sto a destination node t such that the delay of the path is withina specified bound. The other problem, denoted as CSDP(k),The work of K. Thulasiraman has been supported by NSF ITR grant ANI0312435. The work of G. Xue has been supported by NSF ITR grant ANI0312635.Ying Xiao and Krishnaiyan Thulasiraman are with University of Oklahoma,Norman, OK 73019, USA (e-mail: ying xiao@ou.edu, thulsi@ou.edu). Guoliang Xue is with Arizonia State University, Tempe, AZ 85287, USA. (e-mail:xue@asu.edu)is to select a set of k link disjoint paths from s to t such thatthe total cost of these paths is minimum and that the totaldelay of these paths is not greater than a specified bound.Both problems are NP-hard [1], [2]. This has led researchersto propose heuristics and approximation algorithms for theseproblems.For a detailed account of the different algorithms for theCSP problem, [2]–[13] may be consulted. Of special interestto us in the context of our work in this paper are [8], [10]–[13].References [8] and [10]–[12] present the LARAC algorithmthat is based on the Lagrangian dual of the CSP problemas well as some generalizations. Reference [11] presents ageneralization of the LARAC algorithm and is applicable togeneral combinatorial optimization problems involving twoadditive metrics. One of such problem is the minimum costspanning tree problem with the restriction that the total delaybeing within a specified limit. Several such constrained discrete optimization problems arise in the VLSI physical designarea. Reference [13] shows that these algorithms are stronglypolynomial. In perhaps the most recent work [14] on theCSP problem, we have studied this problem from a primalperspective.The CSDP(k) problem arises in the context of provisioningpaths that could be used to provide resilience to failures inone or more of these paths. Orda et al. [15] have studied theCSDP(2) problem and have provided several approximationalgorithms. A special case of the CSDP(k) problem whichdoes not have the delay requirement has been studied in [16].The algorithms in [11] and [16] can be integrated to providean approximate solution to the CSDP(k) problem. We call thisthe G-LARAC(k) algorithm.The rest of the paper is organized as follows. In Section IIwe define the CSDP(k) problem and a generalized version ofthis problem called the GCSDP(k) problem. The GCSDP(k)problem requires that the delay of each path in the set oflink-disjoint paths be bounded by a specified value. This is incontrast to the CSDP(k) problem wherein the delay constraintis with respect to the total delay of the paths. However, evenfinding two delay constrained link-disjoint paths is NP-hardand is not approximable within a factor of 2 ² for any ² 0[17]. We first show that the optimal objective values of the LPrelaxations of these two problems have equal value. Hencewe focus our study on the relaxed version of the CSDP(k)problem, namely, the RELAX-CSDP(k) problem. In SectionIII we review the G-LARAC(k) algorithm which is a dualbased approach to solving RELAX-CSDP(k). In Section IVwe introduce a transformation on the CSDP(k) problem. The
2transformed problem will be called the TCSDP(k) problem.We show that the CSDP(k) problem and the TCSDP(k)problem are equivalent. As we show later in the paper thetransformed problem has several properties that enable us toachieve an efficient implementation of our approach. In theremainder of the paper we study the LP relaxation of theTCSDP(k) problem, namely, RELAX-TCSDP(k), using therevised simplex method of linear programming. In SectionV, several properties of basic solutions of RELAX-TCSDP(k)are established. We also show how to extract an approximatesolution to the CSDP(k) problem starting from an optimalsolution to RELAX-TCSDP(k). In Sections VI-VII, the revisedsimplex method and several issues relating to an efficientimplementation are discussed. We also develop an anti-cyclingstrategy and establish the pseudo-polynomial time complexityof the revised simplex method when applied on RELAXTCSDP(k). Simulation results comparing our approach withthe G-LARAC(k) algorithm and the commercially availableCPLEX package are presented in Section VIII. These results demonstrate that our algorithm is faster than currentlyavailable approaches. They also indicate that in most casesthe individual delays of the paths produced starting fromRELAX-CSDP(k) do not deviate in a significant way fromthe individual delay requirements of the GCSDP(k) problem,thereby demonstrating that there is not much loss of generalityin focusing on RELAX-CSDP(k) rather than on the relaxedversion of the more complex GCSDP(k) problem. We conclude in Section IX with a summary of our work and pointingto certain directions for future research.II. C ONSTRAINED S HORTEST L INK -D ISJOINT PATHSS ELECTION P ROBLEMS : F ORMULATIONS , R ELAXATIONS ,AND T HEIR E QUIVALENCEIn this section we first define two classes of link-disjointpaths selection problems. One is a special case of the other.They both admit integer linear programming (ILP) formulations. They are computationally intractable because of theintegrality constraints. For networks involving small numbersof nodes and links, these problems can be solved using anygeneral purpose ILP package. For larger networks, fasteralgorithms are desired. So, we are interested in solving theseproblems after relaxing the integrality requirement and exp
General Constrained Shortest k-Disjoint Paths (GCSDP(k)) Problem: Given two nodes s and t and a positive integer T, the GCSDP(k) problem is to find a set of k(k ‚ 2) link-disjoint s-t paths p1;p2:::;pk such that the delay of each path pi is at most T and the total cost of the k paths is minimum. Constrained Shortest k-Disjoint Paths (CSDP(k .
The classical K -Shortest Paths (KSP) problem, which identifies the k shortest paths in a directed graph, plays an important role in many application domains, such as providing alternative paths for v ehicle routing services. However, the returned k shortest paths may be highly similar, i.e., sharing significant amounts of edges, thus adversely
2.2 Improvements for Shortest Paths There have been a number of works on shortest paths in the past [Ga182], [Jaf80]. The best previously known shortest-paths algorithms is obtained using the SYN- CHRONIZER of to [Awe85]. It requires O(E . V”) mes- sages and O( V. log, V) t ime. (This does not count the
1 Finding Top-k Shortest Paths with Diversity Huiping Liu, Cheqing Jin , Bin Yang, and Aoying Zhou Abstract—The classical K Shortest Paths (KSP) problem, which identifies the kshortest paths in a directed graph, plays an important role in many application domains, such as providing alternative paths for vehicle routing services.
2 Approximating k-Link Shortest Paths Lemma 1. Let p be a shortest k-link path between edges es and et of R. Then, each link of p has an endpoint on an edge of R or goes through a vertex of R. Proof. The proof is by contradiction. Let p be a k-link path between es and et, let l1;l2 and l3 be three consecutive links of p and refer to Figure 2 .
Our algorithm takes the hierarchy-based approach invented by Thorup. Key words. single-source shortest paths, all-pairs shortest paths, undirected graphs, Dijkstra’s algorithm AMS subject classifications. 05C12, 05C85, 68R10 DOI. 10.1137/S0097539702419650 1. Introduction. The problem of computing shortest paths is indisputably one
Dr. Haim Levkowitz Fall, 2007 Graph Algorithms: Chapters 24-25 Part 3: Shortest paths. 2 Shortest Paths Chapter 24: Single-source Chapter 25: All-pairs. 3 Shortest Paths Chapter 24: Single-source. 4 How to find shortest route between two
shortest one. Yen (1971) first introduced a k-shortest path searching method by deleting node from the network, and then several k-shortest algorithms have been suggested. There are two groups of k-shortest path algorithm. The difference is one allow loops in result paths and another don’t. In transportation network the latter is always used .
us88685734 agma 1003-g 1993 us88685738 agma 2008-b 1990 us88685800 agma 6004-f 1988 us88685801 agma 6017-e 1986 us88685804 agma 6033-b 1998 us88685818 agma 9001-a 1986 de88686927 tgl 18790/03 1972-09 us88687103 a-a-20079 1984-04-16 us88687140 a-a-1953 1982-08-31 us88687157 a-a-1669 1982-10-18 us88687212 a-a-55063 1992-08-13 us88687305 a-a-59606 2002-08-23 us88687309 a-a-59606/2 2002-08-23 .
