Title: Computational Methods for Path-based Robust Flows,
Abstract: Real world networks are often subject to severe uncertainties which need to
be addressed by any reliable prescriptive model. In the context of the maximum
flow problem subject to arc failure, robust models have gained particular
attention. For a path-based model, the resulting optimization problem is
assumed to be difficult in the literature, yet the complexity status is widely
unknown. We present a computational approach to solve the robust flow problem
to optimality by simultaneous primal and dual separation, the practical
efficacy of which is shown by a computational study.
Furthermore, we introduce a novel model of robust flows which provides a
compromise between stochastic and robust optimization by assigning
probabilities to groups of scenarios. The new model can be solved by the same
computational techniques as the robust model. A bound on the generalization
error is proven for the case that the probabilities are determined empirically.
The suggested model as well as the computational approach extend to linear
optimization problems more general than robust flows.