A Branch-and-Cut algorithm for the stochastic uncapacitated lot-sizing problem

• 成果类型: Article
• 署名作者: Guan, YP; Ahmed, S; Nemhauser, GL; Miller, AJ
• 署名单位: University System of Georgia; Georgia Institute of Technology; University of Wisconsin System; University of Wisconsin Madison
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-005-0572-9
• 发表日期: 2006
• 页码: 55-84
• 关键词: valid inequalities; capacity expansion; COSTS

摘要

This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical (l, S) inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the (l, S) inequalities to a general class of valid inequalities, called the ( Q, S-Q) inequalities, and we establish necessary and sufficient conditions which guarantee that the ( Q, S-Q) inequalities are facet-defining. A separation heuristic for ( Q, S-Q) inequalities is developed and incorporated into a branch-and-cut algorithm. A computational study verifies the usefulness of the ( Q, S-Q) inequalities as cuts.