Totally unimodular stochastic programs

• 成果类型: Article
• 署名作者: Kong, Nan; Schaefer, Andrew J.; Ahmed, Shabbir
• 署名单位: Purdue University System; Purdue University; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0529-8
• 发表日期: 2013
• 页码: 1-13
• 关键词: algorithm

摘要

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.