Optimización de Restricciones

Muchos problemas de optimización combinatoria dentro de la Inteligencia Artificial se pueden representar mediante restricciones. La optimización de restricciones permite modelar y solucionar problemas de optimización combinatoria. Problemas relacionados con la planificación de calendarios, logística y planificación en general, son ejemplos de problemas de optimización de restricciones.

scheduling

Un problema de optimización de restricciones (COP, de sus siglas en inglés) se define por tres elementos fundamentalmente: el conjunto finito de variables, los dominios de valores de las variables y el conjunto de las funciones de coste que relaciona las variables. Las funciones de coste definen el coste de las tuplas de valores para subconjuntos de variables. Una solución del problema es una asignación completa (todas las variables tienen asociadas un valor) con un coste global aceptable, según el usuario. Una solución es óptima, si su coste es el mínimo de todas las posibles soluciones. La complejidad algoritmica de COP es NP-hard.