En el anterior post habíamos introducido las herramientas que utilizaremos para resolver el problema, así como los datos concretos con los que vamos a trabajar. También habíamos indicado la función que resolverá finalmente el desafío y el tipo de resultado que queremos obtener.
Es pues, momento de escribir nuestras primeras ecuaciones.
NOTA: he decidido introducir los elementos según surjan, de forma que mostraré primero los más sencillos y luego los más complicados, ésto hará (quizás) que no se vea porqué introduzco determinada variable en determinado momento, pero es con la esperanza de hacer la lectura más rápida y sencilla pues, si explicara el porqué de mis decisiones, la serie se haría mucho más larga. Cualquier duda no obstante ¡a los comentarios!.
Variables y restricciones
El meollo, la injundia de todo este tema, es saber especificar (que no resolver) nuestro problema en base a un sistema de inecuaciones lineales. Si ésto te asusta, te sugiero leer el antiguo post Programación lineal y entera, pero verás que con un poco de práctica no es tan difícil.
Los elementos básicos con que trabajaremos serán las variables y las restricciones. Las variables pueden estar restringidas a tomar únicamente ciertos valores, se dice que una variables es booleana si sólo toma los valores 0 y 1; es entera si sólo toma valores enteros y real, si toma valores reales.
Las restricciones que podemos indicar son únicamente inecuaciones lineales en base a nuestras variables, por ejemplo:
Y realmente no nos hace falta nada más.
Algunos símbolos
Éste apartado lo puedes leer cuando tengas dudas al leer las ecuaciones (aunque son muy sencillas y explicaré cada una de ellas). Por comodidad (las ecuaciones serían muy farragosas de otro modo) y dado que usaremos sólo unas pocas variables, vamos a definir algunos símbolos que usaremos en lo que queda de serie:
-
Las variables de nuestro sistema de inecuaciones (en el ejemplo anterior x1) las indicaremos como mayúsculas y uno o varios subíndices, por ejemplo, la variable que indique si viajaremos el primer día será D1. En realidad, puedes pensar que D es un array y los subíndices los índices del array (por ejemplo D[1]).
-
Las letras con estilo "Blackboard bold" (o "negrita de pizarra") indicarán un conjunto de índices (los días 1º, 2º, 3º, ..., los checkpoints 1º, 2º, 3º, ...). Por ejemplo:
-
Cuando queramos indicar una variable de índice de algún conjunto, lo indicaremos diciendo que pertenece a alguno de los anteriores, por ejemplo:
significa "para cada d que pertenece al conjunto ID" o, en nuestro caso, "para cada día". -
El último símbolo, nos permitirá simplificar la suma de muchas variables, por ejemplo, supongamos que un requisito es que "los días del viaje deben ser siempre 3", entonces, escribiríamos que:
pero suele resultar más corto escribirlo como
que significaría más o menos "la suma, para cada d (que es un IDía), del valor Dd, debe ser 3".
Como ves son pocos, muy sencillos y nos ayudarán a simplificar las restricciones de nuestro problema.
Restricción 1: cada día, sólo podemos estar, a lo sumo, en un único checkpoint
Parece lógico, cuando empezamos el viaje, estamos en un checkpoint, vemos sus puntos de interés y nos desplazaremos al siguiente, así, cada día del viaje, sólo podemos estar en un único checkpoint. Por supuesto, habrá días en los que no estaremos en ningún checkpoint.
La variables de los días ya la hemos mencionado, pero definamoslas adecuadamente:
-
La letra D será la variable de los "días en que viajamos", su índice es sólo el número de día (día 1, día 2, ...), serán booleanas y nos indicarán con 1 si ese día forma parte del viaje y con 0 si ese día no forma parte del viaje. Por ejemplo, si el 4º día sí forma parte del viaje, entonces forzosamente será que D4 = 1. Ten en cuenta que el número de días en D no son los días del viaje, son todos los posibles (ej. queremos rastrear rutas en 30 días, pero luego buscar rutas de 5 días entre éstos 30). En el código F# éstas quedan definidas como:
-
La letra C será la variable de los "en que checkpoint estoy que día", su índice será un día y un checkpoint, serán booleanas y nos indicarán con 1 si para ese día estamos en ese checkpoint y con 0 si ese día no estamos en ese checkpoint. Por ejemplo, si el 4º día no estamos en el checkpoint 2º, entonces forzosamente será que C4,2 = 0. Puedes verla como una matriz bidimensional de días y checkpoints. En F# la definiremos como:
Con sólo estas dos variables, ya podemos especificar la restricción indicada: "cada día, sólo podemos estar, a lo sumo, en un único checkpoint":
Es decir, hemos indicado un total de "nº de días" inecuaciones y cada una de ellas es la suma de las variables que indican si estamos en un checkpoint en ese día, donde dicha suma podrá ser 0 (en ese día no estamos en ningún checkpoint) o 1 (en ese día estamos en un único checkpoint).
No puede haber dos checkpoint seleccionados el mismo día, porque su suma sería 2 y como esas variables son booleanas, no puede ocurrir que una valga 1 y otra -1 (con suma nula).
En F# la forma de expresar esta restricción puede ser:
Sencillo ¿verdad?, acabamos de conseguir que nuestra ruta (de haber alguna) cumpla con la condición de que como mucho un checkpoint va a ser seleccionado cada día ¡y sin escribir ningún algoritmo!.
Restricción 2: un día está seleccionado, si y sólo si algún checkpoint para ese día está seleccionado
En la restricción anterior, asegurábamos que como mucho un checkpoint estará seleccionado un día pero, ¿y las variables de día?, si alguna variable C está seleccionada para algún día, obviamente ese día D deberá también estar seleccionado. Es decir, si es C4,2=1 entonces forzosamente deberá ser D4=1. Es decir, "un día está seleccionado, si y sólo si algún checkpoint para ese día está seleccionado":
Pero... ¡un momento!, si las variables de día D sólo pueden tomar valores 0 o 1, ésta restricción hará que siempre se cumpla la condición de la anterior (la restricción 1), luego sólo nos hace falta esta restricción y podemos omitir la anterior.
Este es un aspecto interesante ¿verdad?, no hay ningún problema si introducimos más restricciones de las necesarias, siempre que sean restricciones que queramos que se cumplan. Normalmente, será más fácil de entender y mantener una lista de restricciones más corta (normalmente pero no siempre, pueden ser más complejas) que una larga.
Bien, la ecuación anterior en F# podríamos escribirla así:
Restricción 3: el número de días totales seleccionados está acotado
Nosotros vamos a rastrear rutas en muchos días posibles (por ejemplo 10 o 30), pero el usuario puede indicar que su viaje tenga como mínimo y como máximo un determinado número de días (de entre esos 10 o 30).
¿Te imaginas ya la ecuación?, es muy sencilla, si un día está seleccionado vale 1 y si no 0, por tanto, la suma de las variables de día D está acotada:
Y en F#:
¿A que es más fácil de lo que parecía?, como vemos, la dificultad estriba en reconocer las restricciones que hacen que nuestro problema se cumpla (y eso lo estoy haciendo sin explicar porqué para no alargarme en exceso), una vez definidas ¡la programación lineal resolverá nuestro problema de forma automática!.
En el próximo post, iremos completando con más restricciones que debe cumplir nuestro sistema.
¿Te animas a pensar por ejemplo cómo conseguir que los días seleccionados sean consecutivos?, es decir, de entre (digamos) 30 días, el usuario nos pide no menos de 4 y no más de 7, pero claro, ¡consecutivos!, no podemos decirle que viajará los días 2º, 5º, 12º y 25º, se cumple que son 4 días ¡pero no consecutivos!.
¡Ánimo!
¡Por cierto!, mi especial agradecimiento a @mausch por mostrarme como sobrecargar la función Σ ;)
Más información |
En genbetadev | Programación declarativa: el superbuscador (I)
En genbetadev | Programación declarativa: el superbuscador (II)
En genbetadev | Programación declarativa: el superbuscador (III)
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)
