Programación de restricciones - Constraint programming

La programación de restricciones (CP) 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 manera declarativa las restricciones sobre las soluciones factibles para un conjunto de variables de decisión. Las restricciones difieren 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 a 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 de un problema .

La programación de restricciones tiene su raíz y se puede expresar en forma de programación lógica de restricciones , que incorpora restricciones en un programa lógico . Esta variante de la programación lógica se debe a Jaffar y Lassez, 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 de restricciones fueron Prolog III , CLP (R) y CHIP .

En lugar de la programación lógica, las restricciones se pueden combinar con la programación funcional , la reescritura de términos y los lenguajes imperativos . Los lenguajes de programación con soporte incorporado 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 separadas para un lenguaje imperativo existente.

Programación lógica de restricciones

La programación de restricciones es una incrustación de restricciones en un lenguaje anfitrión. Los primeros lenguajes de host utilizados fueron los lenguajes de programación lógica , por lo que el campo se llamó inicialmente programación lógica de 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 de restricciones.

La diferencia entre los dos 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 restricción.

El enfoque de programación de restricciones consiste en buscar un estado del mundo en el que se satisfagan una gran cantidad de restricciones al mismo tiempo. Un problema se expresa típicamente como un estado del mundo que contiene una serie de variables desconocidas. El programa de restricción busca valores para todas las variables.

La programación de restricciones temporales concurrentes (TCC) y la programación de restricciones temporales concurrentes no deterministas (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 todo lo que tenemos ; ${\ Displaystyle k \ en [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 se define 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} \ subconjunto {\ 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 es definida 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}}}} \ subconjunto {\ 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 tomados por 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 pertenecen todos los valores de las variables de la restricción . ${\ 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} \ subconjunto {\ 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 asignación total que satisface todas las limitaciones del problema.

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

encontrar una solución (satisfacer 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 las soluciones de un CSP, un usuario puede desear:

encontrar una solución (satisfacer todas las restricciones);

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

Modelos de perturbación vs refinamiento

Los lenguajes para la programación basada en restricciones siguen uno de dos enfoques:

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 podan si se demuestra que son incompatibles con los posibles valores de otras variables, hasta que se encuentra un solo valor 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 a su antiguo valor) 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 los problemas de satisfacción de restricciones es un ejemplo típico de un modelo de refinamiento, y las hojas de cálculo son un ejemplo típico de un modelo de perturbación.

El modelo de refinamiento es más general, ya que no restringe las variables para que tengan un solo valor, puede llevar 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 de restricción imperativa mixta.

Dominios

Las restricciones que se utilizan en la programación de restricciones se encuentran típicamente en 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
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 del nodo , la coherencia del arco y la coherencia de la ruta .

Cada condición de coherencia local se puede imponer mediante una transformación que cambie el problema sin cambiar sus soluciones. Esta transformación se denomina propagación de restricciones . La propagación de restricciones funciona reduciendo dominios de variables, fortaleciendo restricciones o creando nuevas. Esto conduce a una reducción del espacio de búsqueda, lo que facilita la resolución del problema mediante algunos algoritmos. La propagación de restricciones también se puede utilizar como un verificador de insatisfacción, incompleta en general pero completa 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 de retroceso, búsqueda local y programación dinámica.

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 gradualmente candidatos a las soluciones y abandona a un candidato ("retrocesos") tan pronto como determina que el candidato no puede posiblemente se complete con 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 las variables hasta que se satisfagan todas las restricciones. En particular, los algoritmos de búsqueda local normalmente modifican el valor de una variable en una asignación en cada paso. La nueva asignación se acerca 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 de computadoras. 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 desarmar de esta manera, las decisiones que abarcan varios puntos en el tiempo a menudo se rompen de forma recursiva. Del mismo modo, en informática, si un problema puede resolverse de manera óptima dividiéndolo en subproblemas y luego encontrando de forma recursiva 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 la programación lógica de restricciones:

% This code works in both YAP and SWI-Prolog using the environment-supplied
% CLPFD constraint solver library.  It may require minor modifications to work
% in other Prolog environments or using other constraint solvers.
:- use_module(library(clpfd)).
sendmore(Digits) :-
   Digits = [S,E,N,D,M,O,R,N,Y],   % Create variables
   Digits ins 0..9,                % Associate domains to variables
   S #\= 0,                        % Constraint: S must be different from 0
   M #\= 0,
   all_different(Digits),          % all the elements must take different values
                1000*S + 100*E + 10*N + D     % Other constraints
              + 1000*M + 100*O + 10*R + E
   #= 10000*M + 1000*O + 100*N + 10*E + Y,
   label(Digits).                  % Start the search

El intérprete crea una variable para cada letra del rompecabezas. El operador ins se utiliza para especificar los dominios de estas variables, de modo que se extiendan sobre el conjunto de valores {0,1,2,3, ..., 9}. Las restricciones S#\=0 y M#\=0 significa 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 quitando el valor 0 de ellas. Entonces, 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 se mantenga "ENVIAR + MÁS = DINERO" cuando cada letra es reemplazada por su dígito correspondiente. De esta restricción, el solucionador infiere que M = 1. Todas las restricciones almacenadas que involucran la variable M se despiertan: en este caso, la propagación de la all_different restricción en la restricció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 probar que el problema no tiene solución al reducir un dominio al conjunto vacío, pero también puede terminar sin probar satisfacibilidad o insatisfacción. Los literales de etiqueta se utilizan para realizar la búsqueda de una solución.

Ver también

Referencias

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 )
Cork Constraint Computation Center en archive.today (archivado el 7 de enero de 2013)
Catálogo de restricciones globales

Languages

In other projects