Perspectives on Using Benders Decomposition to Solve Two-Stage Stochastic Mixed-Integer Programs

Benders decomposition has shown great potential as a means to efficiently solve two-stage stochastic integer programs. As originally proposed, the stochastic programs are decomposed by first partitioning the decision variables into two groups, separating the first-stage decisions, to define a master problem, from the second-stage decisions, to define a set of subproblems. An optimal solution to the stochastic program is then obtained by successively solving the master and subproblems, until the solution of the master can be established as optimal (the subproblems being used here as a means to find violated cuts to strengthen the master’s formulation). Although this decomposition strategy has produced successful results, recent studies have shown that the partitioning choices that underly the decomposition should be revisited. Specifically, the Benders method can be significantly enhanced and accelerated by either transferring information from the subproblems to the master, thus strengthening the latter’s formulation, or applying the reverse approach and sending information from the master to the subproblems, thus improving the quality of the cuts that can be obtained from them. In the present chapter, we thus highlight these new strategies to partition the decision variables and discuss how to successfully implement these enhancements for the Benders method.