Groupe d’études et de recherche en analyse des décisions

G-2020-54

Unified branch-and-Benders-cut for two-stage stochastic mixed-integer programs

, , et

Two-stage stochastic programs are a class of stochastic problems where data uncertainty is often discretized into scenarios, making them amenable to solution approaches such as Benders decomposition. However, classic Benders decomposition is not applicable to general two-stage stochastic mixed-integer programs due to the restriction that the second stage variables must be continuous. We propose a novel Benders decomposition-based framework that accommodates mixed-integer variables in both stages as well as uncertainty in all the recourse parameters. The proposed approach is a unified branch-and-Benders algorithm, where we use a heuristic to maintain a global upper bound and a post-processing phase to determine an optimal solution. We also study how enhanced Benders decomposition strategies such as the partial decomposition technique can be used to improve the algorithm's convergence. Through an extensive series of experiments, we demonstrate that the proposed framework performs better than state-of-the-art methods. It is able to solve some problem instances with more than one million variables in reasonable time.

, 33 pages