TY - JOUR

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

AU - Andreas, April K.

AU - Smith, J. Cole

AU - Kucukyavuz, Simge

N1 - Funding Information:
Acknowledgements The authors are grateful for the remarks made by two anonymous referees, which helped improve the presentation and contribution of the paper. The authors also gratefully acknowledge the support of the Office of Naval Research under Grant Number N00014-03-1-0510 and the Air Force Office of Scientific Research under Grant Number F49620-03-1-0377
Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.

PY - 2008/12

Y1 - 2008/12

N2 - 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.

AB - 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.

KW - Branch-and-price-and-cut

KW - Network optimization

KW - Nonconvex optimization

KW - Reliability

UR - http://www.scopus.com/inward/record.url?scp=54949117240&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=54949117240&partnerID=8YFLogxK

U2 - 10.1007/s10898-007-9254-x

DO - 10.1007/s10898-007-9254-x

M3 - Article

AN - SCOPUS:54949117240

VL - 42

SP - 443

EP - 466

JO - Journal of Global Optimization

JF - Journal of Global Optimization

SN - 0925-5001

IS - 4

ER -