Share Email Print

Proceedings Paper

Lagrangean relaxation algorithm for disjoint paths with different path costs
Author(s): Zeyan Wang; Li Li; Bo Wang
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

To improve the reliability of the increasing network two disjoint paths should be found between a given source and a given destination. The problem of finding two minimum cost node-disjoint/edge-disjoint paths with different costs in a directed network can be formulated as a linear integer programming problem minimizing the sum of the costs on the edges in two paths, which is strongly NP-complete problem. Linear relaxation programming which relaxes the integer variables in the original programming is often applied to solve this NP problem. Comparing with linear relaxation programming, Lagrangean relaxation affords a lower bound of the objective value of original programming. Based on this a Lagrangean relaxation method for solving two disjoint paths is presented after a mathematical programming model of the problem is established. By using a modified subgradient optimization technology a new algorithm to solve the Lagrangean relaxation is put forward. The complexity of the proposed algorithm is as same as the Dijkstra’s algorithm (O(n2)). The efficiency of this algorithm is demonstrated by test examples.

Paper Details

Date Published: 15 April 2004
PDF: 8 pages
Proc. SPIE 5282, Network Architectures, Management, and Applications, (15 April 2004); doi: 10.1117/12.518805
Show Author Affiliations
Zeyan Wang, PLA Univ. of Science and Technology (China)
Li Li, PLA Univ. of Science and Technology (China)
Bo Wang, Southwest Jiaotong Univ. (China)

Published in SPIE Proceedings Vol. 5282:
Network Architectures, Management, and Applications
S. J. Ben Yoo; Kwok-wai Cheung; Yun-Chur Chung; Guangcheng Li, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?