Hace unos años publicamos en este blog un acertijo que se le atribuye a Einstein y del que se dice que solo el 2% de las personas es capaz de resolverlo. Lo que no se dice es que esto es así cuando el problema se aborda con una “estrategia humana” de resolución, como cuando resolvemos un sudoku.

Sin embargo, ese problema y cualquier variante del mismo se pueden resolver mediante analítica prescriptiva con garantía de éxito y en décimas de segundo. Y la razón por la que te estamos contando esto es que hay muchas industrias que aún resuelven sus problemas como si fueran un sudoku, a pesar de que hay toda una disciplina dedicada a resolver dichos problemas en tiempos muy reducidos y con excelentes resultados.

El acertijo

El acertijo, aparentemente sencillo, se basa en una serie de consideraciones y en una pregunta: ¿quién es el dueño del pez?

Las consideraciones:

• El inglés vive en la casa roja.
• El sueco tiene perro.
• El danés toma té.
• El noruego vive en la primera casa.
• El alemán fuma Prince.
• La casa verde queda inmediatamente a la izquierda de la blanca.
• El dueño de la casa verde toma café.
• La persona que fuma Pall Mall cría pájaros.
• El dueño de la casa amarilla fuma Durnhill.
• El hombre que vive en la casa del centro toma leche.
• El hombre que fuma Blends vive al lado del que tiene un gato.
• El hombre que tiene un caballo vive al lado del que fuma Dunhill.
• El hombre que fuma Bluemaster toma cerveza.
• El hombre que fuma Blends es vecino del que toma agua.
• El noruego vive al lado de la casa azul.

El problema que nos plantea Einstein es un problema de carácter combinatorio. Los problemas combinatorios se caracterizan por la existencia de un conjunto de elementos (por ejemplo, bebida de cada persona) para el cual hay diferentes alternativas (agua, cerveza, te, café o leche). Veamos qué estructura tiene una solución a este problema.

Si rellenásemos las dos tablas que tenemos a continuación, tendríamos una solución. Por un lado, asignaríamos una bebida, una mascota, una casa y una marca de tabaco a cada persona y, por otro, decidiríamos qué posición ocupa cada casa.

	Bebida	Mascota	Casa	Tabaco
Inglés
Sueco
Noruego
Danés
Alemán

En el caso de la primera tabla hay cinco bebidas candidatas, por lo que cada una de las celdas de la columna bebida puede tomar una de esas cinco opciones y, a su vez, el conjunto de todas las posibles combinaciones con las que podemos rellenar esa columna es 5⁵=3125. Del mismo modo hay otras 3125 posibles asignaciones de mascotas a las cinco personas, y lo mismo para las casas y las marcas de tabaco. Por lo tanto, el número total de combinaciones con las que podemos rellenar esta primera tabla es (5⁵)⁵=5²⁵, es decir, un total de 298 023 223 876 953 000.

Nota: Evidentemente, muchas de estas combinaciones no son válidas y cuando la mente humana resuelve el acertijo las descarta, (nadie rellenaría perro, perro, perro, perro, perro). Sin embargo, cuando delegamos la tarea a una máquina, como veremos después, hay que excluirlas explícitamente de la búsqueda.

	Verde	Blanca	Amarilla	Roja	Azul
Posición

Igualmente, tenemos que asignar una posición a cada casa rellenando la segunda tabla. Como hay cinco posibles valores para cada celda, existen 5⁵=3125 posibles combinaciones.

Finalmente, el conjunto de todas las posibles combinaciones para las dos tablas es el productos de las combinaciones de ambas, es decir, 5²⁵*5⁵ o 931 322 574 615 479 000 000 posibles combinaciones. Si necesitásemos un nanosegundo (10^-9 segundos) para construir cada una de ellas y comprobar que las reglas que se deben cumplir efectivamente se cumplen, tardaríamos casi  30 000 años en evaluarlas todas.

Esta conclusión se puede generalizar a los problemas combinatorios: la combinación de las posibles asignaciones para los diferentes elementos suele dar lugar a un espacio de soluciones de tamaño demasiado grande para ser tratado mediante la fuerza bruta, es decir explorando todas y cada una de las combinaciones existentes.

Por ello cuando la mente humana trata de resolver un problema como éste no va probando una a una las posibles asignaciones con la esperanza de encontrar la solución, sino que lo hace de forma secuencial, intentando respetar las reglas a medida que construye la solución (según va rellenando las celdas de las tablas), de manera parecida a como nos enfrentamos a un sudoku.

De esta manera, aunque evitamos explorar soluciones que claramente no cumplen con las reglas, como, por ejemplo, asignar agua como bebida a todas las personas, el “enfoque de resolución humano” tiene grandes inconvenientes:

• En primer lugar es “miope”, trata de asignar valores teniendo en cuenta las reglas y las asignaciones que se han hecho hasta el momento y puede llegar un punto en el que no hay forma de poder continuar porque no hay manera de seguir haciendo asignaciones sin violar alguna regla. Cuando esto ocurre, hay que volver atrás o, incluso, empezar de nuevo. Es decir, no hay garantía de éxito.
• Además, es lento e incierto. Como no se trata de un procedimiento para el cual hay prueba de convergencia, el tiempo empleado es incierto, variable y, sobre todo si depende de cálculos manuales realizados por una persona, muy lentos.
• Por último, depende de la pericia de la persona que resuelve el problema.

Cómo resolver el acertijo mediante analítica prescriptiva

Resolver un problema como el de Einstein usando el ingenio está bien como pasatiempo y como ejercicio para mantener un cerebro activo, pero no más.

En el mundo del siglo XXI los problemas combinatorios son cada vez más y de mayor complejidad. Las rutas de reparto, los turnos de personal, los planes de producción… son problemas de la misma naturaleza que el problema de Einstein: son problemas combinatorios pero típicamente mucho más grandes; en lugar de cinco personas, tenemos cientos de clientes a los que tenemos que hacer visitas, y decenas de vehículos en los que hay que cargar miles de paquetes… El número de posibles combinaciones excede casi cualquier número imaginable.

En muchas ocasiones, los responsables de los sistemas donde aparecen estos problemas, los abordan como la mente humana aborda el problema de Einstein, resolviendo el problema de forma secuencial. Por ejemplo, en el caso de las rutas, se pueden elaborar rutas de forma que se van añadiendo clientes, donde cada nuevo cliente de una ruta es el más cercano al último añadido. Sin embargo, si los clientes imponen ventanas de entrega, este método muchas veces no funcionará y habrá que volver a empezar.

El enfoque desde la analítica prescriptiva es completamente diferente al plantear el problema de forma global, no secuencial. Consiste en describir matemáticamente todas las posibilidades a través de variables y de ecuaciones e inecuaciones y, después, explorar de forma inteligente los valores de esas variables. “Inteligente” significa no buscar la aguja en el pajar recorriendo cada resquicio del mismo, sino identificando en qué zonas no está la aguja para no perder tiempo donde sabemos que no está.

Un modelo matemático de optimización tiene tres elementos: las variables, las restricciones y la función objetivo. Vamos a ver en qué consiste cada uno de estos tres elementos con el ejemplo de Einstein.

Las variables.

Las variables representan la solución, de tal manera que si asignamos valores a  las variables tenemos una solución. En el caso del acertijo de Einstein, una de las variables del problema es x_pc, de forma que si x_pc=1 la persona p vive en la casa c y si x_pc=0 la persona p no vive en la casa c. Podemos definir variables análogas para la bebida, el tabaco y la mascota y, por otro lado, las posiciones que ocupan las casas.

Las restricciones.

Las restricciones representan los requisitos con los que debe cumplir una solución, o de otra manera, son las reglas que deben cumplir los valores de las variables. Siguiendo con el ejemplo de la variable x_pc, sabemos que en cada casa vive una persona y solo una. Por lo tanto, por ejemplo, para la casa verde se debe cumplir la siguiente ecuación:

x_{inglés verde}+x_{sueco verde}+x_{danés verde}+x_{noruego verde}+x_{alemán verde}=1

La suma de las cinco variables correspondientes a la asignación de la casa verde deben sumar 1. Es decir, una variable y solo una debe tomar el valor 1, lo cual se traduce en que una persona y solo una habita en la casa verde.

La función objetivo.

La función objetivo es el indicador que queremos maximizar o minimizar, como, por ejemplo, los costes o los tiempos asociados a alguna actividad. En el caso de este acertijo no hay función objetivo ya que basta con encontrar una solución factible. En muchas ocasiones, los responsables de los gestores indican que es suficiente con disponer de una solución factible. Sin embargo, en la realidad, siempre hay algún KPI que permite diferenciar las soluciones y con el que construir una función objetivo.

Lo que queremos es la solución óptima a nuestro problema, que es aquella solución factible con el mejor valor de la función objetivo (si no es factible, no la podemos poner en práctica y no nos interesa porque no cumple con los requisitos).

Generalización

Los modelos matemáticos para tomar decisiones en situaciones reales comparten la misma estructura.

Así, podemos encontrar variables como x_vcc’  que toma el valor 1 si el vehículo v visita al cliente c’ después de haber visitado al cliente c o, por ejemplo q_pd, que representa la cantidad de producto transportado desde la planta p al centro de distribución d.

Igualmente, los requisitos de negocio se traducen en relaciones entre las variables. Por ejemplo, si un vehículo llega al cliente c’ desde el cliente c, deberá necesariamente salir de c’ hacia algún otro cliente c’’. Es decir, se debe cumplir x_vcc’= ∑_c”x_vc’c” para cualquier vehículo v y clientes c y c’.

Por último, habría una función objetivo. En el caso de las rutas podría ser la distancia total recorrida. Así, si conocemos la distancia entre cualesquiera dos clientes c y c’ (D_cc’), podemos calcular la suma de todas las distancias que recorren todos los vehículos con una expresión parecida a ∑_v∑_c∑_c’D_cc’x_vcc’

La solución

Una vez formulado el modelo, el siguiente paso es resolverlo, es decir, conseguir encontrar el conjunto de valores de todas las variables (la decisión) que cumplen con todas las restricciones (requisitos del cliente) y que minimicen la función objetivo (el KPI que queremos optimizar).

George Dantzig fue el pionero en este ámbito, formulando el llamado método del Simplex en 1947. Desde entonces, las técnicas de resolución se fueron extendiendo y perfeccionando y hoy tenemos a nuestra disposición diferentes solvers que incorporan estos métodos. 

En este caso, ofrecemos una implementación en Python con la librería de PuLP y CBC como solver. Está desarrollado en un Google Colaboratory Jupyter notebook, cuyo código se puede ejecutar mediante la opción de ‘Run all’ en el menú ‘Runtime’ (o con el atajo Control+F9). De esta manera, se ejecutan todas las celdas de código del notebook.

En la última de ellas se muestran las tablas que copiamos a continuación y que constituyen la asignación que respeta todas las reglas.

Por cierto: el pez lo tiene el alemán.

	casa	tabaco	bebida	mascota
inglés	roja	pall	leche	pájaros
sueco	blanca	bluemaster	cerveza	perro
danés	azul	blends	té	caballo
noruego	amarilla	durnhill	agua	gato
alemán	verde	prince	café	pez

	Verde	Blanca	Amarilla	Roja	Azul
Posición	4	5	1	3	2