SISTEMA DE VISUALIZACIÓN Y EVALUACIÓN DEL DESEMPEÑO DE ALGORITMOS BRANCH AND BOUND PARA PROBLEMAS MIP

Abstract

El presente trabajo aborda la medición y visualización del progreso de algoritmos de resolución para problemas de programación entera mixta (MIP) basados en el esquema algorítmico Branch and Bound. Para este estudio se implementó un sistema de visualización y control del proceso de resolución de problemas MIP. Después de estudiar algunos modelos clásicos de programación entera en el capítulo 1, se presenta, en el capítulo 2, un estudio de las principales técnicas de resolución de esta clase de problemas, dentro del esquema Branch and Bound. En el capítulo 3 se discuten las técnicas de medición y visualización de algoritmos Branch and Bound desarrolladas hasta la fecha, para posteriormente presentar un conjunto de métricas a ser implementadas en el sistema de visualización. El diseo e implementación del sistema se desarrollan en el capítulo 4. Finalmente, el análisis de resultados es presentado en detalle en el capítulo 5. Los resultados ilustran con claridad la utilidad que proveen las métricas y visualizaciones implementadas para expresar el progreso del algoritmo -dentro de los límites impuestos por un proceso de tal complejidad que en determinadas situaciones se muestra efectivamente impredecible -, permitiendo a quien las analice, formarse una idea de cómo evoluciona el proceso de resolución, y al mismo tiempo, entregando información que permita tomar decisiones con respecto a la factibilidad de resolver problemas de alta dificultad