The Ancestral Benders' cutting plane algorithm with multi-term disjunctions for mixed-integer recourse decisions in stochastic programming

• 成果类型: Article
• 署名作者: Qi, Yunwei; Sen, Suvrajeet
• 署名单位: University System of Ohio; Ohio State University; University of Southern California
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1006-6
• 发表日期: 2017
• 页码: 193-235
• 关键词: linear-programs; DECOMPOSITION; branch; variables; cut

摘要

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.