Computation in Discrete Stochastic Programs with Recourse

This paper presents a solution procedure for discrete stochastic programs with recourse (linear programs under uncertainty). It views the m stochastic elements of the requirements vector as an m-dimensional space in which each combination of the discrete values is a lattice point. For a given second-stage basis, certain of the lattice points are feasible. A procedure is presented to delete infeasible points from the space. Thus, the aggregate probability associated with points feasible for this basis can be enumerated, and used to weight the vector of dual variables defined by the basis. Finally, the paper presents a systematic procedure for changing optimal bases so that a feasible and optimal basis is found for every lattice point.