El gráfico compuesto de restricciones es un gráfico no dirigido ponderado por nodos asociado con un problema de optimización combinatoria dado planteado como un problema de satisfacción de restricciones ponderadas . Desarrollada e presentada por Satish Kumar Thittamaranahalli (TK Satish Kumar), la idea del gráfico compuesto de restricciones es un gran paso hacia unificar 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) es una generalización de un problema de satisfacción de restricciones en el que las restricciones ya no son "duras", sino que se extienden para especificar costos no negativos asociados con las tuplas . El objetivo entonces es encontrar una asignación de valores a todas las variables de sus respectivos dominios de modo que se minimice el costo total. Los problemas de satisfacción de restricciones ponderadas encuentran 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 NP-difíciles de resolver en general, varias subclases se pueden resolver en tiempo polinomial cuando sus restricciones ponderadas exhiben tipos específicos de estructura numérica. Las subclases manejables también se pueden identificar analizando la forma en que se imponen las restricciones a las variables. Específicamente, un problema de satisfacción de restricciones ponderadas se puede resolver en tiempo exponencial sólo en el ancho del árbol de su gráfico de interacción variable (red de restricciones). Sin embargo, un inconveniente 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 gráfico compuesto de restricciones proporciona un marco unificador para representar tanto la estructura gráfica de las interacciones variables como la estructura numérica de las restricciones ponderadas. Puede construirse utilizando un procedimiento simple de tiempo polinomial; y un problema de satisfacción de restricción ponderada dado se puede reducir al problema de calcular la cobertura de vértice ponderada mínima para su gráfico compuesto de restricción asociado. Las propiedades computacionales "híbridas" del gráfico compuesto de restricciones se reflejan en los dos resultados importantes siguientes:
(Resultado 1) El gráfico compuesto de restricciones de un problema de satisfacción de restricciones ponderado 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 manejables en virtud de la estructura numérica de sus restricciones ponderadas tienen gráficos compuestos de restricciones asociados que son de naturaleza bipartita .
El resultado 1 muestra que el gráfico compuesto de restricciones se puede utilizar para capturar la estructura gráfica de las interacciones variables (ya que una cobertura de vértice ponderada mínima para cualquier gráfico se puede calcular en tiempo exponencial solo en el ancho del árbol de ese gráfico). El resultado 2 muestra que el gráfico compuesto de restricciones también se puede utilizar para capturar la estructura numérica de las restricciones ponderadas (ya que una cobertura de vértice ponderada mínima se puede calcular en tiempo polinómico para gráficos 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 gráfico compuesto de restricciones del WCSP que directamente en el WCSP. [3] [4]