Méthodes de modélisation et résolution à base de contraintes

La programmation par contraintes (CP, Constraint Programming) est une approche de résolution de problèmes combinatoires qui repose sur la modélisation du problème à l’aide de variables, de domaines et de contraintes. Proche de la programmation linéaire en nombres entiers (ILP, Integer Linear Programming), elle s’en distingue par la nature des contraintes qui peuvent être non linéaires et par les techniques de résolution utilisées, basées sur le backtracking et la propagation de contraintes.

Cependant, tout comme pour la PLNE, la modélisation du problème est une étape cruciale qui influence fortement l’efficacité de la résolution. Dans ce cours, nous allons explorer différentes méthodes de modélisation et de résolution de problèmes à l’aide de contraintes, en mettant l’accent sur les bonnes pratiques et les techniques pour tirer profit des solveurs de contraintes.

Nous utiliserons principalement le solveur Choco-solver, un solveur de contraintes open-source en Java, pour illustrer les concepts et les techniques présentés dans ce cours. Nous aborderons également des exemples concrets et des exercices pour mettre en pratique les concepts appris. Dans les sections suivantes, nous présenterons des exemples de modélisation de problèmes à l’aide de contraintes, en détaillant les paramètres, les variables, les domaines et les contraintes associées à chaque problème. Chaque exemple sera accompagné de son implémentation en Choco-solver, permettant ainsi de comprendre comment traduire une modélisation en code exécutable.