MA1 - Exposé magistral 1 / Tutorial 1

Benders decomposition has been established as an efficient method for solving two-stage stochastic integer programs. In its classical form, the stochastic program is decomposed by partitioning the decision variables into two groups: the first-stage decisions define a master problem, while the second-stage decisions define a set of subproblems. An optimal solution to the stochastic program is obtained by iteratively solving the master problem and the subproblems until optimality can be established. In this process, the subproblems are primarily used to identify violated cuts that strengthen the formulation of the master problem. Although this decomposition strategy has proven successful in many applications, recent studies suggest that the partition underlying the decomposition can be revisited and improved. In particular, the performance of Benders decomposition can be significantly enhanced by transferring additional information between the master problem and the subproblems. On the one hand, transferring information from the subproblems to the master problem can strengthen the master formulation. On the other hand, transferring information from the master problem to the subproblems can improve the quality of the cuts generated. In this tutorial, we review these emerging strategies for redefining the partition of decision variables and discuss how these enhancements can be effectively implemented to improve the performance of Benders decomposition.