A Converging Benders' Decomposition Algorithm for Two-Stage Mixed-Integer Recourse Models

• 成果类型: Article
• 署名作者: van der Laan, Niels; Romeijnders, Ward
• 署名单位: University of Groningen
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2021.2223
• 发表日期: 2024
• 关键词: fenchel cutting planes; lift-and-project; stochastic programs; disjunctive cuts; gomory cuts; approximation

摘要

We propose a new solution method for two-stage mixed-integer recourse models. In contrast to existing approaches, we can handle general mixed-integer variables in both stages. Our solution method is a Benders' decomposition, in which we iteratively construct tighter approximations of the expected second stage cost function using a new family of optimality cuts. We derive these optimality cuts by parametrically solving extended formulations of the second stage problems using deterministic mixed-integer programming techniques. We establish convergence by proving that the optimality cuts recover the convex envelope of the expected second stage cost function. Finally, we demonstrate the potential of our approach by conducting numerical experiments on several investment planning and capacity expansion problems.