Thesis DESARROLLO DE ALGORITMO BRANCH & BOUND EN PARALELO PARA LA RESOLUCIÓN DE PROBLEMAS DE OPTIMIZACIÓN COMBINATORIAL
Date
2020-08-28
Authors
LARREA EGAÑA, PABLO IGNACIO
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
En el presente trabajo de memoria se presenta el estudio, desarrollo y evaluación de la paralelización de procesos en la ejecución de un algoritmo Branch and Bound para la resolución eficiente de problemas combinatoriales.
Con lo anterior, el objetivo es estudiar el comportamiento que adquiere el algoritmo de resolución de problemas de optimización de variable entera y/o binaria al adoptar esta metodología. ¿Mejoran los tiempos de ejecución del algoritmo Branch and Bound paralelizado frente al serial? Y, de ser así, ¿con qué técnicas de exploración se aprovechan de mejor manera los beneficios obtenidos por esto? ¿Vale la pena paralelizar?
El algoritmo Branch and Bound paralelo fue programado utilizado Python 3.5.6, con su respectivo modo multiprocessing, apoyado con el lenguaje de modelamiento Pyomo 5.6.9. Pyomo entrega las herramientas para definir los componentes de un problema de optimización, siendo luego manipulados para armar el árbol de subproblemas y entregar las soluciones correspondientes. La resolución de los nodos del árbol se realizó mediante el uso del solver Gurobi 8.1.1, con apoyo de una licencia académica, haciendo uso de un equipo con dos procesadores Intel Xeon Silver 4114 CPU @2.20 Ghz y 2.19 Ghz, con un sistema operativo Windows 10 Pro for Workstations y 64 GB RAM.
Se determinó un beneficio importante en los tiempos de resolución de los problemas, con aceleraciones siempre positivas que dan a conocer la eficiencia de la paralelización. El cambio más notorio se da al pasar desde una resolución serial a una paralelizada con dos procesos. Desde dicho punto, la eficiencia de la paralelización decrece potencialmente, aunque siempre se mantiene positiva. La estrategia centrada en exploración en profundidad (DFS) es quién recibe más cambios en sus velocidades de resolución por parte de esto. Ahora bien, también se determinó que la estrategia centrada en el mejor valor (BFS) es aquella que provee los mejores resultados en cuanto a tiempos de ejecución. Aunque no se descarta que pudiese ser opacada por la DFS en ambientes de gran cantidad de procesos paralelos, aún mayores a los utilizados en el presente estudio. Se plantea además la existencia de un máximo de aceleración que se puede alcanzar al hacer uso de la paralelización, tras lo cual, al aumentar la cantidad de procesos utilizados, se consiguen peores tiempos de ejecución.
Por último, se sugiere realizar a futuro un estudio en profundidad de técnicas de almacenamiento de información para los nodos. Debido a la cantidad de data que se debe almacenar en la memoria física (RAM) del equipo computacional, instancias de gran tamaño tienden a desestabilizar el funcionamiento correcto del computador, por lo que su manejo correcto es clave.
Description
Keywords
OPTIMIZACIÓN DE PROCESOS , BRANCH & BOUND , PYTHOM