Programación de restricciones

La programación con restricciones (CP) ^[1] es un paradigma para resolver problemas combinatorios que se basa en una amplia gama de técnicas de inteligencia artificial , informática e investigación de operaciones . En la programación con restricciones, los usuarios establecen de manera declarativa las restricciones sobre las soluciones factibles para un conjunto de variables de decisión. Las restricciones se diferencian de los primitivos comunes de los lenguajes de programación imperativa en que no especifican un paso o una secuencia de pasos a ejecutar, sino las propiedades de una solución que se debe encontrar. Además de las restricciones, los usuarios también deben especificar un método para resolver estas restricciones. Esto generalmente se basa en métodos estándar como el retroceso cronológico y la propagación de restricciones , pero puede usar código personalizado como una heurística de ramificación específica del problema .

La programación con restricciones tiene su origen en la programación lógica con restricciones y puede expresarse en forma de esta , que incorpora restricciones en un programa lógico . Esta variante de la programación lógica se debe a Jaffar y Lassez ^[2] , quienes ampliaron en 1987 una clase específica de restricciones que se introdujeron en Prolog II . Las primeras implementaciones de la programación lógica con restricciones fueron Prolog III, CLP(R) y CHIP .

En lugar de programación lógica, las restricciones se pueden combinar con programación funcional , reescritura de términos y lenguajes imperativos . Los lenguajes de programación con soporte integrado para restricciones incluyen Oz (programación funcional) y Kaleidoscope (programación imperativa). En su mayoría, las restricciones se implementan en lenguajes imperativos a través de kits de herramientas de resolución de restricciones , que son bibliotecas independientes para un lenguaje imperativo existente.

Programación lógica de restricciones

La programación con restricciones es una incorporación de restricciones en un lenguaje anfitrión. Los primeros lenguajes anfitriones utilizados fueron lenguajes de programación lógica , por lo que el campo se denominó inicialmente programación lógica con restricciones . Los dos paradigmas comparten muchas características importantes, como las variables lógicas y el retroceso . Hoy en día, la mayoría de las implementaciones de Prolog incluyen una o más bibliotecas para la programación lógica con restricciones.

La diferencia entre ambos radica principalmente en sus estilos y enfoques para modelar el mundo. Algunos problemas son más naturales (y, por lo tanto, más simples) de escribir como programas lógicos, mientras que otros son más naturales de escribir como programas de restricciones.

El enfoque de programación de restricciones consiste en buscar un estado del mundo en el que se cumplan al mismo tiempo una gran cantidad de restricciones. Normalmente, un problema se plantea como un estado del mundo que contiene una cantidad de variables desconocidas. El programa de restricciones busca valores para todas las variables.

La programación de restricciones concurrentes temporales (TCC) y la programación de restricciones concurrentes temporales no deterministas (MJV) son variantes de la programación de restricciones que pueden tratar con el tiempo.

Problema de satisfacción de restricciones

Una restricción es una relación entre múltiples variables que limita los valores que estas variables pueden tomar simultáneamente.

Definición : Un problema de satisfacción de restricciones en dominios finitos (o CSP) se define mediante un triplete donde: $({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$

${\mathcal {X}}=\{x_{1},\puntos ,x_{n}\}$ es el conjunto de variables del problema;
${\mathcal {D}}=\{{\mathcal {D}}_{1},\puntos ,{\mathcal {D}}_{n}\}$ es el conjunto de dominios de las variables, es decir, para todo tenemos ; $k\in [1;n]$ $x_{k}\in {\mathcal {D}}_{k}$
${\mathcal {C}}=\{C_{1},\puntos ,C_{m}\}$ es un conjunto de restricciones. Una restricción se define mediante un conjunto de variables y una relación que define el conjunto de valores permitidos simultáneamente para las variables de . $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ ${\mathcal {X}}_{i}=\{x_{i_{1}},\puntos ,x_{i_{k}}\}$ ${\mathcal {R}}_{i}\subseteq {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}$ ${\mathcal {X}}_{i}$

Existen tres categorías de restricciones:

restricciones extensionales: las restricciones se definen enumerando el conjunto de valores que las satisfarían;
restricciones aritméticas: las restricciones se definen mediante una expresión aritmética, es decir, utilizando ; $<,>,\leq ,\geq ,=,\neq ,...$
restricciones lógicas: las restricciones se definen con una semántica explícita, es decir, AllDifferent , AtMost , ...

Definición — Una asignación (o modelo) de un CSP se define por el par donde: ${\mathcal {A}}$ $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}}, {\mathcal {V_{\mathcal {A}}}})$

${\mathcal {X_{\mathcal {A}}}}\subseteq {\mathcal {X}}$ es un subconjunto de variable;
${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ es la tupla de los valores que toman las variables asignadas.

La asignación es la asociación de una variable a un valor de su dominio. Una asignación parcial es cuando se ha asignado un subconjunto de las variables del problema. Una asignación total es cuando se han asignado todas las variables del problema.

Propiedad — Dada una asignación (parcial o total) de un CSP , y una restricción de tal como , la asignación satisface la restricción si y solo si todos los valores de las variables de la restricción pertenecen a . ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ $P$ ${\mathcal {X}}_{i}\subseteq {\mathcal {X_{\mathcal {A}}}}$ ${\mathcal {A}}$ $C_{i}$ ${\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}$ $C_{i}$ ${\mathcal {R}}_{i}$

Definición — Una solución de un CSP es una asignación total que satisface todas las restricciones del problema.

Durante la búsqueda de soluciones de un CSP, un usuario puede desear:

encontrar una solución (que satisfaga todas las restricciones);
encontrar todas las soluciones del problema;
demostrando la insatisfacción del problema.

Problema de optimización de restricciones

Un problema de optimización de restricciones (COP) es un problema de satisfacción de restricciones asociado a una función objetivo.

Una solución óptima para un COP de minimización (maximización) es una solución que minimiza (maximiza) el valor de la función objetivo .

Durante la búsqueda de soluciones de una COP, un usuario puede desear:

encontrar una solución (que satisfaga todas las restricciones);

encontrar la mejor solución con respecto al objetivo;
demostrar la optimalidad de la mejor solución encontrada;
demostrando la insatisfacción del problema.

Modelos de perturbación vs. modelos de refinamiento

Los lenguajes para programación basada en restricciones siguen uno de dos enfoques: ^[3]

Modelo de refinamiento: las variables del problema no tienen asignación inicial y se supone que cada una de ellas puede contener cualquier valor incluido en su rango o dominio. A medida que avanza el cálculo, los valores del dominio de una variable se eliminan si se demuestra que son incompatibles con los valores posibles de otras variables, hasta que se encuentra un único valor para cada variable.
Modelo de perturbación: a las variables del problema se les asigna un único valor inicial. En distintos momentos una o más variables reciben perturbaciones (cambios en su valor anterior) y el sistema propaga el cambio intentando asignar nuevos valores a otras variables que sean consistentes con la perturbación.

La propagación de restricciones en problemas de satisfacción de restricciones es un ejemplo típico de un modelo de refinamiento, y la evaluación de fórmulas en hojas de cálculo es un ejemplo típico de un modelo de perturbación.

El modelo de refinamiento es más general, ya que no restringe las variables a tener un único valor, por lo que puede dar lugar a varias soluciones para el mismo problema. Sin embargo, el modelo de perturbación es más intuitivo para los programadores que utilizan lenguajes orientados a objetos con restricciones imperativas mixtas. ^[4]

Dominios

Las restricciones que se utilizan en la programación con restricciones suelen aplicarse a dominios específicos. Algunos dominios populares para la programación con restricciones son:

Dominios booleanos , donde solo se aplican restricciones de verdadero/falso ( problema SAT )
dominios enteros , dominios racionales
dominios de intervalo , en particular para problemas de programación ^[5]
dominios lineales , donde sólo se describen y analizan funciones lineales (aunque existen enfoques para problemas no lineales )
dominios finitos, donde las restricciones se definen sobre conjuntos finitos
dominios mixtos, que involucran dos o más de los anteriores

Los dominios finitos son uno de los dominios más exitosos de la programación con restricciones. En algunas áreas (como la investigación de operaciones ), la programación con restricciones suele identificarse con la programación con restricciones sobre dominios finitos.

Propagación de restricciones

Las condiciones de consistencia local son propiedades de los problemas de satisfacción de restricciones relacionadas con la consistencia de subconjuntos de variables o restricciones. Se pueden utilizar para reducir el espacio de búsqueda y hacer que el problema sea más fácil de resolver. Se aprovechan varios tipos de condiciones de consistencia local, incluidas la consistencia de nodos , la consistencia de arcos y la consistencia de rutas .

Cada condición de consistencia local puede ser impuesta por una transformación que cambia el problema sin cambiar sus soluciones. Tal transformación se llama propagación de restricciones . ^[6] La propagación de restricciones funciona reduciendo dominios de variables, fortaleciendo restricciones o creando otras nuevas. Esto conduce a una reducción del espacio de búsqueda, haciendo que el problema sea más fácil de resolver por algunos algoritmos. La propagación de restricciones también puede usarse como un verificador de insatisfacción, incompleto en general pero completo en algunos casos particulares.

Resolución de restricciones

Hay tres técnicas algorítmicas principales para resolver problemas de satisfacción de restricciones: búsqueda hacia atrás, búsqueda local y programación dinámica. ^[1]

Búsqueda de retroceso

La búsqueda con retroceso es un algoritmo general para encontrar todas (o algunas) soluciones a algunos problemas computacionales , en particular problemas de satisfacción de restricciones , que construye candidatos de manera incremental para las soluciones y abandona un candidato ("retrocede") tan pronto como determina que el candidato no puede completarse hasta una solución válida.

Búsqueda local

La búsqueda local es un método incompleto para encontrar una solución a un problema . Se basa en mejorar iterativamente una asignación de las variables hasta que se satisfacen todas las restricciones. En particular, los algoritmos de búsqueda local suelen modificar el valor de una variable en una asignación en cada paso. La nueva asignación es cercana a la anterior en el espacio de asignación, de ahí el nombre de búsqueda local .

Programación dinámica

La programación dinámica es tanto un método de optimización matemática como un método de programación informática. Se refiere a simplificar un problema complicado dividiéndolo en subproblemas más simples de manera recursiva . Si bien algunos problemas de decisión no se pueden descomponer de esta manera, las decisiones que abarcan varios puntos en el tiempo a menudo se descomponen de manera recursiva. Del mismo modo, en informática, si un problema se puede resolver de manera óptima dividiéndolo en subproblemas y luego encontrando recursivamente las soluciones óptimas para los subproblemas, entonces se dice que tiene una subestructura óptima .

Ejemplo

La sintaxis para expresar restricciones sobre dominios finitos depende del lenguaje anfitrión. El siguiente es un programa Prolog que resuelve el clásico rompecabezas alfabético SEND+MORE=MONEY en la programación lógica de restricciones:

% Este código funciona tanto en YAP como en SWI-Prolog utilizando la biblioteca de resolución de restricciones CLPFD proporcionada por el entorno. Es posible que se requieran modificaciones menores para que funcione en otros entornos Prolog o utilizando otros solucionadores de restricciones. :-  use_module ( library ( clpfd )). sendmore ( Dígitos )  :-  Dígitos  =  [ S , E , N , D , M , O , R , Y ],  % Crear variables  Dígitos  ins  0..9 ,  % Asociar dominios a las variables  S  #\=  0 ,  % Restricción: S debe ser diferente de 0  M  #\=  0 ,  all_different ( Dígitos ),  % todos los elementos deben tomar valores diferentes  1000 * S  +  100 * E  +  10 * N  +  D  % Otras restricciones  +  1000 * M  +  100 * O  +  10 * R  +  E  #=  10000 * M  +  1000 * O  +  100 * N  +  10 * E  +  Y ,  etiqueta ( Dígitos ).  % Iniciar la búsqueda

El intérprete crea una variable para cada letra del rompecabezas. El operador insse utiliza para especificar los dominios de estas variables, de modo que ocupen el conjunto de valores {0,1,2,3, ..., 9}. Las restricciones S#\=0y M#\=0significan que estas dos variables no pueden tomar el valor cero. Cuando el intérprete evalúa estas restricciones, reduce los dominios de estas dos variables eliminando el valor 0 de ellas. Luego, all_different(Digits)se considera la restricción; no reduce ningún dominio, por lo que simplemente se almacena. La última restricción especifica que los dígitos asignados a las letras deben ser tales que "ENVIAR+MÁS=DINERO" se cumpla cuando cada letra se reemplaza por su dígito correspondiente. A partir de esta restricción, el solucionador infiere que M=1. Se activan todas las restricciones almacenadas que involucran a la variable M: en este caso, la propagación de la restricción en la all_differentrestricción elimina el valor 1 del dominio de todas las variables restantes. La propagación de restricciones puede resolver el problema reduciendo todos los dominios a un único valor, puede demostrar que el problema no tiene solución reduciendo un dominio al conjunto vacío, pero también puede terminar sin demostrar la satisfacibilidad o insatisfacibilidad. Los literales de etiqueta se utilizan para realizar la búsqueda de una solución.

Véase también

Referencias

^ ab Rossi, Francesca ; Beek, Peter van; Walsh, Toby (18 de agosto de 2006). Manual de programación con restricciones. Elsevier. ISBN 9780080463803.
^ Jaffar, Joxan y JL. Lassez. "Programación lógica de restricciones". Actas del 14.º Simposio ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación . ACM, 1987.
^ Mayoh, Brian; Tyugu, Enn; Penjam, Jaan (1993). Programación con restricciones. Springer Science+Business Media . p. 76. ISBN 9783642859830.
^ Lopez, G., Freeman-Benson, B., y Borning, A. (1994, enero). Kaleidoscope: A limitations empire programming language (Caleidoscopio: un lenguaje de programación imperativo con restricciones). En Constraint Programming (págs. 313-329). Springer Berlin Heidelberg.
^ Baptiste, Philippe; Pape, Claude Le; Nuijten, Wim (6 de diciembre de 2012). Programación basada en restricciones: aplicación de la programación basada en restricciones a problemas de programación. Springer Science & Business Media. ISBN 978-1-4615-1479-4.
^ Bessiere, Christian (2006), "Propagación de restricciones", Manual de programación con restricciones , Fundamentos de la inteligencia artificial, vol. 2, Elsevier, págs. 29-83, CiteSeerX 10.1.1.398.4070 , doi :10.1016/s1574-6526(06)80007-6, ISBN 9780444527264

Enlaces externos

Wikimedia Commons tiene medios relacionados con Programación con restricciones .

Asociación para la Programación de Restricciones
Serie de conferencias CP
Guía para la programación con restricciones
El sistema de programación Mozart en archive.today (archivado el 5 de diciembre de 2012), un software libre basado en Oz ( estilo X11 )
Centro de cálculo de restricciones de Cork en archive.today (archivado el 7 de enero de 2013)