Minimum Cost Paths with Survivability Considerations

Event Details
  • Date/Time:
    • Monday January 24, 2005
      10:00 am - 10:59 pm
  • Location: Rm. 228 Main Bldg
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
Barbara Christopher
Industrial and Systems Engineering
Contact Barbara Christopher

Summary Sentence: Minimum Cost Paths with Survivability Considerations

Full Summary: Minimum Cost Paths with Survivability Considerations

In this talk, we examine a directed network in which each arc is associated with a nonnegative cost and a reliability value (independent of all other arc reliabilities). Hence, the total probability that some path in the network remains operational is the product of its arc reliabilities. The general problem that we consider seeks to determine a
minimum-cost set of paths from an origin to a destination in the network such that at least one path remains operational with sufficiently large probability. While this problem is solvable in pseudo-polynomial time by
an adaptation of Dijkstra's shortest path algorithm for the case in which one origin-destination path is required, it becomes strongly NP-hard for
the case in which two origin-destination paths are required. We examine the cause for this added complexity, and model the two-path problem by means of a nonlinear-mixed-integer program. We then provide a continuous
branch-and-bound scheme to optimally solve this problem, for both the case in which the paths must be arc-disjoint, and for the case in which the paths may share arcs. The algorithmic challenge becomes even more difficult for the case in which k arc-disjoint paths are required. We model this problem as nonlinear-mixed-integer program with an exponential
number of variables. By replacing the set of nonlinear constraints with an equivalent, but exponential, set of linear cover constraints, we can
then prescribe a branch-and-price-and-cut algorithm for the solution of this problem.

Additional Information

In Campus Calendar

School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
No keywords were submitted.
  • Created By: Barbara Christopher
  • Workflow Status: Published
  • Created On: Oct 8, 2010 - 7:38am
  • Last Updated: Oct 7, 2016 - 9:52pm