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, pueden resolverse mediante algoritmos diseñados para este tipo de problemas. Los grafos de unión y los árboles de unión de un problema de satisfacción de restricciones son grafos que representan su problema dual o un problema derivado 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 se construyen de manera que se imponga una especie de equivalencia con el problema original. En particular, el dominio de una variable del problema dual contiene un elemento para cada tupla que satisface la restricción original correspondiente. De esta forma, una variable dual puede tomar un valor si y solo si la restricción original correspondiente es satisfecha por la tupla 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.${\displaystyle x=1,y=2}$mientras que otra variable dual toma el valor correspondiente a${\displaystyle y=3,z=1}$, que asigna un valor diferente a${\displaystyle y}$.

En términos más generales, 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 que impone la igualdad de todas las variables compartidas.

En el problema dual, todas las restricciones son binarias. Todas exigen que dos valores, que son tuplas, coincidan en una o más variables originales.

El grafo dual representa cómo se restringen las variables en el problema dual. Más precisamente, el grafo dual contiene un nodo por cada variable dual y una arista por cada restricción entre ellas. Además, la arista entre dos variables está etiquetada con las variables originales que se mantienen iguales entre estas dos variables duales.

El grafo dual se puede construir directamente a partir del problema original: contiene un vértice para cada restricción y una arista entre cada par de restricciones que comparten variables; dicha arista está etiquetada con estas variables compartidas.

En el grafo dual, algunas restricciones pueden ser innecesarias. De hecho, las restricciones duales imponen la igualdad de las variables originales, y algunas restricciones pueden ser redundantes debido a la transitividad de la igualdad. Por ejemplo, si ${\displaystyle C_{2}}$y${\displaystyle C_{1}}$están unidos por una arista cuya etiqueta contiene${\displaystyle y}$y también lo son${\displaystyle C_{1}}$y${\displaystyle C_{3}}$, igualdad de${\displaystyle y}$En las tres variables duales se garantiza. Como resultado, una restricción dual entre${\displaystyle C_{2}}$y${\displaystyle C_{3}}$hacer cumplir la igualdad de${\displaystyle y}$No es necesario y podría eliminarse si estuviera presente.

Un grafo obtenido a partir del grafo dual eliminando algunas aristas redundantes se denomina grafo de unión . Si es un árbol, se denomina árbol de unión . El problema dual puede resolverse a partir de un grafo de unión, ya que todas las aristas eliminadas son redundantes. A su vez, el problema puede resolverse de manera eficiente si dicho grafo de unión es un árbol, utilizando algoritmos diseñados para problemas de satisfacción de restricciones acíclicas.

Encontrar un árbol de unión, si existe, se puede hacer explotando la siguiente propiedad: si un grafo dual tiene un árbol de unión, entonces todos los árboles de expansión de peso máximo del grafo son árboles de unión, si las aristas están ponderadas por el número de variables que las restricciones correspondientes imponen que sean iguales. Un algoritmo para encontrar un árbol de unión, si existe, procede de la siguiente manera. En el primer paso, se asignan pesos a las aristas: si dos nodos representan restricciones que comparten${\displaystyle n}$variables, al borde que las une se le asigna un peso${\displaystyle n}$En el segundo paso, se busca un árbol de expansión de peso máximo. Una vez encontrado, se comprueba si garantiza la igualdad requerida entre las variables. Si es así, este árbol de expansión es un árbol de unión.

Otro método para determinar si un problema de satisfacción de restricciones tiene un árbol de unión utiliza el grafo primal del problema, en lugar del grafo dual. El grafo primal de un problema de satisfacción de restricciones es un grafo cuyos nodos son variables del problema y cuyas aristas representan la presencia de dos variables en la misma restricción. Existe un árbol de unión para el problema si:

1. El grafo primal es cordal ;
2. Las variables de cada camarilla máxima del grafo primal son el alcance de una restricción y viceversa; esta propiedad se llama conformabilidad .

A su vez, la cordalidad se puede verificar mediante un ordenamiento de cardinalidad máxima de las variables. Dicho ordenamiento también puede utilizarse, si se cumplen las dos condiciones anteriores, para hallar un árbol de unión del problema. Ordenando las restricciones según su variable más alta, un algoritmo para generar un árbol de unión procede desde la última restricción hasta la primera; en cada paso, una restricción se conecta con la restricción que comparte el mayor número de variables con ella entre las restricciones que la preceden en el ordenamiento.

No todos los problemas de satisfacción de restricciones tienen un árbol de unión. Sin embargo, es posible modificarlos para que adquieran uno. La agrupación de árboles de unión es un método específico para modificar problemas de tal manera que adquieran un árbol de unión. Esto se logra fusionando restricciones, lo que generalmente aumenta el tamaño del problema; sin embargo, resolver el problema resultante es sencillo, como ocurre con todos los problemas que tienen un árbol de unión.

Los métodos de descomposición generalizan la agrupación por árbol de unión al agrupar variables de tal manera que el problema resultante tenga un árbol de unión. Estos métodos asocian directamente un árbol con los problemas; los nodos de este árbol son variables y/o restricciones asociadas al problema original. Al fusionar las restricciones basadas en este árbol, se puede generar un problema que tenga un árbol de unión, el cual se puede derivar fácilmente del árbol de descomposición. Alternativamente, se puede construir un problema binario acíclico directamente a partir del árbol de descomposición.

• Dechter, Rina (2003). Procesamiento de restricciones . Morgan Kaufmann.ISBN 978-1-55860-890-0
• Downey, Rod; M. Fellows (1997). Complejidad parametrizada . Springer.ISBN 978-0-387-94883-6
• Georg Gottlob; Nicola Leone; Francesco Scarcello (2001). "Descomposiciones de hiperárboles: una revisión" . MFCS 2001. págs. 37–57 . 

• Transformación oculta