Mathematical Programming Algorithms for Two-Path Routing Problems with Reliability Considerations

Mathematical Programming Algorithms for Two-Path Routing Problems with Reliability Considerations

0.00 Avg rating0 Votes
Article ID: iaor200952636
Country: United States
Volume: 20
Issue: 4
Start Page Number: 553
End Page Number: 564
Publication Date: Sep 2008
Journal: INFORMS Journal On Computing
Authors: ,
Keywords: programming: mathematical
Abstract:

Most traditional routing problems assume perfect operability of all arcs and nodes. However, when independent arc failure probabilities exist, a secondary objective must be present to retain some measure of expected functionality, introducing nonlinear, nonconvex constraints. We examine the robust two–path problem, which seeks to establish two paths between a source and destination node wherein at least one path must remain fully operable with some threshold probability. We consider the case where both paths must be arc disjoint and the case where arcs can be shared between the paths. We examine various strategies for solving the resulting nonlinear integer program, including pruning, coefficient tightening, lifting, and branch–and–bound partitioning schemes. We discuss the advantages and disadvantages of these methods and conclude with computational results.

Reviews

Required fields are marked *. Your email address will not be published.