Guan, Yongpei
[Author];
Ahmed, Shabbir
[Author];
Nemhauser, George L.
[Author]
;
Higle, Julie L.
[Contributor];
Römisch, Werner
[Contributor];
Sen, Surrajeet
[Contributor]
A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical $(\mathcal{l}, S)$ inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the $(\mathcal{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.