Walter Rei, ESG, UQAM

Partial Benders Decomposition Strategies for Two-Stage Stochastic Integer Programs

Benders decomposition is a broadly used used exact solution method for stochastic programming, enabling such programs to be decomposed according to the realizations of the random events that set the values of their stochastic parameters. This strategy also comes with important drawbacks, however, such as a weak master problem following the relaxation step that confines the dual cuts to the scenario sub-problems. We propose the first comprehensive Partial Benders Decomposition methodology for two- stage integer stochastic program, based on the idea of including explicit information from the scenario sub-problems in the master. We propose two scenario-retention strategies that include a subset of the second stage scenario variables in the master, aiming to significantly reduce the number of feasibility cuts generated. We also propose a scenario- creation strategy to improve the lower-bound provided by the master problem, as well as three hybrids obtained by combining these pure strategies. We report the results of an extensive experimental campaign on two-stage stochastic multicommodity network design problems. The analysis clearly shows the proposed methodology yields significant benefits in computation efficiency, solution quality, and stability of the solution process.