Mathematical programming algorithms for two-path routing problems with reliability considerations

April K. Andreas, J. Cole Smith

Research output: Contribution to journalArticle

14 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)553-564
Number of pages12
JournalINFORMS Journal on Computing
Volume20
Issue number4
DOIs
StatePublished - Jan 1 2008
Externally publishedYes

Keywords

  • Algorithms
  • Bound
  • Branch
  • Graphs: Theory
  • Integer
  • Networks
  • Nonlinear
  • Programming

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Mathematical programming algorithms for two-path routing problems with reliability considerations'. Together they form a unique fingerprint.

  • Cite this