The Ancestral Benders’ cutting plane algorithm with multi-term disjunctions for mixed-integer recourse decisions in stochastic programming
详细信息 查看全文
- 作者：Yunwei Qi ; Suvrajeet Sen
- 关键词：Two ; stage stochastic mixed ; integer programs ; Cutting plane tree algorithm ; Multi ; term disjunctive cut ; Benders’ decomposition
- 刊名：Mathematical Programming
- 出版年：2017
- 出版时间：January 2017
- 年：2017
- 卷：161
- 期：1-2
- 页码：193-235
- 全文大小：
- 刊物类别：Mathematics and Statistics
- 刊物主题：Calculus of Variations and Optimal Control; Optimization; Mathematics of Computing; Numerical Analysis; Combinatorics; Theoretical, Mathematical and Computational Physics; Mathematical Methods in Phys
- 出版者：Springer Berlin Heidelberg
- ISSN：1436-4646
- 卷排序：161
文摘
This paper focuses on solving two-stage stochastic mixed integer programs (SMIPs) with general mixed integer decision variables in both stages. We develop a decomposition algorithm in which the first-stage approximation is solved by a branch-and-bound algorithm with its nodes inheriting Benders’ cuts that are valid for their ancestor nodes. In addition, we develop two closely related convexification schemes which use multi-term disjunctive cuts to obtain approximations of the second-stage mixed-integer programs. We prove that the proposed methods are finitely convergent. One of the main advantages of our decomposition scheme is that we use a Benders-based branch-and-cut approach in which linear programming approximations are strengthened sequentially. Moreover as in many decomposition schemes, these subproblems can be solved in parallel. We also illustrate these algorithms using several variants of an SMIP example from the literature, as well as a new set of test problems, which we refer to as Stochastic Server Location and Sizing. Finally, we present our computational experience with previously known examples as well as the new collection of SMIP instances. Our experiments reveal that our algorithm is able to produce provably optimal solutions (within an hour of CPU time) even in instances for which a highly reliable commercial MIP solver is unable to provide an optimal solution within an hour of CPU time.