Charlotte Truchet

Sampling et programmation par contraintes

Zoom (if you want to participate, please request the meeting password. If your interest in the seminar is more general, you can request to be added to the announcement mailing list which will contain the password for each meeting)

La programmation par contraintes (CP) s’attache à résoudre des problèmes fortement combinatoires, exprimés sous forme déclarative. Les contraintes, relations logiques simples, permettent de modéliser le problème, que l’on peut aussi résoudre efficacement en raisonnant sur ces mêmes contraintes. La CP s’applique bien à des problèmes combinatoires issus de domaines variés, y compris hors de l’informatique (médecine, urbanisme, musique, graphisme, viticulture…). Cependant, les solveurs de contraintes ne savent énumérer des solutions que dans l’ordre où ils les trouvent, de sorte que deux solutions successives ont de grandes chances d’être très similaires. Dans cet exposé, après une introduction à la CP, on présentera un travail en cours consistant à intégrer à un solveur de contraintes des techniques permettant d’échantillonner l’espace des solutions, sans (trop) perdre en efficacité.