P.P.C > Notions avancées > Les contraintes globales

Les contraintes globales ont été introduites afin d’améliorer la recherche en PPC. Les trois types principaux de contraintes sont :

  • Contraintes sémantiquement globales
    Il est impossible ou difficile de modéliser avec les contraintes basiques.

  • Contraintes algorithmiquement globales
    La complexité de l’algorithme de filtrage et / ou de la phase de propagation est plus faible.

  • Contraintes opérationnellement globales
    Le filtrage est plus efficace : le raisonnement supprime plus de valeurs inconsistantes.

Exemple 1 : la contrainte AllDifferent

Un exemple typique est la contrainte globale allDifferent. Cependant ce n’est pas une contrainte sémantiquement globale :

allDifferent ( { X1, X2, … Xn } ) = { X1!=X2, X1!=X3, … X1!=Xn, X2!=X3… }

Au moins deux types d’implémentations ont été proposées :

  • Obtenir l’AC généralisée
    On garantit qu’il existe un support pour toute valeur autorisée.

  • Obtenir la consistance de borne généralisée
    On garantit qu’il existe un support pour toutes les bornes.

Un des algorithmes efficaces de filtrage proposé pour cette contrainte globale est basé sur la recherche des Composantes Fortement Connexes (CFC) dans un graphe biparti d’affectation.


Exemple 2 : La contrainte Occurence

On souhaite avoir une contrainte prenant un ensemble de variables (x1, x2, … xn), une valeur l et un nombre d’occurrence minimal et maximal de cette valeur dans la liste. Comment mettre en place la contrainte ?

Le principe va être le suivante : si la borne maximale est atteinte, on retire la valeur des autres domaines. Si le borne minimale est atteinte, on instancie toutes les variables le pouvant à la valeur l. Pour faire tout cela efficacement, il est important de maintenir des compteurs incrémentalement.

Conclusion

  • Les contraintes globales filtrent mieux et permettent donc de réduire l’espace de recherche
  • Les contraintes globales peuvent simplifier la modélisation d’un problème
  • Les contraintes globales demandent un développement dédié : peu de contraintes globales en commun entre tous les solveurs.
  • Les contraintes globales peuvent se révéler inefficaces sur des problèmes de petite taille (le gain en recherche ne compense pas les calculs supplémentaires)

 

Voici le plan de cette présentation sur la programmation par contraintes

Cette page a été co-réalisée avec Guillaume Rochart, docteur en mathématiques dans mon équipe de recherche au Bouygues e-lab.10/03/2009.