Branch-and-price-and-cut algorithms for solving the reliable h-paths problem

Branch-and-price-and-cut algorithms for solving the reliable h-paths problem

0.00 Avg rating0 Votes
Article ID: iaor20097195
Country: Netherlands
Volume: 42
Issue: 4
Start Page Number: 443
End Page Number: 466
Publication Date: Dec 2008
Journal: Journal of Global Optimization
Authors: , ,
Abstract:

We examine a routing problem in which network arcs fail according to independent failure probabilities. The reliable h–path routing problem seeks to find a minimum–cost set of h ≥ 2 arc–independent paths from a common origin to a common destination, such that the probability that at least one path remains operational is sufficiently large. For the formulation in which variables are used to represent the amount of flow on each arc, the reliability constraint induces a nonconvex feasible region, even when the integer variable restrictions are relaxed. Prior arc–based models and algorithms tailored for the case in which h = 2 do not extend well to the general h–path problem. Thus, we propose two alternative integer programming formulations for the h–path problem in which the variables correspond to origin–destination paths. Accordingly, we develop two branch–and–price–and–cut algorithms for solving these new formulations, and provide computational results to demonstrate the efficiency of these algorithms.

Reviews

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