Translator Disclaimer
15 April 2004 Lagrangean relaxation algorithm for disjoint paths with different path costs
Author Affiliations +
Proceedings Volume 5282, Network Architectures, Management, and Applications; (2004)
Event: Asia-Pacific Optical and Wireless Communications, 2003, Wuhan, China
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.
© (2004) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Zeyan Wang, Li Li, and Bo Wang "Lagrangean relaxation algorithm for disjoint paths with different path costs", Proc. SPIE 5282, Network Architectures, Management, and Applications, (15 April 2004);

Back to Top