FORMULATING 2-STAGE STOCHASTIC PROGRAMS FOR INTERIOR POINT METHODS

• 成果类型: Article
• 署名作者: LUSTIG, IJ; MULVEY, JM; CARPENTER, TJ
• 署名单位: Princeton University; Princeton University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.39.5.757
• 发表日期: 1991
• 页码: 757-770
• 关键词: programming; LINEAR - TECHNIQUES FOR STOCHASTIC LINEAR PROGRAMS; programming; STOCHASTIC - SOLUTION BY INTERIOR POINT METHODS

摘要

This paper describes an approach for modeling two-stage stochastic programs that yields a form suitable for interior point algorithms. A staircase constraint structure is created by replacing first stage variables with sparse split variables in conjunction with side-constraints. Dense columns are thereby eliminated. The resulting model is larger than traditional stochastic programs, but computational savings are substantial-over a tenfold improvement for the problems tested. A series of experiments with stochastic networks drawn from financial planning demonstrates the attained efficiencies. Comparisons with MINOS and the dual block angular stochastic programming model are provided as benchmarks. The split variable approach is applicable to general two-stage stochastic programs and other dual block angular models.