A branch-and-price algorithm for multistage stochastic integer programming with application to stochastic batch-sizing problems

• 成果类型: Article
• 署名作者: Lulli, G; Sen, S
• 署名单位: University of Arizona
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.1030.0164
• 发表日期: 2004
• 页码: 786-796
• 关键词: stochastic programming; integer programming; batch sizing; branch-and-price algorithm

摘要

In this paper, we present. a branch-and-price method to solve special structured multistage stochastic integer programming problems: We validate our method on two different versions of a multistage stochastic batchsizing problem (SBSP). One version adopts a recourse formulation, and the other is based on probabilistic constraints. Our algorithmic approach is applicable to both formulations. Our computational results suggest that both classes of problems can be solved using relatively few nodes of a branch-and-price tree. The success of our approach calls for extensions in methodology as well as applications.