La résolution de problèmes de satisfaction ou d'optimisation sous contraintes est un thème de recherche important et transversal à de nombreux domaines comme la recherche opérationnelle et l'intelligence artificielle. Différents modèles ont été proposés pour résoudre ces problèmes fortement combinatoires : la satisfiabilité propositionnelle (SAT), la satisfaction de contraintes (CSP), la programmation linéaire en nombres entiers ou 0/1 (PLNE, PL 0/1). Des progrès importants ont été obtenus ces dernières années pour chacun de ces modèles et leurs diverses extensions. Les liens forts entre ces trois modèles font que de nombreux résultats sont issus d'une incessante fertilisation croisée qui remonte à de nombreuses années. En France, on peut citer les projets de l'ex PRC-IA du début des années 90. Le projet BAHIA ``Booléens, Algorithmes et Heuristique pour l'IA'' a été le premier à réunir les trois domaines (CSP, SAT et PL 0/1) et à mener une vaste étude des liens entre les modèles et les algorithmes. Ces liens se sont considérablement renforcés depuis une quinzaine d'années.

C'est dans ce contexte que s'inscrit ce tutoriel. Sans être exhaustif, l'objectif est de faire un survol des principaux liens entre ces trois modèles et de certains des progrès récents en privilégiant ceux qui nous semblent importants pour la Programmation par contraintes (SAT -> CSP, et PL 0/1 -> CSP). Il sera structuré en deux parties.

Dans la première partie, après la présentation des modèles et des transformations connues (SAT, CSP, PL 0/1), nous donnons quelques liens au niveau algorithmique. La suite de cette partie sera consacrée aux derniers développements en SAT et CSP en insistant sur les résultats qui ont fait ou qui nous semblent susceptibles de faire l'objet de transfert entre les deux domaines. Nous donnons ensuite un bilan comparatif des modèles SAT et CSP.

Dans la seconde partie, nous présentons quelques formulations de problèmes de satisfaction et d'optimisation de systèmes de contraintes sous forme de programme linéaire (PL 0/1). Dans un premier temps, nous rappelons les modélisations classiques d'un CSP sous forme d'un PL 0/1, puis nous développons quelques modélisations récentes basées sur les notions de cliques et d'inégalités valides. Puis, nous montrons comment exploiter ces modélisations pour élaborer des méthodes hybrides de résolution.

Les méthodes complètes développées en RO s'appuient en général sur différents types de relaxations (relaxation continue, relaxation lagrangienne, relaxation composite) du problème à résoudre. La cohérence d'arc et la relaxation lagrangienne sont très utilisées respectivement en PPC et en RO. En exploitant les formulations d'un CSP sous forme d'un PL, nous montrons comment les combiner dans une technique de filtrage. Nous présentons des extensions des modélisations précédentes aux CSOP et WCSP, qui seront utilisées pour la conception de nouvelles techniques de calcul de bornes inférieures.