AbstractThe overwhelming majority of survivable (fault-tolerant) network design models assume auniform scenario set. Such a scenario set assumes that every subset of the network resources(edges or vertices) of a given cardinality k comprises a scenario. While this approach yieldsproblems with clean combinatorial structure and good algorithms, it often fails to capture thetrue nature of the scenario set coming from applications.One natural reﬁnement of the uniform model is obtained by partitioning the set of resourcesinto faulty and secure resources. The scenario set contains every subset of at most k faultyresources. This work studies the Fault-Tolerant Path (FTP) problem, the counterpart of theShortest Path problem in this failure model. We present complexity results alongside exact andapproximation algorithms for FTP. We emphasize the vast increase in the complexity of theproblem with respect to its uniform analogue, the Edge-Disjoint Paths problem. 1 Introduction The Minimum-Cost Edge-Disjoint Path (EDP) problem is a classical network design problem,deﬁned as follows. Given an edge-weighted graph G = (V,E), two terminals s,t ∈V and an integerparameter k ∈Z
We propose an approach to address data uncertainty for discrete optimization and network flow problems that allows controlling the degree of conservatism of the solution, and is computationally tractable both practically and theoretically. In particular, when both the cost coefficients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows controlling the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coefficients are subject to uncertainty and the problem is a 0−1 discrete optimization problem on n variables, then we solve the robust counterpart by solving at most n+1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0−1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. We also show that the robust counterpart of an NP-hard α-approximable 0−1 discrete optimization problem, remains α-approximable. Finally, we propose an algorithm for robust network flows that solves the robust counterpart by solving a polynomial number of nominal minimum cost flow problems in a modified network. Preface. 1. Approaches to Handle Uncertainty In Decision Making. 2. A Robust Discrete Optimization Framework. 3. Computational Complexity Results of Robust Discrete Optimization Problems. 4. Easily Solvable Cases of Robust Discrete Optimization Problems. 5. Algorithmic Developments for Difficult Robust Discrete Optimization Problems. 6. Robust 1-Median Location Problems: Dynamic Aspects and Uncertainty. 7. Robust Scheduling Problems. 8. Robust Uncapacitated Network Design and International Sourcing Problems. 9. Robust Discrete Optimization: Past Successes and Future Challenges.