Una heurística para el problema de interdicción determinística.

Abstract

El presente trabajo tuvo como propósito desarrollar una heurística para resolver el problema de interdicción determinística, en el cual se busca minimizar el flujo máximo que puede atravesar una red cuando existen limitaciones en la disponibilidad de recursos que pueden destinarse a la inhabilitación de uno o más arcos de dicha red. La capacidad nominal de cada arco y su costo de interdicción pueden variar entre cada arco. Para el desarrollo de la heurística se tomó como base una heurística pre-existente, denominada Probabilistic Solution Discovery Algorithm (PSDA), propuesta por Ramírez-Márquez y Rocco (2008), la cual fue diseñada originalmente para abordar el problema de confiabilidad all-terminal en redes. Un estudio detallado de la misma condujo a identificar las modificaciones necesarias para adaptar dicha heurística al problema de interdicción determinística. La versión modificada, PSDA-INT, fue aplicada a tres tipos de redes: a) problemas de redes ilustrativas, b) problemas de redes con solución óptima conocida y c) problemas de redes con solución óptima desconocida. Los resultados obtenidos se compararon con los reportados en la literatura para las redes que han sido estudiadas desde la óptica de la interdicción. Esta comparación se efectuó en términos de calidad de la solución (valores extremos y promedio) y eficiencia en el espacio de búsqueda. El estudio permitió concluir que el PSDA-INT demostró buena capacidad de búsqueda en los distintos experimentos realizados. Desde el punto de vista de esfuerzo computacional, el PSDA-INT demostró eficiencia debido a que produjo las soluciones a partir de espacios de búsqueda significativamente reducidos con respecto a los que resultarían de la enumeración explícita de las posibles configuraciones de las redes. Esta investigación proporcionará una herramienta para orientar la búsqueda de estrategias destinadas a atenuar las actividades de un adversario que esté operando en un sistema modelable a través de una red.