Problema de satisfacción de restricciones

Los problemas de satisfacción de restricciones ( CSP ) son problemas matemáticos definidos 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 operativa , 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 alta complejidad , lo que requiere 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 de satisfacibilidad booleana (SAT), la satisfacibilidad módulo teorías (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 del problema de satisfacción de restricciones.

Algunos ejemplos de problemas que pueden modelarse como un problema de satisfacción de restricciones son:

Inferencia de tipo ^{[ 3 ]}^{[ 4 ]}
Rompecabezas de las ocho reinas
Problema de coloración de mapas
Problema de corte máximo ^{[ 5 ]}
Sudoku , crucigramas , futoshiki , kakuro (sumas cruzadas), Numbrix / Hidato , Zebra Puzzle y muchos otros rompecabezas de lógica .

Estos suelen ir acompañados de tutoriales de solucionadores CP , ASP, Boolean SAT y SMT. En general, los problemas de restricciones pueden ser mucho más difíciles y es posible que no se puedan expresar en algunos de estos sistemas más simples. Ejemplos de la vida real incluyen la planificación automatizada , ^{[ 6 ]}^{[ 7 ]} la desambiguación léxica , ^{[ 8 ]}^{[ 9 ]} la musicología , ^{[ 10 ]} la configuración de productos ^{[ 11 ]} y la asignación de recursos . ^{[ 12 ]}

La existencia de una solución a un problema de satisfacción de restricciones (CSP) puede considerarse un problema de decisión . Esta decisión se puede tomar encontrando una solución o no encontrándola tras una búsqueda exhaustiva ( los algoritmos estocásticos normalmente no llegan a una conclusión exhaustiva, mientras que las búsquedas dirigidas sí suelen hacerlo 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.

Definición formal

Formalmente, un problema de satisfacción de restricciones se define como una tripleta $\langle X,D,C\rangle$ , donde ^{[ 13 ]}

$X=\{X_{1},\ldots ,X_{n}\}$ es un conjunto de variables,
$D=\{D_{1},\ldots ,D_{n}\}$ es un conjunto de sus respectivos dominios de valores, y
$C=\{C_{1},\ldots ,C_{m}\}$ es un conjunto de restricciones.

Cada variable $X_{i}$ puede tomar los valores en el dominio no vacío $D_{i}$ Cada restricción $C_{j}\in C$ es a su vez un par $\langle t_{j},R_{j}\rangle$ , dónde $t_{j}\subseteq \{1,2,\ldots ,n\}$ es un conjunto de $k$ índices y $R_{j}$ es un $k$ Relación -aria en el producto correspondiente de dominios $\times _{i\in t_{j}}D_{i}$ donde el producto se toma con índices en orden ascendente. 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 $v$ satisface una restricción $\langle t_{j},R_{j}\rangle$ si los valores asignados a las variables $t_{j}$ satisfacer la relación $R_{j}$ .

Una evaluación es consistente si no viola ninguna de las restricciones. Una evaluación es completa si incluye todas las variables. Una evaluación es una solución si es consistente y completa; se dice que dicha evaluación resuelve el problema de satisfacción de restricciones.

Solución

Los problemas de satisfacción de restricciones en dominios finitos se resuelven típicamente mediante algún tipo 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 se combinan con frecuencia, como en el método VLNS , y la investigación actual incluye 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 sin asignar. En cada paso, se elige una variable y se le asignan todos los valores posibles. Para cada valor, se comprueba la consistencia de la asignación parcial con las restricciones; en caso de consistencia, se realiza una llamada recursiva . Cuando se han probado todos los valores, el algoritmo retrocede. En este algoritmo básico de retroceso, la consistencia se define como la satisfacción de todas las restricciones cuyas variables están todas asignadas. Existen varias variantes de retroceso. El marcado de retroceso mejora la eficiencia de la comprobación de consistencia. El salto hacia atrás permite ahorrar 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 usa a menudo en el retroceso para intentar prever los efectos de elegir una variable o un valor, determinando así a veces de antemano si un subproblema es satisfacible o insatisfacible.

Las técnicas de propagación de restricciones son métodos que se utilizan 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 diversas aplicaciones. En primer lugar, transforma un problema en uno equivalente, pero generalmente más sencillo de resolver. En segundo lugar, puede demostrar la satisfacibilidad o insatisfacibilidad de los problemas. Esto no está garantizado en general; sin embargo, siempre ocurre para algunas formas de propagación de restricciones y/o para ciertos tipos de problemas. Las formas más conocidas y utilizadas de consistencia local son la consistencia de arco , la consistencia de hiperarco y la consistencia de camino . El método de propagación de restricciones más popular es el algoritmo AC-3 , que impone la consistencia de arco.

Los métodos de búsqueda local son algoritmos de satisfacibilidad incompleta. Pueden encontrar una solución a un problema, pero pueden fallar incluso si el problema es satisfacible. Funcionan mejorando iterativamente una asignación completa sobre las variables. En cada paso, se modifica el valor de un pequeño número de variables, con el objetivo general de aumentar el número 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, dando lugar a algoritmos híbridos .

Aspectos teóricos

Complejidad computacional

Los problemas de satisfacción de restricciones (CSP) también se estudian en la teoría de la complejidad computacional , la teoría de modelos finitos y el álgebra universal . Se ha demostrado que las preguntas sobre la complejidad de los CSP se traducen en importantes cuestiones de álgebra universal sobre las álgebras subyacentes. Este enfoque se conoce como el enfoque algebraico de los CSP. ^{[ 15 ]}

Dado que todo problema de decisión computacional es equivalente en tiempo polinomial a un CSP con una plantilla infinita, ^{[ 16 ]} los CSP generales pueden tener complejidad arbitraria. En particular, también hay CSP dentro de la clase de problemas NP-intermedios , cuya existencia fue demostrada por Ladner , bajo el supuesto de que P ≠ NP .

Sin embargo, una gran clase de CSP que surgen de aplicaciones naturales satisfacen una dicotomía de complejidad, lo que significa que cada CSP dentro de esa clase está en P o es NP-completo . Estos CSP proporcionan así uno de los subconjuntos más grandes conocidos de NP que evita problemas NP-intermedios . Schaefer demostró por primera vez una dicotomía de complejidad para CSP booleanos, es decir, CSP sobre un dominio de 2 elementos y donde todas las relaciones disponibles son operadores booleanos . Este resultado se ha generalizado para varias clases de CSP, sobre todo para todos los CSP sobre dominios finitos. Esta conjetura de dicotomía de dominio finito fue formulada por primera vez por Tomás Feder y Moshe Vardi, ^{[ 17 ]} y finalmente demostrada independientemente por Andrei Bulatov ^{[ 18 ]} y Dmitriy Zhuk en 2017. ^{[ 19 ]}

Otras clases para las que se ha confirmado una dicotomía de complejidad son:

todos los reductos de primer orden de $(\mathbb {Q} ,<)$ , ^{[ 20 ]}
todos los reductos de primer orden del grafo aleatorio contable , ^{[ 21 ]}
todos los reductos de primer orden del compañero modelo de la clase de todas las relaciones C, ^{[ 22 ]}
todos los reductos de primer orden del poset homogéneo universal , ^{[ 23 ]}
todos los reductos de primer orden de grafos homogéneos no dirigidos, ^{[ 24 ]}
todos los reductos de primer orden de todas las estructuras unarias, ^{[ 25 ]}
todos los CSP en la clase de complejidad MMSNP. ^{[ 26 ]}

La mayoría de las clases de CSP que se sabe que son tratables son aquellas en las que el hipergrafo de restricciones tiene un ancho de árbol acotado , ^{[ 27 ]} o en las que las restricciones tienen una forma arbitraria pero existen polimorfismos no triviales desde el punto de vista de la ecuación del conjunto de relaciones de restricción. ^{[ 28 ]}

Se ha formulado una conjetura de dicotomía de dominio infinito ^{[ 29 ]} para todos los CSP de reductos de estructuras homogéneas finitamente acotadas, que establece que el CSP de tal estructura está en P si y solo si su clon polimórfico no es trivial desde el punto de vista de la ecuación, y NP-difícil en caso contrario.

La complejidad de tales CSP de dominio infinito, así como de otras generalizaciones (CSP valorados, CSP cuantificados, CSP de promesas), sigue siendo un área de investigación activa. ^{[ 30 ]}

Cada CSP también puede considerarse como un problema de contención de consultas conjuntivas . ^{[ 31 ]}

Problemas de funcionamiento

Existe una situación similar entre las clases funcionales FP y #P . Por una generalización del teorema de Ladner , también hay problemas que no son ni FP ni #P-completos siempre que FP ≠ #P. Al igual que en el caso de decisión, un problema en el #CSP se define mediante un conjunto de relaciones. Cada problema toma como entrada una fórmula booleana y la tarea consiste en calcular el número de asignaciones que la satisfacen. Esto se puede generalizar aún más utilizando dominios de mayor tamaño y asignando un peso a cada asignación que la satisface, calculando la suma de estos pesos. Se sabe que cualquier problema #CSP complejo ponderado es FP o #P-difícil. ^{[ 32 ]}

Variantes

El modelo clásico del Problema de Satisfacción de Restricciones define un modelo de restricciones estáticas e inflexibles. Este modelo rígido es una limitación que dificulta la representación sencilla de los problemas. ^{[ 33 ]} Se han propuesto varias modificaciones de la definición básica del CSP para adaptar el modelo a una amplia variedad de problemas.

Proveedores de servicios de comunicación dinámicos

Los CSP dinámicos ^{[ 34 ]} ( DCSP ) son útiles cuando la formulación original de un problema se modifica de alguna manera, generalmente porque el conjunto de restricciones a considerar evoluciona debido al entorno. ^{[ 35 ]} Los DCSP se conciben como una secuencia de CSP estáticos, cada uno una transformación del anterior en la que se pueden agregar (restricción) o eliminar (relajación) variables y restricciones. La información encontrada en las formulaciones iniciales del problema se puede utilizar para refinar las siguientes. El método de resolución se puede clasificar según la forma en que se transfiere la información:

Oráculos : las soluciones encontradas para los CSP anteriores en la secuencia se utilizan como heurísticas para guiar la resolución del CSP actual desde cero.
Reparación local: cada CSP se calcula a partir de la solución parcial del anterior y se reparan las restricciones inconsistentes con búsqueda local .
Registro de restricciones: en cada etapa de la búsqueda se definen nuevas restricciones para representar el aprendizaje a partir de grupos de decisiones inconsistentes. Estas restricciones se transfieren a los nuevos problemas CSP.

Proveedores de servicios de comunicación flexibles

Los problemas de satisfacción de la condición ( CSP) clásicos tratan las restricciones como rígidas, es decir, imperativas (cada solución debe satisfacerlas todas) e inflexibles (en el sentido de que deben cumplirse por completo o, de lo contrario, se incumplen por completo). Los CSP flexibles relajan estas suposiciones, flexibilizando 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:

MAX-CSP, donde se permite que se infrinjan varias restricciones, y la calidad de una solución se mide por la cantidad de restricciones satisfechas.
CSP ponderado , un MAX-CSP en el que cada violación de una restricción se pondera según una preferencia predefinida. Por lo tanto, se prefiere satisfacer la restricción con mayor peso.
Las restricciones del modelo CSP difuso se definen como relaciones difusas en las que la satisfacción de una restricción es una función continua de los valores de sus variables, que va desde la satisfacción total hasta la violación total.

Proveedores de servicios de comunicación descentralizados

En los DCSP ^{[ 36 ]} , 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 totalmente distribuidos para resolver el problema de satisfacción de restricciones.

Véase también

Referencias

↑ Lecoutre, Christophe (2013). Redes de restricciones: técnicas y algoritmos . Wiley. pág. 26. ISBN 978-1-118-61791-5.
↑ "Restricciones – incl. opción de publicación en acceso abierto" . springer.com . Consultado el 3 de octubre de 2019 .
↑ Chandra, Satish; Gordon, Colin S.; Jeannin, Jean-Baptiste; Schlesinger, Cole; Sridharan, Manu; Tip, Frank; Choi, Youngil (2016). "Inferencia de tipos para la compilación estática de JavaScript" (PDF) . Actas de la Conferencia Internacional ACM SIGPLAN 2016 sobre Programación Orientada a Objetos, Sistemas, Lenguajes y Aplicaciones . págs. 410–429 . doi : 10.1145/2983990.2984017 . ISBN 978-1-4503-4444-9.
↑ Jim, Trevor y Jens Palsberg. " Inferencia de tipos en sistemas de tipos recursivos con subtipado ". Disponible en la página web de los autores (1999).
↑ Farhi, Edward; Aram W Harrow (2016). "Supremacía cuántica a través del algoritmo de optimización aproximada cuántica". arXiv : 1602.07674 [ quant-ph ].
↑ Malik Ghallab; Dana Nau; Paolo Traverso (21 de mayo de 2004). Planificación automatizada: teoría y práctica . Elsevier. págs. 1–. ISBN 978-0-08-049051-9.
↑ Satisfacción de restricciones flexibles dinámicas y su aplicación a la planificación de IA , archivado el 6 de febrero de 2009 en Wayback Machine Ian Miguel – diapositivas.
↑ Demetriou, George C. « Desambiguación léxica mediante el manejo de restricciones en Prolog (CHIP) ». Actas de la sexta conferencia del capítulo europeo de la Asociación de Lingüística Computacional. Asociación de Lingüística Computacional, 1993.
↑ MacDonald, Maryellen C., y Mark S. Seidenberg. « Explicaciones de la comprensión léxica y oracional basadas en la satisfacción de restricciones ». Manual de Psicolingüística (Segunda edición). 2006. 581–611.
↑ Mauricio Toro, Carlos Agon, Camilo Rueda, Gerard Assayag. " GELISP: UN MARCO PARA REPRESENTAR PROBLEMAS DE SATISFACCIÓN DE RESTRICCIONES MUSICALES Y ESTRATEGIAS DE BÚSQUEDA ." Journal of Theoretical and Applied Information Technology 86 (2). 2016. 327–331.
↑ Aplicación del enfoque de satisfacción de restricciones para resolver problemas de configuración de productos con reglas de configuración basadas en cardinalidad , Dong Yang y Ming Dong, Journal of Intelligent Manufacturing volumen 24, páginas 99–111 (2013)
↑ Modi, Pragnesh Jay, et al. " Un enfoque dinámico de satisfacción de restricciones distribuidas para la asignación de recursos ". Conferencia Internacional sobre Principios y Práctica de la Programación con Restricciones. Springer, Berlín, Heidelberg, 2001.
↑ Stuart Jonathan Russell; Peter Norvig (2010). Inteligencia artificial: un enfoque moderno . Prentice Hall. pág. Capítulo 6. ISBN 9780136042594.
↑ Milano, Michela ; Van Hentenryck, Pascal, eds. (2011). Optimización híbrida : los diez años de CPAIOR . Conferencia Internacional sobre la Integración de Técnicas de IA e Investigación Operativa en Programación con Restricciones para Problemas de Optimización Combinatoria. Nueva York: Springer. ISBN 9781441916440OCLC 695387020
↑ Barto, Libor; Brady, Zarathustra; Bulatov, Andrei; Kozik, Marcin; Zhuk, Dmitriy (15 de mayo de 2024). "Unificación de los tres enfoques algebraicos del CSP mediante álgebras de Taylor mínimas". Theoretics . 3 11361. arXiv : 2104.11808 . doi : 10.46298/theoretics.24.14 . ISSN 2751-4838 .
↑ Bodirsky, Manuel; Grohe, Martin (2008). "No dicotomías en la complejidad de la satisfacción de restricciones" . En Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor (eds.). Autómatas, lenguajes y programación . Lecture Notes in Computer Science. Vol. 5126. Berlín, Heidelberg: Springer. pp. 184–196 . doi : 10.1007/978-3-540-70583-3_16 . ISBN 978-3-540-70583-3.
↑ Feder, Tomás; Vardi, Moshe Y. (1998). "La estructura computacional de SNP monádico monótono y la satisfacción de restricciones: un estudio a través de Datalog y teoría de grupos" . SIAM Journal on Computing . 28 (1): 57–104 . doi : 10.1137/S0097539794266766 . ISSN 0097-5397 .
↑ Bulatov, Andrei (2017). "Un teorema de dicotomía para CSP no uniformes". Actas del 58.º Simposio Anual de la IEEE sobre Fundamentos de la Informática, FOCS 2017. IEEE Computer Society. págs. 319–330 . arXiv : 1703.03021 . doi : 10.1109/FOCS.2017.37 . ISBN 978-1-5386-3464-6.
↑ Zhuk, Dmitriy (2020). "Una prueba de la conjetura de la dicotomía CSP". Journal of the ACM . 67 (5): 1– 78. arXiv : 1704.01914 . doi : 10.1145/3402029 .
↑ Bodirsky, Manuel; Kára, Jan (2010-02-08). "La complejidad de los problemas de satisfacción de restricciones temporales" . J. ACM . 57 (2): 9:1–9:41. doi : 10.1145/1667053.1667058 . ISSN 0004-5411 .
↑ Bodirsky, Manuel; Pinsker, Michael (2011). «Teorema de Schaefer para grafos». Actas del 43.º Simposio Anual sobre Teoría de la Computación (STOC '11) . Association for Computing Machinery . págs. 655–664 . arXiv : 1011.2894 . doi : 10.1145/1993636.1993724 . ISBN 978-1-4503-0691-1. S2CID 47097319 .
↑ Bodirsky, Manuel; Jonsson, Peter; Pham, Trung Van (2017-08-02). "La complejidad de los problemas de satisfacción de restricciones filogenéticas" . ACM Trans. Comput. Logic . 18 (3): 23:1–23:42. arXiv : 1503.07310 . doi : 10.1145/3105907 . ISSN 1529-3785 .
↑ Kompatscher, Michael; Pham, Trung Van (2017). "Una dicotomía de complejidad para la satisfacción de la restricción Poset". 34º Simposio sobre Aspectos Teóricos de la Informática (STACS 2017) . Actas internacionales de Leibniz en informática. vol. 66. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. págs. 47:1–47:12. doi : 10.4230/LIPIcs.STACS.2017.47 . ISBN 978-3-95977-028-6.
↑ Bodirsky, Manuel; Martin, Barnaby; Pinsker, Michael; Pongrácz, András (enero de 2019). "Problemas de satisfacción de restricciones para reductos de grafos homogéneos" . SIAM Journal on Computing . 48 (4): 1224– 1264. arXiv : 1602.05819 . doi : 10.1137/16M1082974 . ISSN 0097-5397 .
↑ Bodirsky, Manuel; Mottet, Antoine (2018-05-20), "Una dicotomía para reductos de primer orden de estructuras unarias", Métodos lógicos en informática , 14 (2) 3264, arXiv : 1601.04520 , doi : 10.23638/LMCS-14(2:13)2018
↑ Bodirsky, Manuel; Madelaine, Florent; Mottet, Antoine (09-07-2018). "Una prueba algebraica universal de la dicotomía de complejidad para SNP monádico monótono" . Actas del 33.er Simposio Anual ACM/IEEE sobre Lógica en Ciencias de la Computación . LICS '18. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 105–114 . arXiv : 1802.03255 . doi : 10.1145/3209108.3209156 . ISBN 978-1-4503-5583-4.
↑ Barto, Libor; Kozik, Marcin (2014-01-01). "Problemas de satisfacción de restricciones resolubles mediante métodos de consistencia local" . J. ACM . 61 (1): 3:1–3:19. doi : 10.1145/2556646 . ISSN 0004-5411 .
↑ Bodirsky, Manuel (2021). Complejidad de la satisfacción de restricciones en dominios infinitos . Lecture Notes in Logic. Cambridge: Cambridge University Press. ISBN 978-1-107-04284-1.
^ Bodirsky, Manuel; Pinsker, Michael; Pongrácz, András (marzo de 2021). "Homomorfismos de clones proyectivos" . La revista de lógica simbólica . 86 (1): 148–161 . arXiv : 1409.4601 . doi : 10.1017/jsl.2019.23 . hdl : 2437/268560 . ISSN 0022-4812 .
↑ Pinsker, Michael (2022-03-31). "Desafíos actuales en la satisfacción de restricciones de dominio infinito: dilemas de la oveja infinita". arXiv : 2203.17182 [ cs.LO ].
↑ Kolaitis, Phokion G.; Vardi, Moshe Y. (2000). "Contención de consultas conjuntivas y satisfacción de restricciones" . Journal of Computer and System Sciences . 61 (2): 302– 332. doi : 10.1006/jcss.2000.1713 .
↑ Cai, Jin-Yi; Chen, Xi (2012). "Complejidad del conteo de CSP con pesos complejos". Actas del Cuadragésimo Cuarto Simposio Anual de la ACM sobre Teoría de la Computación (STOC '12) . págs. 909–920 . arXiv : 1111.2384 . doi : 10.1145/2213977.2214059 . ISBN 978-1-4503-1245-5. S2CID 53245129 .
↑Miguel, Ian (July 2001). Dynamic Flexible Constraint Satisfaction and its Application to AI Planning (Ph.D. thesis). University of Edinburgh School of Informatics. CiteSeerX 10.1.1.9.6733. hdl:1842/326.
↑Dechter, R. and Dechter, A., Belief Maintenance in Dynamic Constraint NetworksArchived 2012-11-17 at the Wayback Machine In Proc. of AAAI-88, 37–42.
↑Solution reuse in dynamic constraint satisfaction problems, Thomas Schiex
↑Duffy, K.R.; Leith, D.J. (August 2013), "Decentralized Constraint Satisfaction", IEEE/ACM Transactions on Networking, 21(4), vol. 21, pp. 1298–1308, arXiv:1103.3240, doi:10.1109/TNET.2012.2222923, S2CID 11504393