Los problemas de satisfacción de restricciones ( CSP ) son cuestiones matemáticas definidas como un conjunto de objetos cuyo estado debe satisfacer una serie de restricciones o limitaciones . Los CSP representan las entidades de un problema como una colección homogénea de restricciones finitas sobre variables , que se resuelve mediante métodos de satisfacción de restricciones . Los CSP son objeto de investigación tanto en inteligencia artificial como en investigación de operaciones , ya que la regularidad en su formulación proporciona una base común para analizar y resolver problemas de muchas familias aparentemente no relacionadas. Los CSP suelen presentar una gran complejidad y requieren una combinación de heurísticas y métodos de búsqueda combinatoria para resolverse en un tiempo razonable. La programación de restricciones (CP) es el campo de investigación que se centra específicamente en abordar este tipo de problemas. [1] [2] Además, el problema booleano de satisfacibilidad (SAT), las teorías del módulo de satisfacibilidad (SMT), la programación entera mixta (MIP) y la programación de conjuntos de respuestas (ASP) son campos de investigación que se centran en la resolución de formas particulares de la problema de satisfacción de restricciones.
Ejemplos de problemas que se pueden modelar como un problema de satisfacción de restricciones incluyen:
Estos suelen contar con tutoriales de solucionadores de CP , ASP, SAT booleano y SMT. En el caso general, los problemas de restricciones pueden ser mucho más difíciles y pueden no ser expresables en algunos de estos sistemas más simples. Los ejemplos de la "vida real" incluyen planificación automatizada , [6] [7] desambiguación léxica , [8] [9] musicología , [10] configuración de productos [11] y asignación de recursos . [12]
La existencia de una solución para un CSP puede verse como un problema de decisión . Esto se puede decidir encontrando una solución, o no logrando encontrar una solución después de una búsqueda exhaustiva ( los algoritmos estocásticos normalmente nunca llegan a una conclusión exhaustiva, mientras que las búsquedas dirigidas a menudo sí lo hacen, en problemas suficientemente pequeños). En algunos casos, se puede saber de antemano que el CSP tiene soluciones, mediante algún otro proceso de inferencia matemática.
Formalmente, un problema de satisfacción de restricciones se define como un triple , donde [13]
Cada variable puede tomar los valores en el dominio no vacío . Cada restricción es a su vez un par , donde es un subconjunto de variables y es una relación aria en el correspondiente subconjunto de dominios . Una evaluación de las variables es una función de un subconjunto de variables a un conjunto particular de valores en el subconjunto de dominios correspondiente. Una evaluación satisface una restricción si los valores asignados a las variables satisfacen la relación .
Una evaluación es consistente si no viola ninguna de las restricciones. Una evaluación está completa si incluye todas las variables. Una evaluación es una solución si es consistente y completa; Se dice que tal evaluación resuelve el problema de satisfacción de restricciones.
Los problemas de satisfacción de restricciones en dominios finitos normalmente se resuelven mediante una forma de búsqueda . Las técnicas más utilizadas son variantes de retroceso , propagación de restricciones y búsqueda local . Estas técnicas también suelen combinarse, como en el método VLNS , y la investigación actual involucra otras tecnologías como la programación lineal . [14]
El retroceso es un algoritmo recursivo. Mantiene una asignación parcial de las variables. Inicialmente, todas las variables están desasignadas. En cada paso, se elige una variable y se le asignan todos los valores posibles por turno. Para cada valor, se verifica la coherencia de la asignación parcial con las restricciones; en caso de coherencia, se realiza una llamada recursiva . Cuando se han probado todos los valores, el algoritmo retrocede. En este algoritmo básico de retroceso, la coherencia se define como la satisfacción de todas las restricciones cuyas variables están asignadas. Existen varias variantes de retroceso. El backmarking mejora la eficiencia a la hora de comprobar la coherencia. El salto hacia atrás permite guardar parte de la búsqueda retrocediendo "más de una variable" en algunos casos. El aprendizaje de restricciones infiere y guarda nuevas restricciones que pueden usarse posteriormente para evitar parte de la búsqueda. La anticipación también se utiliza a menudo para retroceder para intentar prever los efectos de elegir una variable o un valor, determinando así a veces de antemano cuándo un subproblema es satisfactorio o insatisfactorio.
Las técnicas de propagación de restricciones son métodos utilizados para modificar un problema de satisfacción de restricciones. Más precisamente, son métodos que imponen una forma de consistencia local , que son condiciones relacionadas con la consistencia de un grupo de variables y/o restricciones. La propagación de restricciones tiene varios usos. En primer lugar, convierte un problema en uno equivalente pero normalmente más sencillo de resolver. En segundo lugar, puede demostrar la satisfacibilidad o insatisfacción de los problemas. No se garantiza que esto suceda en general; sin embargo, siempre ocurre con algunas formas de propagación de restricciones y/o con ciertos tipos de problemas. Las formas de consistencia local más conocidas y utilizadas son la consistencia de arco , la consistencia de hiperarco y la consistencia de ruta . El método de propagación de restricciones más popular es el algoritmo AC-3 , que impone la coherencia del arco.
Los métodos de búsqueda local son algoritmos de satisfacibilidad incompletos. Pueden encontrar una solución a un problema, pero pueden fracasar incluso si el problema es satisfactoria. Funcionan mejorando iterativamente una asignación completa sobre las variables. En cada paso, se cambia el valor de una pequeña cantidad de variables, con el objetivo general de aumentar la cantidad de restricciones satisfechas por esta asignación. El algoritmo de conflictos mínimos es un algoritmo de búsqueda local específico para CSP y se basa en ese principio. En la práctica, la búsqueda local parece funcionar bien cuando estos cambios también se ven afectados por elecciones aleatorias. Se ha desarrollado una integración de la búsqueda con la búsqueda local, lo que ha dado lugar a algoritmos híbridos .
Los CSP también se estudian en la teoría de la complejidad computacional y la teoría de modelos finitos . Un importante teorema de dicotomía establece que para cada conjunto de relaciones, el conjunto de todos los CSP que pueden representarse utilizando únicamente relaciones elegidas de ese conjunto está en P o NP-completo . Los CSP proporcionan así uno de los subconjuntos más grandes conocidos de NP que evita problemas intermedios de NP , cuya existencia fue demostrada por el teorema de Ladner bajo el supuesto de que P ≠ NP . El teorema de dicotomía de Schaefer maneja el caso en el que todas las relaciones disponibles son operadores booleanos , es decir, para un tamaño de dominio 2. El teorema de dicotomía de Schaefer se generalizó posteriormente a una clase más amplia de relaciones, [15] y por primera vez se conjeturó un teorema de dicotomía completo como el de Feder. –Conjetura de Vardi [16] y finalmente demostrada de forma independiente por Andrei Bulatov [17] y Dmitriy Zhuk. [18]
La mayoría de las clases de CSP que se sabe que son manejables son aquellas en las que el hipergráfico de restricciones tiene un ancho de árbol limitado (y no hay restricciones en el conjunto de relaciones de restricciones), o donde las restricciones tienen forma arbitraria pero existen polimorfismos esencialmente no unarios . aclaración necesaria ] del conjunto de relaciones de restricción.
Cada CSP también puede considerarse como un problema de contención de consultas conjuntivas . [19]
Existe una situación similar entre las clases funcionales FP y #P . Por una generalización del teorema de Ladner , tampoco hay problemas ni en FP ni en #P-completo siempre que FP ≠ #P. Como en el caso de la decisión, un problema en el #CSP se define por un conjunto de relaciones. Cada problema toma una fórmula booleana como entrada y la tarea es calcular el número de asignaciones satisfactorias. Esto se puede generalizar aún más utilizando tamaños de dominio más grandes y asignando un peso a cada asignación satisfactoria y calculando la suma de estos pesos. Se sabe que cualquier problema #CSP ponderado complejo está en FP o #P-hard. [20]
El modelo clásico de problema de satisfacción de restricciones define un modelo de restricciones estáticas e inflexibles. Este modelo rígido es una deficiencia que dificulta representar los problemas fácilmente. [21] Se han propuesto varias modificaciones de la definición básica de CSP para adaptar el modelo a una amplia variedad de problemas.
Los CSP dinámicos [22] ( DCSP ) son útiles cuando la formulación original de un problema se altera de alguna manera, generalmente porque el conjunto de restricciones a considerar evoluciona debido al entorno. [23] Los DCSP se ven como una secuencia de CSP estáticos, cada uno de los cuales es una transformación del anterior en el que se pueden agregar variables y restricciones (restricción) o eliminar (relajación). La información encontrada en las formulaciones iniciales del problema se puede utilizar para perfeccionar las siguientes. El método de resolución se puede clasificar según la forma en que se transfiere la información:
Los CSP clásicos tratan las restricciones como duras, lo que significa que son imperativas (cada solución debe satisfacerlas todas) e inflexibles (en el sentido de que deben satisfacerse completamente o, de lo contrario, serán violadas por completo). Los CSP flexibles relajan esos supuestos, relajando parcialmente las restricciones y permitiendo que la solución no las cumpla todas. Esto es similar a las preferencias en la planificación basada en preferencias . Algunos tipos de CSP flexibles incluyen:
En los DCSP [24] se considera que cada variable de restricción tiene una ubicación geográfica separada. Se imponen fuertes restricciones al intercambio de información entre variables, lo que requiere el uso de algoritmos completamente distribuidos para resolver el problema de satisfacción de restricciones.