El origen de las técnicas de composición
La programación matemática es un área de la investigación operativa que atrajo mucho interés desde el desarrollo del método SIMPLEX por Dantzig en los años 60, principalmente por las diversas aplicaciones que está técnica posee y la disponibilidad de un algoritmo para resolver los problemas de forma eficiente.
Dadas las limitaciones de poder de cómputo de la época, la aplicación de la programación matemática era observada con reserva ya que las dimensiones de los problemas surgidos de aplicaciones reales eran muy elevadas para lo que los súper ordenadores de la época podían procesar.
En aquellos tiempos los programadores informáticos, que eran casi todos matemáticos o físicos, invertían mucho tiempo en escribir software que hiciera un uso muy eficiente de la memoria disponible y en escribir código lo más optimizado posible para los compiladores (en aquellos tiempos casi todo se hacía en FORTRAN). Esto se debía esencialmente a que existían estas limitaciones, y fue natural que surgieran líneas de investigación académicas para desarrollar nuevos algoritmos que pudieran resolver problemas con las capacidades de hardware existentes. Esto y las características tan particulares de los problemas de programación matemática, en concreto de programación lineal, diría que fueron las principales razones por las que surgieron las diversas técnicas de descomposición que conocemos actualmente. Técnicas que tuvieron mucho éxito pero que su importancia se vio reducida y prácticamente quedaron obsoletas con la extraordinaria evolución del poder de cálculo de los ordenadores. Por poner un ejemplo, hemos pasado de disponer de 256 K de memoria a tener 32 Gb en un portátil.
Con la informatización de los negocios y de prácticamente casi todo en nuestra época, con el crecimiento en el volumen de datos disponible, con la investigación operativa haciéndose camino en las empresas y en la toma de decisiones, y con la disposición de software comercial preparado para entornos productivos, sorprende que la mayoría de los problemas con los que el consultor en investigación operativa se enfrenta ahora puedan ser resueltos en ordenadores portátiles, siendo raros los casos en los que sea necesario el uso de un servidor con más de 64Gb de memoria y más de 8 núcleos de CPU. Este es el caso de casi todos los problemas operativos existentes en la industria, pero una tarea pendiente de la programación matemática en la actualidad es la programación estocástica y la principal complicación, como en los inicios de la programación matemática, el tamaño.
En la era del «Big Data» es posible tener información sobre cómo afectan ciertos factores a las decisiones de negocio, factores e información que antes no estaban disponibles y que ahora es posible incluir en los modelos para reflejar en mayor medida la realidad. Por ejemplo, no tiene mucho sentido determinar el número óptimo de personas necesarias para que un hotel cumpla cierto nivel de servicio si no se ha considerado que esa semana es la final de la Champions League y un equipo ruso juega en España. Para esa semana en concreto, no solo se debe considerar el número de personas necesarias, sino las habilidades que poseen cada una de ellas, como por ejemplo que las cuatro personas que saben ruso en el hotel vengan a trabajar esos días. Estos factores no se solían considerar principalmente porque no estaban informatizados y los sistemas no permitían considerarlos, pero ahora, cuando es posible que hasta el color de nuestros ojos esté en algún sistema informático de alguna cadena de supermercados, es posible incluirlos en los modelos, haciendo que estos sean más grandes y complejos.
Hemos llegado entonces a una época en la que las limitaciones de hardware vuelven a ser un stopper para la programación matemática. Tenemos la ventaja que este problema ya se resolvió en el pasado, ahora solo tenemos que hacer que aquellas técnicas estén disponibles en software comerciales preparados para entornos productivos.
Técnicas de descomposición
Las técnicas de descomposición en programación matemática, en particular programación lineal, aprovechan la estructura de los problemas y las características del método de resolución para resolver problemas más pequeños de forma secuencial asegurando la convergencia al óptimo del problema completo. En esta serie de artículos comentaremos métodos de descomposición para problemas con «coupling constraints and variables» y la descomposición de Benders.
Métodos para problemas con «Coupling constraints and variables»
Dado un problema con la siguiente estructura
donde Ai,Bi son matrices bidimensionales y ci,bi,xi,y son vectores de dimensiones coherentes para que los productos estén definidos, es posible aplicar distintos métodos de particionamiento y descomposición. El más relevante es el método de descomposición de Dantzig-Wolfe que transforma el problema en un con muchas más restricciones y luego aplica generación de columnas. Otros métodos para resolver problemas con esta estructura son el método de particionamiento de Ritter y el de Rosen que sirven de enfoque general para resolver problemas de este tipo. Algunos ejemplos de problemas en los que se pueden aplicar estas técnicas son:
- Problemas de rutas de vehículos En el que se determinan las rutas de los vehículos para suplir la demanda de los nodos a los que hay que distribuir minimizando alguna medida como el coste.
- Planificación de tripulación En el que se determinan las asignaciones de la tripulación entre los vuelos planificados, respetando restricciones como la satisfacción de un mínimo de personal con cierta habilidad y minimizando por ejemplo el número de personal necesario para satisfacer la demanda de personal.
Descomposición de Benders
La descomposición de Benders recientemente ha recibido atención por parte de la comunidad de investigación operativa debido a su aplicabilidad en la resolución de problemas de programación estocástica. Esta resuelve problemas «separables» de la siguiente forma:
Básicamente se resuelve un problema maestro en las variables y , se fijan los valores de estas y luego se resuelve un subproblema en las variables x, de la resolución del subproblema se extraen restricciones que son añadidas al problema maestro, y de forma iterativa se va restringiendo el problema maestro hasta que se cumpla cierto criterio de parada. Esta técnica tiene la característica particular que las funciones f y F no tienen que ser lineales. Ejemplos de problemas en los que puede aplicar esta técnica son los siguientes:
- Problemas de programación estocástica sin restricciones probabilísticas En los que las restricciones del problema deben ser satisfechas por todos los escenarios generados y la función objetivo posee un valor esperado de las variables de decisión.
- Ubicación de almacenes En el que se determina donde abrir nuevos almacenes minimizando el coste de apertura de un nuevo almacén y los costes de distribución de cada almacén hasta los nodos de distribución.
La programación estocástica es de especial interés para la aplicabilidad de las técnicas de descomposición pues cuando existen restricciones probabilísticas en los problemas, se puede usar la descomposición de Benders para separar las variables estocásticas y las variables de decisión, y usar la descomposición de Dantzig-Wolfe u otra similar para resolver los subproblemas.
Si quieres saber más sobre optimización matemática o sobre decide4AI, contáctanos o síguenos en las redes sociales (Linkedin, Twitter, Youtube).