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.
- Workflow Status: Published
- Created By: Barbara Christopher
- Created: 10/08/2010
- Modified By: Fletcher Moore
- Modified: 10/07/2016