Programación de restricciones
La Programación de Restricciones (CPP) resuelve problemas de tipo Satisfacción de Restricciones (CSP). Un CSP es un problema de modelado en forma de un conjunto de restricciones impuestas a las variables, cada una de estas variables tomando sus valores en un dominio definido.
Un CSP se define por un triplete (X, D, C, R) tal que:
- X = {X1, X2,…,Xno} el conjunto de variables del problema;
- D una función que se asocia con cada variable XI su dominio (conjunto de valores posibles) D (XI);
- C = C1, VS2,…,VSk} el conjunto de restricciones.
Solución de programación de restricciones
Resolver un CSP consiste en asignar valores a las variables, de manera que se satisfagan todas las restricciones. Para ello, necesitamos un vocabulario preciso:
- Una asignación es una instancia de ciertas variables por valores de sus respectivos dominios. Denotaremos por A = {(X1, V1),…} asignación que instancia la variable X1 por el valor V1, etc;
- Se dice que una asignación es total si instancia todas las variables del problema; de lo contrario, se dice que es parcial;
- Una asignación A viola una restricción Ck si todas las variables de Ck se instancian en A y si la relación definida por Ck no se comprueba por asignación:
- Una asignación total o parcial es consistente si no viola ninguna restricción; de lo contrario, se dice que es inconsistente;
- Una solución CSP es una asignación total consistente.
En la programación con restricciones, cuando un CSP no tiene solución, se dice que está sobre-restringido. En este caso, se puede encontrar la asignación total que viola la menor cantidad de restricciones posibles. Entonces hablamos de max-CSP.
Otra posibilidad en la programación de restricciones es asignar un peso a cada restricción, luego se busca minimizar el peso de las restricciones violadas. Hablamos entonces de VCSP (valorado). Un max-CSP es un VCSP donde todas las restricciones tienen el mismo peso.
Cuando un CSP admite varias soluciones diferentes, se dice que está sub-restringido. Si las soluciones no son todas equivalentes, entonces es posible establecer preferencias entre las soluciones. Agregamos una función que asocia un valor numérico a cada solución, representando la calidad de esta solución. El objetivo es maximizar esta función objetivo. Hablamos entonces de CSOP (satisfacción de restricciones mejoramiento problema).
Ejemplo de programación de restricciones: problema de n-reinas
Un constructor posee un terreno con 16 parcelas (4 filas y 4 columnas) que forman un tablero de ajedrez. Quiere colocar las turbinas eólicas de tal manera que no estén en contacto. Dos aerogeneradores están engranados si están en la misma línea, la misma columna o la misma diagonal.
Programación de restricciones 1
Las variables son las posiciones de las filas y columnas de los aerogeneradores en el tablero de ajedrez. Cada aerogenerador i está asociado a dos variables LI y CI correspondientes respectivamente a la fila y la columna sobre la que colocar el aerogenerador. Tenemos el siguiente modelo de programación de restricciones:
- Variables:
- X = {L1, LOS2, LOS3, LOS4, VS1, VS2, VS3, VS4}
- Áreas:
- D (L1) = D (L2) = D (L3) = D (L4)={1,2,3,4}
- D (C1) = D (C2) = D (C3) = D (C4)={1,2,3,4}
- Restricciones:
- VSlig = allDiff ({L1, LOS2, LOS3, LOS4}) para tener valores LI todos diferentes entre sí
- VScollar = allDiff ({C1, VS2, VS3, VS4}) para tener valores CI todos diferentes entre sí
- VSdm= {CI+ LI ! = Cj+ Lj / para todo i y j en {1, 2, 3, 4} e i! = j}
- VSdd= {CI-LOSI ! = Cj-LOSj / para todo i y j en {1, 2, 3, 4} e i! = j}
- Es la unión de estos juntos.
Este modelado es ingenuo ya que se consideran todas las restricciones sin buscar su significado.
Programación de restricciones 2
Es fácil notar que habrá al menos un aerogenerador por columna del tablero de ajedrez (o línea, etc.). La programación por restricciones consiste entonces en determinar en qué línea se encuentra el aerogenerador colocado en la columna i, se anotará la variable XI :
- Variables:
- X = {X1, X2, X3, X4}
- Áreas:
- D (X1) = D (X2) = D (X3) = D (X4)={1,2,3,4}
- Restricciones:
- VSlig = allDiff ({X1, X2, X3, X4}) para tener valores XI todos diferentes entre sí
- VSdm= {XI+ yo! = Xj+ j / para todo i y j en {1, 2, 3, 4} e i! = j}
- VSdd= {XI-i! = Xj-j / para todo i y j en {1, 2, 3, 4} e i! = j}
- Es la unión de estos juntos.
Discusión
Hay muchas otras formas de modelar el problema. En este caso, ¿cuál es el mejor modelo? Para ello, existen tres criterios para evaluar la pertinencia de la modelización: ¿modeliza mejor el problema? ¿El modelado fue trivial? ¿El modelado resuelve el problema de manera efectiva?
Resolviendo un CSP
Resolver un CSP es un problema Np-Completo en el caso general. El mecanismo de resolución consiste en repetir los dos pasos siguientes:
- reducción de problemas mediante filtrado;
- recorriendo el árbol de búsqueda.
Estos dos pasos recurren a nociones como la consistencia de arcos o la propagación de restricciones que no desarrollaremos en este curso. Hay muchos solucionadores de CSP, como la biblioteca de herramientas OR de Google.
