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

April K. Andreas, J. Cole Smith, Simge Küçükyavuz

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)443-466
Number of pages24
JournalJournal of Global Optimization
Volume42
Issue number4
DOIs
StatePublished - Dec 1 2008
Externally publishedYes

Keywords

  • Branch-and-price-and-cut
  • Network optimization
  • Nonconvex optimization
  • Reliability

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research
  • Control and Optimization
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Branch-and-price-and-cut algorithms for solving the reliable h-paths problem'. Together they form a unique fingerprint.

Cite this