Preprocessing in Stochastic Programming: The Case of Uncapacitated Networks

Preprocessing can speed up the solution procedures for two-stage stochastic programming. We consider the case when the second-stage problem is a pure, uncapacitated network. We describe a number of procedures to reduce the size of the recourse problem. We describe a procedure for generating efficiently the (induced) feasibility cuts, and show that further reductions are possible if more information about the node-types is taken into account. We also investigate network collapsing techniques that would simplify the work required to find both optimality cuts and feasibility cuts, if we had not yet reduced the problem to one with relatively complete recourse. Computational results confirm that substantial savings are possible.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.