Contenido

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 D_I es el conjunto de valores posibles para la variable X_I. Cada restricción C_j 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:
- D_PARA = {1,4,5,8}
- D_B = {2,3,5,7,9}
- D_VS = {4,8,9}
- D_D = {1,4,5,7,9}
restricciones:
- VS₁(A, C): {(1,7); (1,9); (5,9); (8,9)}
- VS₂(A, D): (1.1); (1.5); (5.5); (5.9); (8.9)}
- VS₃(C, D): {(4.1); (8.1); (9.7)}
- VS₄(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.

Hablamos de instanciación parcial o total (tome todas las variables o no), e inconsistente o consistente (valide las restricciones o no). Por tanto, una solución válida es una instanciación total y coherente.

Resolución ingenua: generar y probar

Generamos todas las asignaciones posibles. Luego verificamos si son consistentes, tan pronto como una asignación sea consistente, tenemos una solución válida.

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 X_I no afectado en A, restamos de D_Xi cualquier valor v tal que la asignación A ∪ {(X_I, v)} es inconsistente. Los valores autorizados se propagan en profundidad.

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

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.