Paralelización del Algoritmo de Descomposición Cluster Benders

• Autores: Jordi Mateo, Jordi Lladós, Josep Ll. Lérida, Lluís Miquel Plà , Francesc Solsona
• Localización: Actas de las XXIV Jornadas de Paralelismo / coord. por Guillermo Botella, Alberto A. del Barrio García , 2013, ISBN 978-84-695-8330-2, págs. 389-394
• Idioma: español
• Texto completo no disponible (Saber más ...)
• Resumen

  • El método Benders es un método dedescomposición que se puede utilizar para resolver losproblemas lineales estocásticos multietapa mediante elanálisis de escenarios. El algoritmo se compone de trespasos: el primero resuelve el problema master, el segundoobtiene los cortes de factibilidad y el tercero los cortes deoptimalidad. Estos cortes se añaden secuencialmente alproblema master hasta que el procedimiento iterativo llegaa la solución óptima. Dado que los cortes de factibilidad seobtienen mediante la resolución de subproblemas por cadaescenario, independientes entre ellos, ésto facilita laparalelización del algoritmo. El algoritmo CBD (ClusterBenders Decomposition) es una modificación del deBenders original, dónde se obtienen los cortes defactibilidad mediante la agrupación de escenariospermitiendo ajustar la carga computacional al tamaño delsubproblema. En este trabajo se presenta la paralelizacióndel algoritmo CBD. Los resultados muestran como laparalelización del algoritmo CBD obtiene gananciassignificativas de rendimiento con respecto a CBD yBenders.