Modelización y resolución exacta vía programación lineal entera del "Prize-Collecting Steiner Tree problem"

Abstract

En este documento se estudia el problema del Prize-Collecting Steiner Tree (PCST), el cual pertenece a la clase de problemas NP-Difíciles. Para comenzar, se presenta un estudio de las técnicas de resolución exacta existentes en la actualidad, seleccionando cinco formulaciones del problema utilizando técnicas de Programación Lineal Entera. En esta investigación se introduce una nueva formulación para resolver el PCST de forma optima. Se realizaron dos implementaciones, el nuevo modelo propuesto en esta investigación y una de las cinco formulaciones mencionadas previamente. Además, se realiza un estudio comparativo entre ambas implementaciones as como otras implementaciones basadas en algoritmos de aproximación, también capaces de resolver el PCST. Por otro lado, se realiza un estudio práctico referente a la relajación de ambos modelos, en busca de cotas inferiores de la solución optima. Por último, se estudia la aplicación del modelo en una numerosa variedad de redes que representan situaciones reales, las cuales han sido estudiadas en una cantidad considerable de investigaciones referentes al tema y se realiza una aplicación práctica en la red de generación de energía eléctrica por parte de los parques eólicos dispuestos en el territorio uruguayo. Los resultados del análisis experimental realizado son bien alentadores, muestran que ambos modelos se comportan correctamente, cumpliendo con el objetivo de llegar a la solución optima.