Grafo compuesto de restricciones

El grafo compuesto de restricciones es un grafo no dirigido con nodos ponderados asociado a un problema de optimización combinatoria dado, planteado como un problema de satisfacción de restricciones ponderadas . Desarrollado e introducido por Satish Kumar Thittamaranahalli (TK Satish Kumar), la idea del grafo compuesto de restricciones representa un gran avance hacia la unificación de diferentes enfoques para explotar la "estructura" en problemas de satisfacción de restricciones ponderadas. ^{[ 1 ] [ 2 ]}

Un problema de satisfacción de restricciones ponderadas (WCSP, por sus siglas en inglés) es una generalización de un problema de satisfacción de restricciones en la que las restricciones ya no son "rígidas", sino que se extienden para especificar costos no negativos asociados con las tuplas . El objetivo es encontrar una asignación de valores a todas las variables de sus respectivos dominios de manera que se minimice el costo total. Los problemas de satisfacción de restricciones ponderadas tienen innumerables aplicaciones en inteligencia artificial e informática . También se les conoce como campos aleatorios de Markov (en estadística y procesamiento de señales ) y problemas de minimización de energía (en física ).

Si bien los problemas de satisfacción de restricciones ponderadas son, en general, NP-difíciles de resolver, varias subclases pueden resolverse en tiempo polinomial cuando sus restricciones ponderadas presentan estructuras numéricas específicas. También se pueden identificar subclases tratables analizando la forma en que se aplican las restricciones a las variables. En concreto, un problema de satisfacción de restricciones ponderadas puede resolverse en tiempo exponencial solo en función del ancho de árbol de su grafo de interacción de variables (red de restricciones). Sin embargo, una desventaja importante de la red de restricciones es que no proporciona un marco computacional para aprovechar la estructura numérica de las restricciones ponderadas.

A diferencia de la red de restricciones, el grafo compuesto de restricciones proporciona un marco unificador para representar tanto la estructura gráfica de las interacciones entre variables como la estructura numérica de las restricciones ponderadas. Se puede construir mediante un procedimiento sencillo de tiempo polinomial; y un problema dado de satisfacción de restricciones ponderadas se reduce al problema de calcular la cobertura mínima ponderada de vértices para su grafo compuesto de restricciones asociado. Las propiedades computacionales "híbridas" del grafo compuesto de restricciones se reflejan en los dos resultados importantes siguientes:

(Resultado 1) El grafo compuesto de restricciones de un problema de satisfacción de restricciones ponderadas dado tiene el mismo ancho de árbol que su red de restricciones asociada.

(Resultado 2) Muchas subclases de problemas de satisfacción de restricciones ponderadas que son tratables en virtud de la estructura numérica de sus restricciones ponderadas tienen grafos compuestos de restricciones asociados que son de naturaleza bipartita .

El resultado 1 muestra que el grafo compuesto de restricciones puede utilizarse para capturar la estructura gráfica de las interacciones entre variables (ya que una cobertura de vértices ponderada mínima para cualquier grafo puede calcularse en tiempo exponencial solo en función del ancho de árbol de dicho grafo). El resultado 2 muestra que el grafo compuesto de restricciones también puede utilizarse para capturar la estructura numérica de las restricciones ponderadas (ya que una cobertura de vértices ponderada mínima puede calcularse en tiempo polinomial para grafos bipartitos).

Empíricamente, al resolver un WCSP, se ha demostrado que es más ventajoso aplicar algoritmos de paso de mensajes y programación lineal entera en el grafo compuesto de restricciones del WCSP que directamente en el WCSP. ^{[ 3 ] [ 4 ]}