Problema dual de satisfacción de restricciones
El problema dual es una reformulación de un problema de satisfacción de restricciones que expresa cada restricción del problema original como una variable. Los problemas duales solo contienen restricciones binarias y, por lo tanto, se pueden resolver mediante algoritmos diseñados para tales problemas. Los gráficos de unión y los árboles de unión de un problema de satisfacción de restricciones son gráficos que representan su problema dual o un problema obtenido del problema dual eliminando algunas restricciones redundantes.
El problema dual de un problema de satisfacción de restricciones contiene una variable para cada restricción del problema original. Sus dominios y restricciones están construidos para imponer una especie de equivalencia con el problema original. En particular, el dominio de una variable del problema dual contiene un elemento por cada tupla que satisface la restricción original correspondiente. De esta manera, una variable dual puede tomar un valor si y solo si la correspondiente tupla satisface la restricción original correspondiente.
Las restricciones del problema dual prohíben que dos variables duales tomen valores que correspondan a dos tuplas incompatibles. Sin estas restricciones, una variable dual puede tomar el valor correspondiente a la tupla mientras que otra variable dual toma el valor correspondiente a , que asigna un valor diferente a .
De manera más general, las restricciones del problema dual imponen los mismos valores para todas las variables compartidas por dos restricciones. Si dos variables duales corresponden a restricciones que comparten algunas variables, el problema dual contiene una restricción entre ellas, lo que impone la igualdad de todas las variables compartidas.
En este ejemplo, las restricciones originales y comparten la variable . En el problema dual, se permite que las variables y tengan valores y porque estos valores concuerdan .
En el problema dual, todas las restricciones son binarias. Todos imponen dos valores, que son tuplas, para coincidir en una o más variables originales.