Solving low-risk, low-cost routing problems

Consider a directed graph in which each arc has an independent probability of failing. Traditional routing problems, such as shortest path and traveling salesman problems, assume perfect operability of all arcs and nodes. However, when arc failure probabilities exist, an additional requirement must be present to retain some measure of expected functionality. In this talk, we introduce mathematical programming techniques to impose these requirements on path and cycle selection problems. We begin by examining a shortest path problem with the side constraint that the probability of successfully traversing the path is at least as large as some threshold probability. The natural formulation of this problem is a mixed-integer nonlinear program, though with some care the problem can be transformed to a mixed-integer linear program. In any case, these side constraints prevent a polynomial-time application of Dijkstra's algorithm, and make this problem ordinarily NP-Hard. This problem is next extended to the case in which a Hamiltonian Circuit is to be constructed, such that the entire circuit remains "functional" (no arc fails) with some minimum probability. A related problem arises in the domain of telecommunication systems, wherein survivable ring structures are capable of functioning properly in the event of any single arc failure. Hence, we also examine the problem in which the probability of no more than one arc failing in a Hamiltonian Circuit is sufficiently small. An even more interesting and applicable version of this problem seeks to establish two arc-independent paths between two nodes subject to some minimum reliability measure. If we require that both paths remain in operating condition with some minimum probability, we can directly apply the foregoing modeling strategies to solve this problem by standard integer (linear) programming models. However, many practical scenarios simply require that at least one path survives between a pair of nodes. In this case, we may stipulate that the probability that at least one path survives is sufficiently large. This probability is given by one minus the probability that both paths fail, which is an inherently nonlinear constraint. Even worse, such a constraint induces a nonconvex feasible region. This Robust Two-Path Problem (RTPP) is the focus of our investigation. The RTPP can be modeled as a union of a minimum cost How problem constraints, linear path-probability calculation constraints, and a single nonlinear, nonconvex constraint. The minimum flow constraints place a capacity of 1 on each arc, and establish a supply of 2 on node 1 and a demand of 2 on node n, with all intermediate nodes serving as transshipment nodes. The path-probability calculation constraints are linear, but employ binary variables that give the problem its combinatorial nature. Our approach to handling the single nonlinear constraint constructs a convex hull relaxation of the feasible region, and then utilizes one of the following iterative approaches to force the final solution to reside within the original nonconvex feasible region. In our first approach, we utilize elementary integer cutting-planes. If the current solution to the convex relaxation is not feasible to the original problem, we simply impose a condition as weak as, "do not generate this exact solution again". Unfortunately, this strategy will almost always result in very slow convergence. The second approach is a branch and bound strategy. We solve the problem in a disjunctive fashion over several intervals, yielding solutions that may or may not be feasible to the original problem. Our goal is to solve the problem in each interval, and take the best solution found in any interval. We discuss the advantages and disadvantages of these methods, and conclude with a preliminary set of computational results.