Programación declarativa: el superbuscador (III)

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:

	type CheckPoint = {
	CPId : string // checkpoint Id
	Lat : double // latitude
	Lon : double // longitude
	}

view raw CheckPoint.fs hosted with ❤ by GitHub

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:

	let checkPoints =
	[ {CPId = "Ciudad A"; Lat = 43.3618742; Lon = -8.4126837}
	{CPId = "Ciudad B"; Lat = 42.8802049; Lon = -8.5447697}
	...
	]

	let distance (a : CheckPoint) (b : CheckPoint) : double =
	sqrt ((a.Lat - b.Lat)2. + (a.Lon - b.Lon)2.)

view raw checkPoints.fs hosted with ❤ by GitHub

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.

	type InterestPoint = {
	IPId : string // interest point Id
	CPId : string // checkpoint Id
	PTId : string // (interest)point type Id
	Prices : double list // prices per day
	}

view raw InterestPoint.fs hosted with ❤ by GitHub

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):

	let interestPoints =
	[ {IPId = "Playa A" ; CPId = "Ciudad A"; PTId = "Costa" ; Prices = [ 1.; 1.; 1.; 1.; 1.; 1.; 1.; 1.; 1.; 1.]}
	{IPId = "Playa B" ; CPId = "Ciudad B"; PTId = "Costa" ; Prices = [ 1.; 1.; 1.; 1.; 1.; 1.; 1.; 1.; 1.; 1.]}
	...
	{IPId = "Cultura A 1"; CPId = "Ciudad A"; PTId = "Cultura" ; Prices = [ 2.; 2.; 2.; 0.; 2.; 2.; 2.; 2.; 2.; 2.]}
	{IPId = "Cultura A 2"; CPId = "Ciudad A"; PTId = "Cultura" ; Prices = [ 4.; 4.; 4.; 4.; 4.; 4.; 0.; 0.; 0.; 0.]}
	...
	{IPId = "Popular A 1"; CPId = "Ciudad A"; PTId = "Popular" ; Prices = [ 4.; 3.; 3.; 3.; 0.; 4.; 4.; 0.; 0.; 0.]}
	...
	{IPId = "Hotel A 1" ; CPId = "Ciudad A"; PTId = "Alojamiento"; Prices = [30.; 30.; 30.; 30.; 45.; 45.; 50.; 30.; 30.; 0.]}
	{IPId = "Hotel A 2" ; CPId = "Ciudad A"; PTId = "Alojamiento"; Prices = [36.; 0.; 20.; 20.; 0.; 0.; 0.; 20.; 20.; 20.]}
	...
	{IPId = "Hotel B 1" ; CPId = "Ciudad B"; PTId = "Alojamiento"; Prices = [20.; 20.; 30.; 35.; 0.; 0.; 50.; 20.; 20.; 20.]}
	{IPId = "Hotel B 2" ; CPId = "Ciudad B"; PTId = "Alojamiento"; Prices = [20.; 20.; 30.; 35.; 0.; 0.; 50.; 20.; 20.; 20.]}
	...

view raw interestPoints.fs hosted with ❤ by GitHub

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.

	type UserPreferences = {
	MinDays : double // minimum total days
	MaxDays : double
	MinDayDistance : double // minimum checkpoint to next checkpoint distance
	MaxDayDistance : double
	MinTotalDistance : double // minimum travel total distance
	MaxTotalDistance : double
	MinTotalPrice : double // minimum travel total price
	MaxTotalPrice : double
	MinDaysPerCheckPoint : double // minimum days on each checkpoint
	MaxDaysPerCheckPoint : double
	DistanceImportance : double // how important is maximize/minimize total distance
	PriceImportance : double
	IPNumberImportance : double
	PTPrefs : UserPointTypePreferences list
	}

view raw UserPreferences.fs hosted with ❤ by GitHub

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):

	type UserPointTypePreferences = {
	PTId : string // (interest)point type Id
	MinPerCheckpoint : double // minimum interestpoint (of that type) on each checkpoints
	MaxPerCheckpoint : double
	MinTotal : double // minimum interestpoint (of that type) on all checkpoints
	MaxTotal : double
	}

view raw UserPointTypePreferences.fs hosted with ❤ by GitHub

Un ejemplo de preferencias de usuario podrían ser:

	let userPreferences = {
	MinDays = 3.
	MaxDays = 6.
	MinDayDistance = 0.
	MaxDayDistance = 0.68
	MinTotalDistance = 0.
	MaxTotalDistance = 1e6
	MinTotalPrice = 0.
	MaxTotalPrice = 999999.
	MinDaysPerCheckPoint = 0.
	MaxDaysPerCheckPoint = 1.
	DistanceImportance = 0.1 // ej. dando cierta importancia a mayor distancia recorrida
	PriceImportance = -1. // ej. lo más barato posible
	IPNumberImportance = 0.
	PTPrefs =
	[ {PTId = "Costa" ; MinPerCheckpoint = 0.; MaxPerCheckpoint = 9.; MinTotal = 1.; MaxTotal = 99.}
	{PTId = "Cultura" ; MinPerCheckpoint = 0.; MaxPerCheckpoint = 9.; MinTotal = 1.; MaxTotal = 99.}
	{PTId = "Popular" ; MinPerCheckpoint = 0.; MaxPerCheckpoint = 9.; MinTotal = 1.; MaxTotal = 99.}
	{PTId = "Alojamiento"; MinPerCheckpoint = 1.; MaxPerCheckpoint = 1.; MinTotal = 0.; MaxTotal = 99.}
	]
	}

view raw userPreferences.fs hosted with ❤ by GitHub

Otros

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

	type CheckPointVar = {cp : CheckPoint; v : Variable}
	type PriceVar = {ip : InterestPoint; v : Variable}
	type EdgeVar = {a : CheckPoint; b : CheckPoint; v : Variable}

view raw anonymousTypes.fs hosted with ❤ by GitHub

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, ...).

	let solveProblem (chkpts : CheckPoint list)
	(ipts : InterestPoint list)
	(userp : UserPreferences ) : (int * InterestPoint list) list =

	...

view raw solveProblem.fs hosted with ❤ by GitHub

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:

	Solution found:
	+ Total travel price: 60.00 eur
	+ Total travel days: 3
	+ Total travel distance: 1.178056 Km
	+ Planning:
	#1 Day 8 (Ciudad C) ~ 0.678604 Km
	* Popular : Popular C 1 , price = 2.00 eur
	* Alojamiento : Hotel C 1 , price = 20.00 eur

	#2 Day 9 (Ciudad B) ~ 0.499452 Km
	* Costa : Playa B , price = 1.00 eur
	* Alojamiento : Hotel B 1 , price = 20.00 eur

	#3 Day 10 (Ciudad A)
	* Cultura : Cultura A 1 , price = 2.00 eur
	* Alojamiento : Hotel A 3 , price = 15.00 eur

view raw solution.txt hosted with ❤ by GitHub

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)