En el post anterior pusimos de manifiesto que nuestro problema se reducía, básicamente, a establecer una serie de condiciones (restricciones) que deben cumplir las soluciones válidas. Vimos que con una simple relación lineal podíamos definir algunas reglas interesantes sin necesidad de resolver ningún tipo de algoritmo. Hoy continuaremos con otro tipo de restricciones. ¿Te animas?.
Restricción 4: las veces que un checkpoint es seleccionado, está acotada
Unos de los requisitos impuestos, es que el usuario pueda indicar cuantas veces como mucho estaremos (de forma consecutiva o no) en un checkpoint. Como nuestras variables Cd,c indican que día estamos en que checkpoint, sólo debemos sumarlas para saber cuantas veces es seleccionado, así:
Que viene a decir que, "para cada checkpoint, la suma de todos los días en los que se ha seleccionado, debe estar entre los valores indicados por el usuario".
Y en F# podría ser:
Restricción 5: un checkpoint es seleccionado un día, si y sólo si, alguno de sus puntos de interés es seleccionado ese día
De forma similar a cómo un día es seleccionado si y sólo si un checkpoint para ese día es seleccionado, un checkpoint no puede seleccionarse si no hay ningún punto de interés seleccionado y, si hay algún punto de interés de ese checkpoint seleccionado, entonces ese checkpoint debe ser seleccionado.
Vamos entonces a introducir la siguiente variable:
-
La letra P será la variable de los "que punto de interés consumiré que día" (muy parecida a C), su índice será un día, un checkpoint y un punto de interés, serán booleanas y nos indicarán con 1 si para ese día "consumiremos" ese punto de interés (de ese checkpoint) y con 0 si ese día no lo consumimos. Por ejemplo, si el 4º día sí visitaremos el 5º punto de interés, entonces forzosamente será que P4,5 = 1. Puedes verla como una matriz bidimensional de días y puntos de interés. En F# la definiremos como:
Al contrario que los días y checkpoints que están ligados 1 a 1 (un día si y sólo si un checkpoint) aquí tenemos que ligar un único checkpoint con múltiples posibles puntos de interés, si consideramos que no habrá más de 999 puntos de interés seleccionados a la vez en ese día (en realidad y como veremos más adelante, basta con poner el nº máximo de sumandos, que es conocido), podemos establecer dicha relación como:
¡Es fantástico!, si el checkpoint no es seleccionado (es Cd,c=0), la acotación es entre 0 y 0 (999·0=0), luego no puede haber puntos de interés seleccionados (la suma de valores 0/1 debe ser 0, luego todos deben ser 0); si sí es seleccionado, la acotación es entre 1 y 999 (999·1=999) luego puede haber todos los puntos de interés seleccionados que se precisen; y al contrario, si no hay puntos de interés seleccionados, debe ser Cd,c <= 0 ¡luego el checkpoint no puede estar seleccionado! y si sí hay puntos de interés seleccionados, entonces debe ser 1 (o 2, 3, ...) <= 999 Cd,c ¡por lo que sólo puede ser Cd,c = 1!. Acabamos de fijar la relación si y sólo si solicitada.
NOTA: más que en el problema concreto, es en este tipo de representar las "ligaduras" entre los elementos de nuestro problema concreto, que debes prestar atención. Algunas estrategias (como veremos en el siguiente post para exigir que los días de viaje sean consecutivos) puede que no sean fáciles de ver "a simple vista", pero con sólo unas pocas, pueden representarse una cantidad enorme de problemas. ¡Ánimo!.
Como siempre, en F# sería:
Restricción 6: cada día, en cada checkpoint seleccionado, queremos disponer de determinados puntos de interés de cada tipo
Esta restricción dota al usuario de la capacidad de decidir que en cada checkpoint desea al menos dos restaurantes, un hotel, ninguna granja porcina, etc...
En realidad es muy parecida a las anteriores, pero están involucradas además, las categorías de los puntos de interés, representadas por t € T:
Una forma de "leerla" podría ser que "para cada día, checkpoint y tipo de punto de interés, la suma de los puntos de interés respectivos, debe estar entre los valores indicados por el usuario".
Una posible forma de asimilar mejor las ecuaciones es con ejemplos. Supongamos para el 6º día el 8º checkpoint y tan sólo dos categorías de puntos de interés, la primera con los puntos 1 y 2, seleccionando entre 0 y 1 y la segunda con los puntos 3, 4 y 5, seleccionando entre 1 y 2 (un punto de interés aquí sólo pertenece a una categoría ¡pero nada impide que pudiera ser en varias!). Entonces, las ecuaciones quedarían así:
0 · C6,8 <= P6,8,1 + P6,8,2 <= 1 C6,8
1 · C6,8 <= P6,8,3 + P6,8,4 + P6,8,5 <= 2 C6,8
En F#:
Restricción 7: a lo largo de todo el viaje, queremos disponer de determinados puntos de interés de cada tipo
Es exactamente como la anterior, pero sólo creamos una inecuación por cada tipo (categoría) de punto de interés. Útil si queremos ir a lo largo del viaje a un y sólo un parque de atracciones, dándonos igual el día que se nos asigne:
En F#:
Restricción 8: el precio total del viaje está acotado
Esta es muy útil claro y fácil de acotar, tan sólo debemos sumar todos los precios que sean aplicados:
En fin, ya casi hemos cumplido con todos los requisitos, nos faltan dos muy interesantes: hacer que todos los días del viaje sean consecutivos y que las distancias, tanto entre checkpoints como total esté acotada.
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)
En genbetadev | Programación declarativa: el superbuscador (IV)
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)
