Polynomial-Time Identification of Optimal Robust Network Flows Under Certain Arc Failures (Preprint); Journal article

摘要

Network flow problems have a wide variety of important applications in many areas. Although deterministic formulations of these problems are well- studied, in many practical situation one has to deal with uncertainties associated with possible failures of network components (e.g., each arc has a probability of failure). Formulations and optimal solutions of these problems need to be adjusted to take into account these uncertainty factors. The main difficulty arising in addressing these issues is the dramatic increase in the computational complexity of the resulting optimization problems. We propose LP- based solution methods for network flow problems under a set of failure scenarios, which allow for robust solutions to be found in polynomial time. We justify this fact by proving that for network flow problems under certainty with linear loss functions, the number of scenarios required to approximate the mean of the loss distribution for any fixed e>0 with probability (1-a), for a c (0,1), is polynomial with respect to the size of the network. (See paper for actual formulas.).