Jeudi 3 avril 2025 (reporté)

La programmation par contraintes s’attache à résoudre des problèmes fortement combinatoires, exprimés à l’aide de relations logiques (les contraintes), portant sur des variables dans des domaines fixés, souvent finis. Chaque contrainte est dotée d’un algorithme de propagation, qui élague autant que possible les domaines des variables sans perdre de solutions. Les solveurs appliquent ces propagateurs tant que c’est possible, puis effectuent des choix (affectation d’une valeur à une variable, réduction d’un domaine) et itèrent le processus. On sait aujourd’hui résoudre des familles de contraintes assez larges (cardinalité, graphes, mots, géométrie…). Mais les mécanismes internes des solveurs posent des problèmes d’implémentation pas toujours simples. Dans cet exposé, nous présenterons les notions principales du domaine (contraintes, domaines, consistance, propagation, heuristiques) puis nous explorerons la question de l’efficacité pratique d’un de ces algorithmes (filtrage de la contrainte alldifferent). Enfin, nous examinerons les difficultés que l’on rencontre pour implémenter ce résultat théorique, en pratique, dans un solveur.

Lieu

En chair et en os dans la salle de séminaire du plateau SCAI – métro Jussieu (lignes 7 et 10) ;

• rentrer sur le campus par le 4 place Jussieu, 75005 Paris ;
• longer la clôture à droite jusqu’au bout ;
• rentrer dans le bâtiment Esclangon ;
• à gauche, monter l’escalier extérieur jusqu’au 1er étage ;
• sur le plateau SCAI, longer le tableau noir puis les baies vitrées ;
• la salle Séminaire se trouve au fond à gauche ;

ou par vidéoconférence (contacter les organisateurs).

---

---