Restricted recourse strategies for bounding the expected network recourse function

This paper presents bounds for the expected recourse function for stochastic programs with network recourse. Cyclic recourse, a concept introduced by Wallace [18], allows the approximation of the recourse problem by restricting the optimal flows on a set of cycles and by augmenting the original network to induce separability. We introduce a new procedure that uses again a set of cycles but does not approximate the problem; instead it solves it heuristically without altering the original network or requiring separability. The method produces tighter bounds and is computationally feasible for large networks. Numerical experiments with selected networks illustrate the effectiveness of the approach.