Scenario formulation of stochastic linear programs and the homogeneous self-dual interior-point method

Abstract

We consider a homogeneous self-dual interior-point algorithm for solving multistage stochastic linear programs. The algorithm is particularly suitable for the so-called "scenario formulation" of the problem, whose constraint system consists of a large block-diagonal matrix together with a set of sparse nonanticipativity constraints. Due to this structure, the major computational work required by the homogeneous self-dual interior-point method can be split into three steps, each of which is highly decomposable. Numerical results on some randomly generated problems and a multistage production-planning problem are reported. © 2006 INFORMS.