Optimització de Restriccions

Molts problemes d'optimització combinatòria dintre de la Intel·ligència Artificial es poden respresentar mitjançant restriccions. L'optimització de restriccions permet modelar i solucionar problemes d'optimització combinatòria. Problemes relacionats amb la planificació de calendaris, logística i planificació en general, són exemples de problemes d'optimització de restriccions.
 
scheduling
Un problema d'optimització de restriccions (COP, de les seves sigles en anglès) es defineix fonamentalment per tres elements: el conjunt finit de variables, els dominis dels seus valors i el conjunt de les funcions de cost que relaciona les variables. Les funcions de cost defineixen el cost de les tuplas de valors per a subconjunts de variables. Una solució del problema és una assignació completa (totes les variables tenen associades un valor) amb un cost global "acceptable", segons l'usuari. Una solució és òptima, si el seu cost és el mínim de totes les solucions. La complexitat algoritmica de COP és NP-hard.