Thierry Petit (LINA, Nantes)

Cet exposé aborde le thème de l’instafiabilité en programmation par contraintes (PPC). Un problème est sur-contraint s’il n’existe aucune affectation de valeurs à l’ensemble des variables satisfaisant la conjonction de toutes les contraintes. Tout d’abord, je rappelerai des notions générales de la PPC afin de souligner l’importance du traitement des problèmes sur- contraints. Ensuite, je présenterai successivement les aspects relatifs à :

  • la modélisation de ce type de problèmes,
  • l’exploitation de contraintes globales dédiées aux sur-contraints,
  • la définition des coûts de violation.

Je poursuivrai en évoquant les problématiques liées au calcul générique de ces coûts. Ce dernier point permettra d’illuster une application de la représentation de contraintes par des propriétés de graphes, qui offre des perspectives pouvant dépasser le cadre des sur-contraints.