Lagrangean relaxation algorithm for disjoint paths with different path costs

Zeyan Wang; Li Li; Bo Wang

doi:10.1117/12.518805

15 April 2004 Lagrangean relaxation algorithm for disjoint paths with different path costs

Zeyan Wang, Li Li, Bo Wang

Proceedings Volume 5282, Network Architectures, Management, and Applications; (2004) https://doi.org/10.1117/12.518805
Event: Asia-Pacific Optical and Wireless Communications, 2003, Wuhan, China

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(n²)). The efficiency of this algorithm is demonstrated by test examples.

Citation Download Citation

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); https://doi.org/10.1117/12.518805

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available