A so-called Cluster Benders Decomposition approach for solving two-stage stochastic linear problems

  1. L. Aranburu 1
  2. L.F. Escudero 2
  3. M.A. Garín 1
  4. G. Pérez 1
  1. 1 Universidad del País Vasco, España
  2. 2 Universidad Rey Juan Carlos, España
Revista:
Top

ISSN: 1863-8279 1134-5764

Año de publicación: 2012

Volumen: 20

Número: 2

Páginas: 279-295

Tipo: Artículo

Otras publicaciones en: Top

Resumen

The optimization of stochastic linear problems, via scenario analysis, based on Benders decomposition requires appending feasibility and/or optimality cuts to the master problem until the iterative procedure reaches the optimal solution. The cuts are identified by solving the auxiliary submodels attached to the scenarios. In this work, we propose the algorithm named scenario Cluster Benders Decomposition (CBD) for dealing with the feasibility cut identification in the Benders method for solving large-scale two-stage stochastic linear problems. The scenario tree is decomposed into a set of scenario clusters and tighter feasibility cuts are obtained by solving the auxiliary submodel for each cluster instead of each individual scenario. Then, the scenario cluster based scheme allows to identify tighter feasibility cuts that yield feasible second stage decisions in reasonable computing time. Some computational experience is reported by using CPLEX as the solver of choice for the auxiliary LP submodels at each iteration of the algorithm CBD. The results that are reported show the favorable performance of the new approach over the traditional single scenario based Benders decomposition; it also outperforms the plain use of CPLEX for medium-large and large size instances.

Información de financiación

Acknowledgements This research has been partially supported by the projects ECO2008-00777/ECON from the Ministry of Education and Science, PLANIN, MTM14087-C04-01 from the Ministry of Science

Financiadores