RESOLUCIÓN DE PROBLEMAS DE DOMINACIÓN TOTAL PONDERADA POR MEDIO DE MODELOS DE OPTIMIZACIÓN

Abstract

Dentro de los todos los distintos tipos de problemas combinatorios orientados a la optimización de grafos, unos de los más importantes son los denominados problemas de conjuntos dominantes. Sin embargo, para estos problemas no se conoce un algoritmo eficiente que los resuelva en un tiempo razonable. Igualmente, existen métodos que permiten descartar posibles soluciones y reducir el tiempo de resolución. También hay otros métodos con los que poder obtener, en caso de que el problema sea muy complejo, una solución aproximada asociada a un margen de error.

En este proyecto se trabajará con problemas de dominanción total ponderados (o WTDP, del inglés, Weighted Total Domination Problem), un tipo de problema específico, dentro de los problemas de conjuntos dominantes, con aplicaciones como el diseño de redes comunicación o el análisis de redes sociales. Se definirán distintas formulaciones para resolver el problema de optimización asociado y se hará un estudio de eficiencia entre ambos.

Además, se compararán las herramientas de Gurobi Optimizer y CPLEX Optimizer (IBM) observando la velocidad de resolución y el fallo cometido por ambas herramientas para una misma formulación en problemas de hasta 125 vértices dentro de un tiempo límite de 30 minutos. También se estudiará cómo influyen las características del grafo en la resolución del problema.

Así, se mostrará que la formulación a usar dependerá del software con el que se ejecuten los problemas y que, en general, Gurobi Optimizer es más eficiente y proporciona menores márgenes de error en sus aproximaciones.