Programación con restricciones

Gecode es una herramienta para el desarrollo
de sistemas basados en restricciones
◦ Abierto
◦ Gratuito
◦ Portable
◦ Eficiente
◦ Concurrente
Está disponible para Linux, Windows y Mac OS
www.gecode.org
Secuencia mágica

Constructura:
◦ En la constructora se inicializan las variables de
decisión, se declaran las restricciones y el
branching
◦ El branching es, a grandes rasgos, la definición de
por dónde debe empezar y hacia dónde debe ir la
búsqueda de una solución al problema

Todo modelo debe incluir:
◦ Constructora adicional que actualiza el valor de las
variables de decisión
◦ Función Copy() que devuelve una copia del espacio
apoyándose en la constructora anterior

Las variables de decisión se pueden imprimir
como si fueran variables de C++

En el main se deben seguir los siguientes
pasos:
◦ Se crea el modelo
◦ se crea el motor de búsqueda para el modelo
◦ se obtiene una (o varias) de las soluciónes y se
imprimen.

#include <gecode/int.hh>

IntVar
◦ Son el equivalente a los var int de Minizinc.
◦ Constructora:
 IntVar(home, liminf, limsup)

IntSet
◦ Son el equivalente a los conjuntos de minizinc.
◦ Constructora:
 IntSet(home, minDom, maxDom)
◦ Se puede construir una variable entera pasándole
un IntSet como dominio:
 IntVar x(home, IntSet(-10, 10)

IntVarArray
◦ Son el equivalente a los array of var de Minizinc
◦ Constructoras:
 IntVarArray(home, n, liminf, limsup)
◦ Acceso:
 IntVarArray x(home, 10, 0, 9)
 x[i] será la posición i-ésima del array siendo i un
entero.

Matrices
◦ Las matrices en Gecode son algo especiales.
◦ Creación:
 IntVarArray x(home, N*M, a, b)
 Matrix<IntVarArray> m(x, N, M)
◦ Acceso:
 m(i,j)
 m.row(i): Fila i-ésima de la matriz
 m.col(i): Columna i-ésima de la matriz

Restricciones


Devuelven “trozos” de la matriz que cumplen
ciertas condiciones
Tienen su versión para arrays

Relaciones:
◦ Las relaciones en Gecode se definen de una manera
especial:
 rel(home, var1, rel_type, var2)
Ejemplo:
rel(home, x, ITR_LE, y) => x< y
Tipos de relaciones:

Count(home, var1, var2, rel_type, c)
◦ c será igual al número de veces que aparece var2 en
el vector var1.

Member(home,x,y):
◦ El valor y debe aparecer por lo menos una vez en el
array x

Distinct(home, x):
◦ Todos los valores del array x deben ser distintos

Operaciones aritméticas


Heredan de la clase Space.
Junto con la clase Options permiten
parametrizar problemas de tamaño variable

Soporte de búsqueda

Main


Es una herramienta gráfica que incluye
Gecode.
Permite ver gráficamente cómo progresa la
búsqueda de una solución.

¿Cómo usar Gist en un modelo?
◦ Solo hace falta cambiar el main:
 Se crea el modelo
 Se crea la instancia de Gist para el modelo
 Se elige el motor de búsqueda y se le pasa el modelo y
las opciones de Gist


Descargar el ejecutable correspondiente a la
versión de Visual Studio del sistema.
Al crear un proyecto nuevo acceder a
propiedades del proyecto->C/C++ y agregar
la carpeta /Gecode/include en Directorios de
inclusión adicionales

En las opciones del vinculador añadir la
carpeta /Gecode/lib en Directorios de
bibliotecas adicionales

Es útil para aplicaciones reales

Es extremadamente rápido

Es intuitivo

La documentación disponible es excelente

Muy recomendable aprender a usarlo
Descargar

Gecode