Programación de restricciones

Programación de restricciones

los programación de restricciones resuelve problemas de toma de decisiones. Un problema de optimización se resuelve sucesivamente después de varios problemas de decisión. Por ejemplo para determinar un camino más corto, buscaremos encontrar un camino de menos de 100 (posible), luego menos de 50 (imposible), luego menos de 75, etc. hasta encontrar la solución óptima. PPC tiene un campo de acción más amplio que los métodos exactos o las metaheurísticas.

Definición

PPC resuelve un problema de satisfacción de restricciones (CSP).

Este último está definido por un triplete con X el conjunto de variables, D el conjunto de dominios y C el conjunto de restricciones. Domaine DI es el conjunto de valores posibles para la variable XI. Cada restricción Cj se define por su aridad (el número de variables con las que se relaciona), la lista de estas variables y el conjunto de tuplas que la satisfacen.

Tomemos un ejemplo de triplete:

  • variables: A, B, C, D
  • áreas:
    • DPARA = {1,4,5,8}
    • DB = {2,3,5,7,9}
    • DVS = {4,8,9}
    • DD = {1,4,5,7,9}
  • restricciones:
    • VS1(A, C): {(1,7); (1,9); (5,9); (8,9)}
    • VS2(A, D): (1.1); (1.5); (5.5); (5.9); (8.9)}
    • VS3(C, D): {(4.1); (8.1); (9.7)}
    • VS4(B, D): {(2,7); (2,9); (5,8); (7,9); (9,9)}

Es posible codificar las restricciones en extensión, por un conjunto de tuplas, o en intención, utilizando operadores cuya semántica es conocida. Una instanciación es una asignación completa de valores a variables, por ejemplo { , , , }. La instanciación es una solución válida si se verifican los valores dados a las variables de las cuales, como todas las restricciones.

Resolución ingenua: generar y probar

Si tenemos un problema con n variables, cada una solo puede tomar dos valores, el procesador hace 1,000,000,000 de cálculos por segundo. Para 30 variables, la resolución toma como máximo 1s, para 50 variables, pasamos a 11 días; para 70 variables es necesario esperar 317 siglos.

Resolución de retroceso

Generamos el árbol de asignaciones y luego viaje en profundidad. Si una asignación parcial (durante el recorrido) es incoherente, se corta el subárbol correspondiente.

Es similar a Branch & Cut.

programación de restricciones de retroceso

Este método no genera todo el árbol de posibilidades a diferencia del método ingenuo. Por otro lado, todas las restricciones se prueban en cada asignación parcial y el tiempo de convergencia también depende del orden de las variables.

Resolución por propagación de tensiones

Este método consiste en propagar las restricciones en el dominio de las variables.

Por ejemplo, tomemos x entre 0 y 10 e y entre 3 y 9; luego con la restricción x> y podemos restringir el dominio de X entre 4 y 10.

propagación de programación de restricciones

Hay tres casos en los que se propaga la información:

  • cuando se reduce un dominio
  • cuando se cambia uno de los terminales de dominio
  • cuando un dominio es un singleton.

Entonces es posible propagar la información una vez (consistencia de nodo), dos veces (consistencia de arco) o más.

En la consistencia de nodos, para cada variable XI no afectado en A, restamos de DXi cualquier valor v tal que la asignación A ∪ {(XI, v)} es inconsistente. Los valores autorizados se propagan en profundidad.

propagación de programación de restricciones

En el arco-consistencia, para cada variable XI no afectado en A, restamos de DXi cualquier valor v tal que haya una variable Xj no asignado para el cual, para cualquier valor w de DXj, la asignación A ∪ {(XI, v); (Xj, w)} es inconsistente. Los valores autorizados se propagan en profundidad.

propagación de programación de restricciones

Cuanto mayor sea la tupla de comparación, mayor será el tiempo de cálculo para definir el dominio válido de las variables. La consistencia del arco es menos eficiente que la consistencia del nudo si los dominios son grandes.

Compartir, repartir