Hui en dia, molts problemes reals poden ser modelats com a problemes de satisfacció de restriccions (CSPs) i ser resolts utilitzant tècniques de programació de restriccions. Estos problemes pertanyen a diferents àrees de coneixement com ara la intel·ligència artificial, la investigació operativa, els sistemes d'informació, les bases de dades, etc. Els CSPs pertanyen a la categoria de problemes NP-complets pel que és necessari l'ús de ferramentes que simplifiquen el problema de manera que es trobe una solució de forma eficient. Les tècniques més comuns per a manejar un CSP són les tècniques de consistència i les tècniques de recerca. Les tècniques de consistència o de filtrat tenen com a objecte reduir l'espai de recerca
mitjançant el filtrat dels dominis de les variables. Les tècniques d'arc-consistència són les més utilitzades ja que duen a terme una important poda de dominis, eliminant valors que no formen part de la solució, d'una manera eficient.

Per això, proposar algorismes que aconseguixen l'arc-consistència ha sigut un punt central en la comunitat científica per a reduir la complexitat tant espacial com temporal d'aquestos algorismes.

No obstant això, molts treballs que investiguen l'arc-consistència duen a terme assumpcions que no estan presents en molts problemes de la vida real. Per exemple, una mateixa parella de variables poden participar en més d'una restricció, el que es denomina problema no-normalitzat,
i quan la grandària dels dominis és gran, el procés de normalització pot resultar prohibitiu. En estos casos la 2-consistència du a terme una reducció dels dominis de les variables major que l'arc-consistència, pel que els algorismes de recerca poden resultar més eficients. No obstant això, la literatura és escassa en relació al desenvolupament d'algorismes que aconseguixen la 2-consistencia.

En aquesta tesi presentem nous algorismes d'arc-consistència i de 2-consistència com algorismes de preprocés per a la resolució de problemes de satisfacció de restriccions. Estos algorismes presenten un millor comportament que les actuals tècniques existents a la literatura en alguns dels criteris d'eficiència establerts per la comunitat científica: reducció del nombre de revisions de restriccions, reducció de la quantitat de propagacions, disminució del temps de còmput, o l'augment de la quantitat de poda. En aquest treball també presentem un algorisme de normalització híbrid, que permet calcular el cost del procés de normalització requerit per a aplicar les tècniques existents a la literatura.
En quant a les tècniques de recerca, en aquesta tesi presentem dos algorismes: un algorisme heurístic de propòsit general i un algorisme complet i dependent del domini. Ambdós algorismes es beneficien dels resultats proporcionats per les tècniques de 2-consistència desenvolupades en aquesta tesi.

Addicionalment, i pel fet que molts problemes reals poden modelar-se de forma natural per mitjà de l'ús de restriccions no-binàries, en aquesta tesi proposem un llenguatge de modelatge que combina l'ús de CSPs amb restriccions no-binàries i planificació POCL per a problemes de planificació i scheduling. El llenguatge de modelatge proposat permet codificar restriccions complexes, expressar l'ús dels recursos continus i beneficiar-se de les tècniques de consistència desenvolupades en aquesta tesi.

Totes les tècniques presentades s'han avaluat empíricament amb diferents instàncies de problemes aleatoris i benchmarks. També han sigut aplicades a la resolució del problema de planificació d'horaris ferroviaris.