期刊
MATHEMATICAL PROGRAMMING
卷 105, 期 1, 页码 55-84出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-005-0572-9
关键词
stochastic lot-sizing; multi-stage stochastic integer programming; polyhedral study; Branch-and-Cut
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据