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, and thus, e.g., do not require that the first-stage variables are binary. 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.
Citation
Van der Laan N, Romeijnders W (2020) A converging Benders’ decomposition algorithm for two-stage mixed-integer recourse models. Department of Operations, University of Groningen, Groningen, The Netherlands.