1 Presentation

• 
  03:30 PM - 04:30 PM

  Partial Decomposition Strategies for Two-Stage Stochastic Integer Programs

  • Walter Rei, presenter, Université du Québec à Montréal

  In this talk we present the concept of partial Benders decomposition for two-stage 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 Benders-based 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.