Scenario Formulation of Stochastic Linear Programs and the Homogeneous Self-Dual Interior-Point Method
INFORMS Journal on Computing · 2006 · Volume 18 · Issue 4
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.
Keywords
multistage stochastic linear programs, interior-point methods, decomposition
Enable JavaScript for citation tools and additional paper interactions.