En el post anterior analizábamos el tipo de problema al que nos enfrentamos, observando el tipo de restricciones que nos impone y concluyendo que mediante un sistema de programación lineal, podíamos cubrir satisfactoriamente una amplia variedad de requisitos. En realidad, desde el punto de vista de resolver nuestro problema, el post anterior era el más importante.

En éste y siguientes post, solucionaremos de forma efectiva el desafío, mostrando de forma simultanea, para cada estrategia utilizada, tanto la representación matemática del sistema de ecuaciones, como su aplicación práctica mediante uno de los más famosos solver disponibles GLPK. Para trasladar los datos del problema al sistema lineal usaremos (aunque yo no estoy muy familiarizado con este lenguaje) F#.

¿Preparado?

Requisitos

Si quieres probar el código que vamos a ir escribiendo (o el código final), puedes usar cualquier lenguaje y librería mientras permita resolver problemas de programación lineal entera. Trasladar el problema no debería resultar nada complicado. De todos modos, yo usaré GLPK desde F# usando un wrapper de Lars Beckmann, se llama GLPKSolver for Optimization.Framework y está disponible en NuGet.

Los datos

Para centrar ideas, veamos los tipos que usaremos y ejemplos de datos representados con ellos.

Check Point

Los CheckPoint son los diferentes hitos por los que puede discurrir nuestro viaje, parece razonable por tanto que sean de la siguiente forma:

Poco hay que decir, cualquier dato relacionado con el mismo (ej. el identificador, nombre, descripción, ...) y las coordenadas geográficas. Un ejemplo de datos y forma simplona de calcular la distancia entre ellos podrían ser:

Interest Point

Los puntos de interés, decíamos que eran cualquier elemento localizado tanto geográfica como temporalmente. Así, una banda de música puede ser un punto de interés, estar en el checkpoint A el primer día, en el checkpoint B el segundo, descansar ("no estar") el tercer día, etc...

Para que el usuario no tenga que hacer una elección individual de cada punto de interés, los podemos agrupar por categorías (ej. ocio, cultura, alojamiento, restauración, ...). En realidad pueden ser muchas otras (ej. un árbol, varias claves, por propiedades, etc...) pero se entiende la idea.

IPId es el identificador del punto de interés, CPId el checkpoint en el que está, PTId es la categoría a la que pertenece y Prices es el precio que tiene para cada uno de los días a "rastrear", por comodidad y simplicidad, si el precio es 0, asumiremos que ese punto de interés para ese día no está disponible (lógicamente no es una solución que valdría para un código real), así por ejemplo podemos indicar los días en que está cerrado un restaurante, dejar sólo abierto el día en que se celebra determinada fiesta popular, etc... Algunos datos de ejmplo podrían ser (para 10 días en que se rastrearán rutas):

User Preferences

Las preferencias de usuario son todos los parámetros que le vamos a dejar modificar, caben muchos más de los que pongo aquí (como dejar fijo un checkpoint inicial y/o final; descartar el pasar por cierto checkpoint; no querer cierto punto de interés concreto; etc...), pero veremos que cada una de las reglas se puede especificar de forma independiente del resto, favoreciendo la refactorización y mantenimiento.

Los únicos valores de los que decir algo son: Distance-, Price- y IPNumberImportance, que permiten indicar al usuario un valor de importancia respecto de los otros, de forma que, como se pedía, pueda balancear las prioridades que él desea (ej. prefiero la distancia mientras el precio no sea demasiado caro); además, les permite maximizar (con valores positivos) o minimizar (con valores negativos) cada factor ¡puede incluso preferir que sea lo más caro posible! (con frecuencia los clientes Estadounidenses eligen las habitaciones más caras porque piensan que así obtendrán mejor servicio).

El tipo UserPointTypePreferences permite indicar parámetros para cada categoría de punto de interés (por ejemplo y como se pedía, que el usuario pueda decir que, a lo largo del viaje, desea ir al menos a 4 conciertos):

Un ejemplo de preferencias de usuario podrían ser:

Otros

Por comodidad, usaré también otros tipos intermedios (parece que en F# no se pueden crear tipos anónimos):

El algoritmo

Bien, ya tenemos todos los ingredientes, ahora ya sólo nos queda ir desgranando cada una de las estrategias que vamos a utilizar para representar nuestro problema como un sistema lineal de inecuaciones en variables mixtas (habrá términos que sólo podrán tomar valor 0/1, otros cualquier natural, otros cualquier real, ...).

Lo que devolverá esta función es la lista de los días seleccionados (ej. 4º, 5º y 6º) junto con la lista de puntos de interés seleccionados para dicho día. Con esta información, emitir un informe como el siguiente, es inmediato:

En el próximo post, las primeras líneas de código ¿te animas a pensar sobre ellas?.

Más información |
En genbetadev | Programación declarativa: el superbuscador (I)
En genbetadev | Programación declarativa: el superbuscador (II)
MLPI Solver | GLPK, GNU Linear Programming Kit (página oficial)
MLPI Solver | GLPK (en Wikipedia)
GLPK .Net Wrapper | GLPKSolver for Optimization.Framework (página oficial)