La optimización matemática es el conjunto de técnicas y algoritmos que tienen por objetivo seleccionar el mejor elemento de un conjunto (con respecto a algún criterio), sujeto – o no – a requisitos que se formulan en términos de restricciones.
Desde los inicios de la civilización, la especie humana ha buscado maneras para encontrar la mejor manera de obtener un objetivo. Por ejemplo, la mejor manera de transportar bienes, o la manera más rápida, o menos costosa de poder llegar de un punto A a un punto B.
Cada vez más, las empresas se están dando cuenta del potencial de estas técnicas para la mejoría de su negocio. Por ejemplo, una empresa de suministro de gasolina está interesada en saber cuál es el mejor sitio para colocar sus dispensadores, o bien, una empresa de transporte puede averiguar cuántos camiones necesita para realizar un pedido y poder saber la cantidad necesaria de los mismos para reponer a tiempo su stock y evitar la pérdida de ventas por falta producto. No obstante, es necesario un conocimiento teórico y práctico de dichas técnicas para poderlas aplicar adecuadamente. Además, muchas veces el problema no está del todo bien definido y a la hora de su resolución presenta complejos desafíos.
En este artículo presentaremos los conceptos básicos que definen un problema de optimización. Comentaremos los tres pasos que se deben dar para obtener el óptimo, a saber: entender las necesidades de quien tiene el problema, construir el correspondiente problema y resolverlo. También explicaremos qué dificultades pueden aparecer y qué buenas prácticas llevar a cabo. Finalmente, presentaremos algunos ejemplos de software y librerías que nos ayudan a resolver problemas de optimización.
Estructura de un problema de optimización
Para poder clasificar y resolver exitosamente un problema de optimización, primero es necesario identificar las tres piezas claves que lo componen:
- Cuál es la decisión: antes de plantear ningún modelo, necesitamos tener claro en qué consisten las decisiones, qué se puede hacer en el sistema para que este funcione “mejor”. Por ejemplo, si se trata de la gestión de la cadena de suministro, ¿se decide solo cuáles serán los flujos o además dónde localizar las instalaciones? En el primer caso, solo se obtendrá la mejor cantidad de cada familia de productos a transportar entre las diferentes instalaciones. En el segundo, también se obtendrán las cantidades transportadas y dónde estarán ubicadas las instalaciones de entre un conjunto de posibles localizaciones candidatas.
- Requisitos: técnicos, comerciales, de negocio… Debemos entender qué elementos y qué restricciones tiene el problema, puesto que en general, la limitación de recursos nos acotará el rango (conjunto) de las posibles soluciones. Por ejemplo, para cada familia de productos y clientes deberemos hacer llegar una cantidad igual a la demanda.
- Indicador a optimizar, del que queremos encontrar su valor óptimo. Por ejemplo, es el coste total de la operación la cadena de suministro o la calidad de servicio. A este indicador también se le conoce como función objetivo o función coste.
En algunas ocasiones, el problema será sencillo y las piezas serán simples de modelizar. En otras, alguno o algunos de los puntos anteriores presentarán dificultad. Generalmente el problema será más difícil en la mayoría de los puntos y se deberá abordar de manera escalonada, primero planteando subproblemas pequeños y más simples y a medida que éstos se entienden y se resuelven, ir incrementando poco a poco su dificultad. Además, otra ventaja de resolver un problema de manera escalonada es que la complejidad computacional de resolución del mismo depende de su naturaleza, hecho que puede provocar que con problemas de tamaño creciente, los tiempos de resolución incrementen. De modo que empezar con problemas con pocas variables, permiten tener resultados parciales más rápidamente y, con ello, ir comprobando la factibilidad del problema.
Modelización del problema
Para el proceso de resolución de problema de optimización se deben diferenciar dos fases: la primera, donde se identifica, como se indicaba anteriormente, en qué consiste la decisión, cuales son los requisitos del sistema y cuál es el indicador que queremos optimizar. Para esta fase se requiere un conocimiento funcional y analítico del negocio.
Tras esta fase, se pasa a la traducción del modelo a un lenguaje matemático, el cual nos permitirá resolver numéricamente el problema. Este proceso es llamado modelización. En esta fase, la decisión se traduce en variables, los requisitos en restricciones y el indicador en la llamada función objetivo, como se comenta en el ejemplo siguiente.
Veamos un ejemplo donde se expone un problema dado por un negocio y determinemos las variables, restricciones y función objetivo entren en juego.
Ejemplo del problema del viajante Dada una lista de ciudades y las distancias entre cada par de ellas, una empresa quiere determinar la ruta más corta para que su comercial pueda visitar todas las ciudades exactamente una vez y vuelva a su ciudad de origen.
Una de las posibles formulaciones del problema es la siguiente.
Variables: Definimos 
como la variable “existe camino entre la ciudad 
y la ciudad 
” (observemos que es una variable binaria, es decir, valdrá 1 en caso de que exista el camino y 0 en caso contrario) y 
como la distancia entre la ciudad y la ciudad . Denotamos por 
el número de ciudades de la lista.
Restricciones:
Función objetivo:
En la figura 1, se puede ver un ejemplo de un caso particular del problema del viajante. El dibujo de la izquierda enseña el grafo de ciudades (cinco ciudades) y sus conexiones (desde cada ciudad, en este caso, se puede viajar a cualquier otra). La figura del centro es una solución del problema, es decir, un recorrido óptimo. Finalmente, la imagen de la derecha es un ejemplo de subtour, que queda descartado por la restricción 3.
| La restricción 3 admite formulaciones. En nuestro caso, hemos aplicado la formulación de Dantzig–Fulkerson–Johnson. En el blog de este enlace, se explican diferentes formas y se compara su eficiencia. |
En general, la forma estándar de escribir un problema de optimización de maximización es 
, donde 
es la función objetivo. Por otro lado, un problema de minimización tiene la forma 
.
La modelización de un problema no tiene porqué ser única. A veces, un tratamiento previo de los datos permite escribir de forma más sencilla el modelo. Por ejemplo, el famoso problema del corte unidimensional es un caso paradigmático donde la modelización del mismo da lugar, a bien un problema muy costoso computacionalmente hablando o bien, a uno bastante más sencillo.
En general, los problemas de optimización binaria, entera o mixta suelen utilizar heurísticas y metaheurísticas así como métodos estocásticos haciendo que su complejidad (tiempo de resolución) aumente considerablemente con respecto al tamaño de los datos de entrada, en contrapartida con, los problemas de programación lineal, que presentan una complejidad más estable. Es habitual encontrarse con casos donde el número de variables se cuenten por miles y, si se desea tener una optimización “en caliente”, esto es, obtener el resultado del problema en un corto intervalo de tiempo desde que se le pasó los datos para poder tomar una decisión óptima lo antes posible, el algoritmo debe estar bien modelado.
Resolución del problema
Con el problema debidamente modelado podemos pasar al último paso, a la resolución del problema. Dependiendo de varias características tales como el tipo de variables, las restricciones, la forma de la función objetivo, etc. se utilizarán una u otras técnicas de resolución. Dichas técnicas deben conocerse para poder explotar sus puntos fuertes teniendo en cuenta sus flaquezas (como el coste de memoria o tiempo de ejecución). Las librerías más complejas (ver siguiente punto), pueden guiarnos a la elección de tales técnicas, pero dependiendo del caso, dichas sugerencias pueden no ser optimas y requieran ser modificadas por el usuario.
Modelización y resolución del problema con librerías
En la mayoría de los casos necesitaremos ayuda computacional para resolver el problema al que nos estamos enfrentando. Para ello, existen varías librerías en diferentes lenguajes de programación. En esta sección hablaremos de algunas librerías de modelización, de algunas de resolución y algunas que aúnan funcionalidades y procesos. No obstante, subrayaremos que modelización y resolución son dos conceptos diferentes.
Modelizador y solver: dos herramientas diferentes
Para obtener la solución de un problema de optimización necesitamos modelizarlo y resolverlo. Hoy en día existen herramientas en diferentes lenguajes de programación que permiten hacer uno o ambos pasos, pero se debe tener claro la diferencia que existe entre ellos.
Por un lado, los paquetes de modelización nos permiten escribir un problema (parámetros, variables, función objetivo y restricciones) de manera que pueda ser entendido por el ordenador y por otros paquetes. Estas, en general, librerías de alto nivel, nos permitirán abstraer el problema, nos facilitarán su mantenimiento, explotación, actualización, etc.
Por otro lado, para poder encontrar la mejor solución (resolver el problema) necesitamos aplicar una serie de algoritmos complejos que dependen (más o menos) de las propiedades y características del problema en cuestión. De ello se encargan los solvers. Los solvers son una “caja de herramientas” que, dado un problema modelizado, se encargan de resolverlo de la mejor manera. Como existen muchos tipos de problemas de optimización, hay solvers más o menos complejos, más o menos ambiciosos que permiten resolver más o menos problemas específicos. Es muy interesante, una vez el problema está formulado matemáticamente, pensar qué solver se va a utilizar teniendo en cuenta sus características. Si el problema es lineal, la elección más adecuada es un solver que esté preparado para resolver este tipo de problemas.
Tanto para la modelización como para la resolución del problema podemos encontrar librerías en los diferentes lenguajes de programación. Generalmente, el problema se modela (se traduce) con una librería de modelización. Una vez el problema está modelado, la librería llama a un solver que se encarga de aplicar los algoritmos pertinentes para la obtención del (de los) óptimo(s). Esta arquitectura permite la flexibilidad de usar diferentes tipos de solver, permitiendo su adecuación al problema.
Finalmente, algunos solvers permiten también la modelización del problema. Sin embargo, en estos casos, la modelización queda determinada por el solver en cuestión, y por tanto limitada al mismo.
Algunos ejemplos de librerías
Hoy en día existen una gran variedad de librerías, algunas de pago y otras gratuitas, que permiten modelar y/o resolver problemas de optimización. Dependiendo del tipo de problema al que nos enfrentemos, elegiremos una u otra. Puede ser habitual probar durante el proceso de desarrollo diferentes librerías (en general, solvers) para determinar cuál tiene el mejor rendimiento en nuestro problema particular.
Existe una gran oferta de estas librerías para la mayoría de lenguajes de programación más usados, como C++, Java o Python. Incluso, lenguajes más emergentes y enfocados al análisis de datos tales como Julia también tienen ecosistemas preparados para resolver problemas de optimización.
Aquí se presentan una serie de ejemplos de las librerías más usadas.
Librerías de modelización
Para modelar los problemas de optimización, algunas de las librerías más usadas (aunque no las únicas) son:
- Pyomo: lenguaje de modelización de alto nivel y de código abierto gratuito. Es un framework flexible, portable y mantenible. Permite llamar a gran variedad solvers para problemas de optimización lineales y no lineales.
- PuLP: librería de alto nivel con código abierto y gratuito. Al igual que Pyomo, es flexible y portable. No obstante, a pesar de aceptar diferentes solvers, solo está pensado para modelar problemas de optimización lineales.
- OR-Tools: software abierto de optimización desarrollado por google capacitado para resolver problemas combinatorios, optimización entera y programación lineal. Acepta hasta seis solvers comerciales como SCIP, GLPK, GLOP, CP-SAT.
- AIMMS: lenguaje de modelización algebraica que permite editar y crear interfaces gráficas para los modelos y un entorno de uso gráfico para el usuario. Soporta varios solvers como GUROBI, FICO, IPOPT… AIMMS soporta problemas de optimización lineal, cuadrática, entera-mixta, estocástica.
- GAMS: sistema de modelización de alto nivel que consiste en un compilador con varios solvers asociados. El compilador traduce el problema al lenguaje adecuado para el solver dado.
- ILOG CPLEX: software comercial fabricado por IBM que permite modelar y resolver problemas de optimización. También tiene interfaz gráfica para ayudar al usuario a la modelización y revisión del modelo y sus resultados.
Solvers
- Gurobi: uno de los solvers más extendidos, permite modelizar y resolver diferentes tipos de problemas (LP, MIP, Convexos, No Convexos, etc.). Se puede usar en gran variedad de lenguajes de programación, como Java, Python, C++.
- LocalSolver: solver especializado en problemas combinatorios tales como rutas de vehículos, \textit{scheduling} o problemas de \textit{supply chain}. Tiene APIS para ser usado en Python, Java, C# y C++.
- CBC: El COIN Branch and Cut solver (o CBC) es de código abierto, escrito en C++, e inspirado para resolver problemas de programación entera-mixta.
- GLPK: GLPK (cuyas siglas significan \textit{GNU Linear Programming Kit}) tiene por objetivo resolver, sobre todo, problemas de programación lineal y programación entera-mixta con una gran cantidad de variables y parámetros.
- IPOPT: del inglés Interior Point OPTimizer, es un paquete de Python para la resolución de problemas de optimización no lineal a gran escala.
Conclusiones
En este artículo hemos visto las tres piezas fundamentales de un problema de optimización: las variables (la decisión), qué se va a optimizar (la función objetivo) y los requisitos (las restricciones). Además, hemos comentado la importancia de la correcta modelización del mismo y cómo diferentes formulaciones pueden implicar grandes variaciones en tiempo o memoria a la hora de resolver el problema.
También hemos subrayado la importancia de clasificar correctamente el problema para aplicar el mejor algoritmo de resolución y poder reducir el tiempo de ejecución y maximizar su precisión. Finalmente, hemos presentado diferentes librerías que permiten modelar y/o resolver un problema de optimización.
