Resumen de Paralelización del Algoritmo de Descomposición Cluster Benders

Jordi Mateo, Jordi Lladós, Josep Ll. Lérida, Lluís Miquel Plà , Francesc Solsona

• 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.