Problema de satisfacción de restricciones ponderadas

En inteligencia artificial e investigación operativa , un problema de satisfacción de restricciones ponderadas ( WCSP , por sus siglas en inglés), también conocido como problema de satisfacción de restricciones valoradas ( VCSP , por sus siglas en inglés ), es una generalización de un problema de satisfacción de restricciones (CSP, por sus siglas en inglés) donde algunas de las restricciones pueden ser violadas (según un grado de violación) y en el que se pueden expresar preferencias entre las soluciones. Esta generalización permite representar problemas del mundo real, en particular aquellos con restricciones excesivas (donde no se puede encontrar ninguna solución sin violar al menos una restricción), o aquellos donde se busca una solución de costo mínimo (según una función de costo ) entre múltiples soluciones posibles.

Una red de restricciones ponderadas (WCN), también conocida como red de funciones de costo (CFN), es una tripleta${\displaystyle \langle X,C,k\rangle }$donde X es un conjunto finito de variables discretas, C es un conjunto finito de restricciones suaves y${\displaystyle k>0}$es un número entero natural o${\displaystyle \infty }$.

Cada restricción suave${\displaystyle c_{S}\in C}$implica un conjunto ordenado S de variables, llamado su alcance, y se define como una función de costo de${\displaystyle l(S)}$a${\displaystyle \langle 0,...,k\rangle }$dónde${\displaystyle l(S)}$es el conjunto de instanciaciones posibles de S. Cuando una instanciación${\displaystyle I\in l(S)}$se le da el costo k , es decir,${\displaystyle c_{S}(I)=k}$Se dice que está prohibido. De lo contrario, está permitido con el costo correspondiente (0 es completamente satisfactorio).

En WCSP, subclase específica de Valued CSP (VCSP), ^{[ 1 ]} los costos se combinan con el operador específico${\displaystyle \oplus }$definido como:

${\displaystyle \forall \alpha ,\beta \in \langle 0,...,k\rangle ,\alpha \oplus \beta =\min(k,\alpha +\beta )}$.

La inversa parcial de${\displaystyle \oplus }$es${\displaystyle \ominus }$definido por:

Si${\displaystyle 0\leq \beta \leq \alpha <k}$,${\displaystyle \alpha \ominus \beta =\alpha -\beta }$y si${\displaystyle 0\leq \beta <k}$,${\displaystyle k\ominus \beta =k}$.

Sin pérdida de generalidad, la existencia de una restricción nula${\displaystyle c_{\emptyset }}$(un costo) así como la presencia de una restricción unaria${\displaystyle c_{x}}$Se asume que para cada variable x .

El coste total de una instanciación completa${\displaystyle I\in l(X)}$es la suma limitada del costo de I en${\displaystyle c_{S}}$para todas las restricciones suaves${\displaystyle c_{S}\in C}$, incluyendo el costo nulo${\displaystyle c_{\emptyset }}$y los costos unarios para I de las variables en X.

Considerando un WCN/CFN, la tarea habitual (NP-difícil) del WCSP es encontrar una instanciación completa con un coste mínimo. Se pueden definir otras tareas en el campo relacionado del modelo gráfico . ^{[ 2 ]}

Se ha demostrado que los algoritmos de transferencia de costos son particularmente eficientes para resolver problemas del mundo real cuando las restricciones flexibles son binarias o ternarias (la aridad máxima de las restricciones en el problema es igual a 2 o 3). Para restricciones flexibles de alta aridad, la transferencia de costos se convierte en un problema grave, ya que es necesario controlar el riesgo de explosión combinatoria .

Se ha propuesto un algoritmo, denominado GAC ^w -WSTR ^{[ 9 ]} , para imponer una versión débil de la propiedad de Consistencia de Arco Generalizada (GAC) en restricciones flexibles definidas extensionalmente mediante la enumeración de tuplas y sus costos. Este algoritmo combina dos técnicas: la Reducción Tabular Simple ( STR ) ^{[ 10 ]} y la transferencia de costos. Se identifican los valores que ya no son consistentes con respecto a GAC ​​y se calculan los costos mínimos de dichos valores. Esto resulta particularmente útil para realizar de manera eficiente las operaciones de proyección necesarias para establecer GAC.

También se han estudiado funciones de coste globales con una semántica dedicada (por ejemplo, SoftAllDifferent, SoftAmong) y complejidad politemporal. ^{[ 11 ]}

• https://www.ics.uci.edu/~dechter/software.html
• https://miat.inrae.fr/toulbar2 (basado en operaciones de transferencia de costes)

Muchos benchmarks WCSP del mundo real están disponibles en http://genoweb.toulouse.inra.fr/~degivry/evalgm ^{[ 12 ]} y https://forgemia.inra.fr/thomas.schiex/cost-function-library (versión anterior en http://costfunction.org/en/benchmark ). Más benchmarks MaxCSP disponibles en http://www.cril.univ-artois.fr/~lecoutre/#/benchmarks (sitio obsoleto, ver también http://xcsp.org/series ).

• Problema de satisfacción de restricciones
• Programación con restricciones
• Planificación basada en preferencias