1.10 Conclusion et perspectives
Dans cette première partie, nous nous avons introduit
une nouvelle approche pour la gestion des décisions de branchement, que
nous avons appelée Dynamic Learning Search. Cette approche, basée
sur des techniques d'apprentissage, présente l'intérêt de
chercher à diriger la recherche vers des sous-espaces prometteurs en
définissant dynamiquement des politiques de priorités de
branchement sur les variables, ainsi que sur les valeurs que peuvent prendre
les variables. Nous avons montré qu'une phase de sondage, permettant
d'avoir un aperçu de l'arbre de recherche, pouvait s'avérer
intéressante afin d'initialiser la recherche. Enfin, nous avons
montré qu'il était possible d'appliquer cette approche aussi bien
sur des problèmes de satisfaction de contraintes que sur des
problèmes d'optimisation combinatoire. Les tests expérimentaux
ont montré que notre méthode était plus efficace que les
méthodes génériques par défaut du solver commercial
ILOG. La méthode que nous proposons est évidemment moins efficace
que les heuristiques dédiées aux problèmes d'optimisation
combinatoire ou aux problèmes de satisfaction de contraintes.
Néanmoins, dans l'optique d'une approche générique, la
méthode que nous proposons semble prometteuse.
Nous pensons cependant que d'autres critères permettant
de définir la qualité d'un sous-arbre d'une recherche
arborescente peuvent être proposés. Ces critères devront
être génériques pour permettre une application aussi bien
dans le cas de problèmes de satisfaction de contraintes que dans celui
de problèmes d'optimisation combinatoire.
| 
