Introducción y breve reseña histórica
El problema de localización de plantas sin capacidades (UPLP), también conocido como problema de localización-asignación o problema de localización de plantas simple (SPLP) se basa en elegir un subconjunto de posibles emplazamientos, y decidir qué clientes son servidos desde cada uno de ellos, de manera que satisfagan ciertos requisitos, con la propiedad de que las plantas tienen indefinida capacidad de servicio, es decir, se asume la posibilidad de que cualquiera de las plantas por sí sola pueda tener capacidad suficiente para satisfacer la demanda de todos. Los requisitos añadidos serán dados en función de cada variante del problema.
Los UPLP son problemas discretos, pues se asume que cada cliente es un punto concreto en un mapa (o, de no serlo, se toma cada zona de demanda concentrada en un punto representativo). Además las posibles zonas de emplazamiento de las plantas y de demanda están predeterminadas.
Este tipo de problemas se centra en la producción y distribución de un servicio en un intervalo de tiempo concreto (ej: un año), durante el cual se asume conocida la demanda con certeza, aunque la característica distintiva de este tipo de problemas es dotar de la capacidad de toma de decisiones, sin tener en cuenta restricciones de presupuesto, tecnológicas o físicas.
Krarup y Pruzan hicieron un primer estudio y recopilación de la literatura de los UPLP en 1983, incluyendo propiedades de las soluciones. Erlenkotter tuvo también un papel muy influyente, presentando en 1978 un algoritmo basado en el problema dual para resolver los UPLP, que ha quedado como una de las técnicas más eficientes para resolver este tipo de problemas (este algoritmo lo veremos en el desarrollo teórico). Anteriormente a Erlenkotter, uno de los métodos más comunes era el algoritmo de "Ramificación-Acotación" (branch-and-bound), que es un algoritmo de resolución de modelos de programación entera, el cual consiste en "linealizar" el modelo, es decir, resolver el problema relajado y luego generar de forma recursiva cotas (o restricciones adicionales) que favorecen la obtención de valores enteros para las variables de decisión que habían adoptado antes valores fraccionarios. Este algoritmo había sido desarrollado por Efroymson y Ray (1966). Otro algoritmo anterior, fue la técnica de enumeración implícita de Spielberg (1969). Efroymson y Ray (1966) usaron una formulación compacta del UPLP, basándose en la característica de que la relajación linear puede ser resueltas por inspección (de forma más sencilla).
Como estos últimos métodos no dotan buenas cotas ni formas eficientes para la resolución, a este modelo se le denomina "formulación débil". Khumawala en 1972 desarrolló estrategias eficientes de ramificación y separación para el algoritmo de "Ramificación-Acotación". Sin embargo, Erlenkotter usó la "formulación ajustada" ("tight formulation"), que producía de forma más directa soluciones enteras. Esta propiedad de la "formulación ajustada" fue puesta de relieve por Schrage en 1975 y fue usada con éxito por Cornuejols en 1977, mismo año en el que Bilde y Krarup desarrollaron un algoritmo basado en el análisis del problema dual similar al que más adelante abordaremos de Erlenkotter.
Tras esto, se empezó a dar más relevancia, por su carácter más realista, al problema de localización de plantas con capacidades (CPLP), donde se asume una cierta capacidad de servicio en cada emplazamiento, y muchas técnicas para la resolución de los CPLP basándose en las técnicas mencionadas para los UPLP.