Formulating Two-Stage Stochastic Programs for Interior Point Methods

Irvin J. Lustig, John M. Mulvey and Tamra J. Carpenter
Additional contact information
Irvin J. Lustig: Princeton University, Princeton, New Jersey
John M. Mulvey: Princeton University, Princeton, New Jersey
Tamra J. Carpenter: Princeton University, Princeton, New Jersey

Operations Research, 1991, vol. 39, issue 5, 757-770

Abstract: 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.

Keywords: programming; linear: techniques for stochastic linear programs; programming; stochastic: solution by interior point methods (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.39.5.757 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:39:y:1991:i:5:p:757-770

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().