¿Qué es un solver? El motor matemático que resuelve problemas complejos

  • Autor de la entrada:
  • Categoría de la entrada:Código
Imagen de Max Fischer en pexels

Muchos problemas complejos se abordan con herramientas pobres

En el contexto de la Industria 4.0 y, en general, del mundo 4.0 aparecen productos y servicios cuya organización plantea problemas extremadamente complejos. Abordarlos bien o mal puede ser la diferencia entre un negocio rentable y otro que no lo es.

Diseñar nuestra red de suministro, organizar las rutas de última milla, planificar la producción, fijar precios de nuestros productos, asignar turnos de personal, etc. son algunos ejemplos. Sin embargo, y a pesar de la importancia de abordar bien estos problemas, el enfoque de muchas empresas no es el más adecuado. En muchas ocasiones, detrás de cada problema hay una persona o un equipo que exploran algunas soluciones típicamente con ayuda de una enorme hoja de cálculo.

Este proceso es lento, no permite un análisis what-if y no garantiza que encontremos la mejor solución ni saber cómo de lejos estamos de esa mejor solución

La alternativa: programación matemática y un solver

Pero hay una alternativa mejor, con impacto de entre un 10 y un 20% de mejora: el uso de la programación matemática y de un tipo de software llamado solver

En un problema de reparto de última milla, un enfoque tradicional pasa por ir añadiendo paradas a una ruta “con sentido común”: a cada vehículo se le añaden paradas de forma secuencial de forma que cada parada que se añade esté “cerca de las anteriores”. A veces la solución no será mala, pero en otras ocasiones habrá que dar marcha atrás y volver otra vez a construir las rutas hasta que el resultado sea suficientemente satisfactorio.

La alternativa es construir un modelo matemático. Si queremos visitar una serie de clientes para realizar entregas tenemos que decidir si para cada dos clientes (A y B) la ruta pasa por B inmediatamente después de A. Si tenemos 10 clientes, existen 181440 rutas diferentes. Si el número de clientes es 100 el número de rutas es 4.6 x 10^155 (46000000… con 155 ceros).

Para definir la ruta, definimos una variable x__{AB} que toma valor igual a 1 si visitamos B inmediatamente después de B y 0 si no.

Si ir del cliente A al cliente B cuesta c__{{AB}^{1}}, el producto {c__{AB}}{x__{AB}} representa el coste en función de la ruta. Si visitamos al cliente B inmediatamente después de A pagamos el coste correspondiente. En caso contrario no.

En general, la formulación* sería como sigue.

min. {c__{ij}}{x__{ij}}

(minimizamos coste total resultado de la ruta elegida)

sujeto a: 

    \begin{align*} \sum_{j}{x__{ij}}   = 1 \hspace{0.1cm} \forall i  \hspace{0.2cm}    \end{align*}

(es necesario salir desde cada cliente hacia algún otro y solo hacia uno)

    \begin{align*} \sum_{j}{x__{ij}}   = 1 \hspace{0.1cm} \forall j  \hspace{0.2cm}   \end{align*}

(es necesario llegar a cada cliente desde algún otro y solo desde uno)

    \begin{align*} {x__{ij}}, \hspace{0.1cm} \in \hspace{0.1cm} \left\{0,1 \right\},  \forall i,j  \hspace{0.2cm}     \end{align*}

(para cada par de clientes i y j podemos incluir o no el trayecto de i a j o no en la solución final)

(* )La formulación que se ofrece no es completa. Faltan las restricciones que evitan la formación de sub-ciclos. Se han omitido de forma deliberada. La explicación de dichas restricciones no añade aspectos esencialmente diferentes e introducen una complejidad adicional a la explicación que no es estrictamente necesaria. 

Con este problema matemático o con la descomposición de este problema en varios sub-problemas podemos delegar en el solver la búsqueda de la mejor ruta. El algoritmo descarta tanto combinaciones de valores de las variables que no son viables, como aquellas donde no merece la pena buscar porque hay otras zonas que con certeza contienen mejores soluciones (rutas más baratas).

La programación matemática no es programación tradicional

Sin un solver, encontrar el óptimo (la mejor manera de diseñar u operar un sistema) es como buscar una aguja muy pequeña en un pajar muy grande.

¿Y por qué los solver sí encuentran la aguja? Porque no funcionan como la mente humana. 

A pesar de que el desarrollo de un modelo matemático y la resolución mediante un solver exigen desarrollo de código, no se trata de programación tradicional, no es un conjunto de instrucciones que se ejecutan de forma secuencial como haría la mente humana.

El solver hace uso de las propiedades matemáticas de las ecuaciones con las que se modela el sistema y buscan de forma eficiente porque “se dan cuenta” de que hay combinaciones o valores que no conviene explorar. Buscan la aguja en el pajar eliminando zonas donde seguro que la aguja no está.

El objetivo: que sea rentable

Existen diferentes alternativas con diferente coste pero para problemas complejos y de impacto en la cuenta de resultados son, sin duda, más rentables que tener al mejor experto buscando soluciones.

Si te parece que estás perdiendo tu tiempo haciendo sudokus probablemente no solo estés perdiendo tiempo sino también dinero, porque con ayuda de un solver (y de una buena formulación analítica de tu problema) podrías encontrar mejores soluciones y en menos tiempo, con impacto directo en la cuenta de resultados.