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

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.

Funding: The research of W. Romeijnders has been supported by the Netherlands Organisation for Scientific Research [Grant 451-17-034 4043].