*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
