Journées de l'optimisation 2014
Incluant une Journée industrielle de l'optimisation
HEC Montréal, 5  7 mai 2014
JOPT2014
HEC Montréal, 5 — 7 mai 2014
MD1 Exposé magistral 2 / Tutorial 2
5 mai 2014 15h30 – 17h10
Salle: TAL Gestion globale d'actifs
Présidée par Fausto Errico
1 présentation

15h30  16h30
Partial Decomposition Strategies for TwoStage Stochastic Integer Programs
In this talk we present the concept of partial Benders decomposition for twostage stochastic integer programs. This decomposition strategy is based on the idea of retaining a subset of scenario subproblems in the master formulation such as to strengthen it throughout the solution process. We have developed a theory to support this strategy and illustrate how it may be applied to any stochastic integer program with continuous recourse. Such programs are used to model many practical applications such as the one considered in this talk, network design. They are also useful for solving problems with integer recourse as many solution methods for such problems also solve one of its linear relaxations. We will present an extensive computational study that shows the significant advantages of using a partial decomposition. Specifically, we show that this approach greatly reduces the number of optimality and feasibility cuts generated when solving a stochastic program with a Bendersbased algorithm. Furthermore, we also show that the manner in which partial decomposition is performed has a significant impact on the results and we point to the most performant strategy.