zbMATH — the first resource for mathematics

Preprocessing in stochastic programming: The case of uncapacitated networks. (English) Zbl 0752.90052
Summary: 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.

90C15 Stochastic programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI