Back to Search Start Over

Totally unimodular stochastic programs.

Authors :
Kong, Nan
Schaefer, Andrew
Ahmed, Shabbir
Source :
Mathematical Programming. Apr2013, Vol. 138 Issue 1/2, p1-13. 13p. 1 Black and White Photograph, 5 Charts.
Publication Year :
2013

Abstract

We consider totally unimodular (TU) stochastic programs, that is, two-stage stochastic programs whose extensive-form constraint matrix is TU. We generalize the notion of total unimodularity to apply to sets of matrices and provide properties of such sets. We provide several sufficient conditions on stochastic programs to be TU. When solving TU stochastic problems using the L-shaped method, it is not clear whether the integrality restrictions should be imposed on the master problem. Such restrictions will make each master problem more difficult to solve. On the other hand, solving the linear relaxation of the master typically means sending fractional (and unlikely optimal) solutions to the subproblems, perhaps leading to more iterations. Our computational results investigate this trade-off and provide insight into which strategy is preferable. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
00255610
Volume :
138
Issue :
1/2
Database :
Academic Search Index
Journal :
Mathematical Programming
Publication Type :
Academic Journal
Accession number :
86213441
Full Text :
https://doi.org/10.1007/s10107-012-0529-8