Lorsque les contraintes sont nombreuses, il est difficile de résoudre un problème surtout si l’on souhaite trouver la meilleure solution…
Prenons l’exemple d’une gare, supposons que nous sommes en charge de l’organisation de cette gare et que nous souhaitons optimiser l’utilisation des rails, les emplois du temps du personnel, le ravitaillement des trains mais également l’arrivée d’un train en retard etc.
Avec un nombre très important de contraintes, comment fait-on pour trouver la solution la plus efficace à ce type de problème ?
Un algorithme d’optimisation puissant
Pour répondre à ces problèmes, il est utile de s’appuyer sur la programmation par contraintes. Dans le cadre de notre exemple, les problèmes sont modélisés à l’aide de variables, de décisions et de contraintes.
Un problème est vu comme une conjonction de sous-problèmes pour lesquels on dispose de méthodes efficaces de résolution. Ces sous-problèmes peuvent être très simples comme x<y ou complexe comme la recherche d’un flot compatible. Ces sous-problèmes correspondent aux contraintes.
Une contrainte est une relation entre une ou plusieurs variables qui limite les valeurs que peuvent prendre, en même temps, chacune des variables liées par la contrainte.
La programmation par contraintes va donc utiliser plusieurs méthodes pour arriver à la solution:
- Le filtrage :
La programmation par contraintes va utiliser pour chaque sous-problème une méthode de résolution spécifique à ce sous-problème, afin de supprimer les valeurs des domaines des variables impliquées dans le sous-problème qui ne peuvent appartenir à aucune solution de ce sous-problème. En procédant ainsi pour chaque sous-problème, donc pour chaque contrainte, les domaines des variables vont se réduire.
- La propagation :
Après chaque modification du domaine d’une variable il est utile de réétudier l’ensemble des contraintes impliquant cette variable car cette modification peut conduire à de nouvelles déductions. La réduction du domaine d’une variable peut permettre de déduire que certaines valeurs d’autres variables n’appartiennent pas à une solution.
- La recherche de solution :
Ensuite et afin de parvenir à une solution, l’espace de recherche va être parcouru en essayant d’affecter successivement une valeur à toutes les variables. Les mécanismes de filtrage et de propagation étant bien entendu relancés après chaque essai puisqu’il y a modification de domaines.
La programmation par contraintes est donc basée sur trois principes : filtrage, propagation et recherche de solutions.
Pour chaque problème sa solution :
Un algorithme d’optimisation peut s’appliquer à des problèmes très variés :
– Attribution des ressources,
– Ordonnancement des tâches,
– Rotation du personnel,
– Gestion des emplois du temps
– Délais
La liste est encore longue, mais si l’on prend notre cas de départ, jamais deux trains ne doivent arriver en gare en même temps sur le même quai, jamais un conducteur de train ne doit dépasser son nombre légal d’heures de conduite journalière…
