Una metaheurística para el problema de conjunto dominante con capacidad mínima.

Abstract

La presente memoria de título tiene como objetivo presentar el problema de conjunto dominante con capacidad mínima (CAPMDSP), de manera más específica, se trata de una variante del problema de conjunto dominante. CAPMDSP integra una restricción adicional que establece una capacidad máxima que puede dominar cada nodo. Con tal de resolver el CAPMDSP se plantea un algoritmo de múltiples inicios de búsqueda local iterada, el cual hace uso de un algoritmo del estado del arte llamado H-MUEC. H-MUEC es modificado y es utilizado para generar la solución inicial y es aplicado como una búsqueda local. Los resultados generan soluciones factibles pero que difieren respectos a los encontrados por el modelo de programación entera mixta, y los tiempos son mayores a la literatura, debido a la diferencia del lenguaje de programación utilizado.