Programación de restricciones

Paradigma de programación en el que las relaciones entre variables se establecen en forma de restricciones.

La programación de 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 de restricciones, los usuarios establecen de forma declarativa las restricciones de las soluciones factibles para un conjunto de variables de decisión. Las restricciones se diferencian de las primitivas comunes de los lenguajes de programación imperativos en que no especifican un paso o secuencia de pasos a ejecutar, sino más bien 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 resolverlas. Por lo general, esto 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 de restricciones tiene su raíz y puede expresarse en la forma de programación lógica de restricciones , que incorpora restricciones en un programa lógico . Esta variante de 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 programación lógica de 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 mediante kits de herramientas de resolución de restricciones , que son bibliotecas separadas para un lenguaje imperativo existente.

Programación lógica de restricciones

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

La diferencia entre los dos está en gran medida 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 satisfagan un gran número de restricciones al mismo tiempo. Un problema generalmente se plantea como un estado del mundo que contiene una serie de variables desconocidas. El programa de restricciones busca valores para todas las variables.

La programación de restricciones temporales concurrentes (TCC) y la programación de restricciones temporales concurrentes (MJV) son variantes de la programación de restricciones que pueden lidiar 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: ${\displaystyle ({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}$

• ${\displaystyle {\mathcal {X}}=\{x_{1},\dots ,x_{n}\}}$es el conjunto de variables del problema;
• ${\displaystyle {\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}}$es el conjunto de dominios de las variables, es decir, para todas tenemos ; ${\displaystyle k\in [1;n]}$ ${\displaystyle x_{k}\in {\mathcal {D}}_{k}}$
• ${\displaystyle {\mathcal {C}}=\{C_{1},\dots ,C_{m}\}}$es un conjunto de restricciones. Una restricción está definida por un conjunto de variables y una relación que define el conjunto de valores permitidos simultáneamente para las variables de . ${\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}$ ${\displaystyle {\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}}$ ${\displaystyle {\mathcal {R}}_{i}\subseteq {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}}$ ${\displaystyle {\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, usando ; ${\displaystyle <,>,\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 la pareja donde: ${\displaystyle {\mathcal {A}}}$ ${\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}$ ${\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})}$

• ${\displaystyle {\mathcal {X_{\mathcal {A}}}}\subseteq {\mathcal {X}}}$es un subconjunto de variable;
• ${\displaystyle {\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 como , la asignación satisface la restricción si y solo si todos los valores de las variables de la restricción pertenecen a . ${\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})}$ ${\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}$ ${\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}$ ${\displaystyle P}$ ${\displaystyle {\mathcal {X}}_{i}\subseteq {\mathcal {X_{\mathcal {A}}}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle C_{i}}$ ${\displaystyle {\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}}$ ${\displaystyle C_{i}}$ ${\displaystyle {\mathcal {R}}_{i}}$

Definición  :  una solución de un CSP es una tarea 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 (satisfaciendo todas las restricciones);
• encontrar todas las soluciones al problema;
• demostrando la insatisfacibilidad 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 un COP, un usuario puede desear:

• encontrar una solución (satisfaciendo todas las restricciones);

• encontrar la mejor solución con respecto al objetivo;
• demostrar la optimidad de la mejor solución encontrada;
• demostrando la insatisfacibilidad del problema.

Modelos de perturbación versus refinamiento

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

• Modelo de refinamiento: las variables del problema inicialmente no están asignadas y se supone que cada variable puede contener cualquier valor incluido en su rango o dominio. A medida que avanza el cálculo, los valores en el dominio de una variable se eliminan si se demuestra que son incompatibles con los posibles valores de otras variables, hasta que se encuentra un valor único para cada variable.
• Modelo de perturbación: a las variables del problema se les asigna un único valor inicial. En diferentes momentos una o más variables reciben perturbaciones (cambios en su valor anterior), y el sistema propaga el cambio tratando de 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 modelo de refinamiento, y las hojas de cálculo son un ejemplo típico de modelo de perturbación.

El modelo de refinamiento es más general, ya que no restringe las variables a tener un solo valor, puede conducir a varias soluciones al 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 utilizadas en la programación de restricciones suelen afectar a algunos dominios específicos. Algunos dominios populares para la programación de 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 solo 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 de restricciones. En algunas áreas (como la investigación de operaciones ), la programación de restricciones a menudo se identifica con la programación de restricciones en dominios finitos.

Propagación de restricciones

Las condiciones de consistencia local son propiedades de los problemas de satisfacción de restricciones relacionados con la consistencia de subconjuntos de variables o restricciones. Se pueden utilizar para reducir el espacio de búsqueda y facilitar la resolución del problema. Se aprovechan varios tipos de condiciones de coherencia local, incluida la coherencia de nodos , la coherencia de arco y la coherencia de ruta .

Cada condición de consistencia local puede imponerse mediante una transformación que cambie el problema sin cambiar sus soluciones. Esta 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, lo que hace que el problema sea más fácil de resolver mediante algunos algoritmos. La propagación de restricciones también se puede utilizar como un verificador de insatisfacibilidad, incompleta en general pero completa en algunos casos particulares.

resolución de restricciones

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

Búsqueda de retroceso

La búsqueda de 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 incrementalmente candidatos para las soluciones y abandona a un candidato ("retrocede") tan pronto como determina que el candidato no puede. posiblemente completarse hasta llegar a una solución válida.

Busqueda 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 variables hasta que se cumplan 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 está cerca de 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 pueden descomponerse de esta manera, las decisiones que abarcan varios momentos en el tiempo a menudo se descomponen de forma 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 a los subproblemas, entonces se dice que tiene una subestructura óptima .

Ejemplo

La sintaxis para expresar restricciones sobre dominios finitos depende del idioma anfitrión. El siguiente es un programa Prolog que resuelve el clásico rompecabezas alfamético ENVIAR+MÁS=DINERO en 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 funcionar en otros entornos de Prolog o utilizar otros solucionadores de restricciones. :-  use_module ( biblioteca ( clpfd )). sendmore ( Dígitos )  : -  Dígitos  =  [ S , E , N , D , M , O , R , Y ],  % Crear variables  Dígitos  ins  0..9 ,  % Asociar dominios a variables  S  #\=  0 ,  % Restricción: S debe ser diferente de 0  M  #\=  0 ,  todo_diferente ( 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 abarquen el conjunto de valores {0,1,2,3, ..., 9}. Las restricciones S#\=0y M#\=0significa 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 quitándoles el valor 0. 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 mantenga cuando cada letra se reemplaza por su dígito correspondiente. A partir de esta restricción, el solucionador infiere que M=1. Se despiertan todas las restricciones almacenadas que involucran la variable M: ​​en este caso, la propagación de 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 solo valor, puede demostrar que el problema no tiene solución reduciendo un dominio al conjunto vacío, pero también puede terminar sin demostrar satisfacibilidad o insatisfacibilidad. Los literales de etiqueta se utilizan para realizar la búsqueda de una solución.

Ver también

• Optimización combinatoria
• Programación lógica de restricciones
• Programación lógica de restricciones concurrentes
• Optimización matemática
• Algoritmos heurísticos
• Problema de programación de enfermeras
• restricción regular
• Problema del torneo itinerante

Referencias

1. Rossi, Francesca ; Beek, Peter van; Walsh, Toby (18 de agosto de 2006). Manual de programación de restricciones. Elsevier. ISBN 9780080463803.
2. 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.
3. Mayoh, Brian; Tyugu, Enn; Penjam, Jaan (1993). Programación de restricciones. Springer Ciencia + Medios comerciales . pag. 76.ISBN​ 9783642859830.
4. López, G., Freeman-Benson, B. y Borning, A. (1994, enero). Caleidoscopio: un lenguaje de programación imperativo con restricciones. En Programación de restricciones (págs. 313-329). Springer Berlín Heidelberg.
5. Bautista, Felipe; Pape, Claude Le; Nuijten, Wim (6 de diciembre de 2012). Programación basada en restricciones: aplicación de programación con restricciones a problemas de programación. Medios de ciencia y negocios de Springer. ISBN 978-1-4615-1479-4.
6. Bessiere, Christian (2006), "Propagación de restricciones", Manual de programación de 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

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