Two-stage integer programs with stochastic right-hand sides: a superadditive dual approach

• 成果类型: Article
• 署名作者: Kong, Nan; Schaefer, Andrew J.; Hunsaker, Brady
• 署名单位: State University System of Florida; University of South Florida; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-006-0711-y
• 发表日期: 2006
• 页码: 275-296
• 关键词: decomposition; algorithm; Recourse; uncertainty; FRAMEWORK

摘要

We consider two-stage pure integer programs with discretely distributed stochastic right-hand sides. We present an equivalent superadditive dual formulation that uses the value functions in both stages. We give two algorithms for finding the value functions. To solve the reformulation after obtaining the value functions, we develop a global branch-and-bound approach and a level-set approach to find an optimal tender. We show that our method can solve randomly generated instances whose extensive forms are several orders of magnitude larger than the extensive forms of those instances found in the literature.