Utilisation de réseaux de neurones pour le filtrage basé sur les coûts en programmation par contraintes

La programmation par contraintes est un paradigme permettant d’obtenir des solutions exactes à des problèmes combinatoires. Ces problèmes sont utilisés dans de nombreux do-maines de l’industrie, mais leur complexité, entrainant des temps de résolution longs, peut constituer un défi. Ces dernières années, plusieurs méthodes guidées par les données ont été introduites avec des résultats prometteurs. Ces approches visent surtout à améliorer les choix de branchement ou le calcul des bornes primales, en vue d’accélérer la résolution. Ce mémoire se focalise sur le mécanisme de propagation de certaines contraintes globales. En effet, plusieurs de ces contraintes utilisent un filtrage basé sur le coût nécessitant le calcul de bornes via la relaxation lagrangienne. La qualité de ces bornes impacte directement l’efficacité du filtrage de la contrainte et, par conséquent, les performances de résolution. Cette qualité est déterminée par les multiplicateurs de Lagrange utilisés dans la relaxation. Le calcul de multiplicateurs appropriés est donc essentiel. Ceux-ci proviennent d’un processus itératif qui nécessite de résoudre une relaxation à chaque itération et s’avère donc coûteux en temps de calcul. Pour pallier ce problème, ce mémoire propose une approche guidée par les données centrée sur ces multiplicateurs. Un réseau de neurones sur graphe est utilisé pour modéliser la relation entre les caractéristiques du problème et les multiplicateurs. Ce type de réseau de neurones est bien adapté à la tâche, car la plupart des problèmes d’optimisation combinatoire peuvent être modélisés comme un graphe. L’approche proposée a été intégrée dans un solveur de programmation par contraintes, et évaluée sur plusieurs problèmes. Les résultats montrent une réduction du temps de résolution, indiquant que la prédiction des multiplicateurs peut améliorer le filtrage selon le coût de certaines contraintes globales. Cette approche est indépendante du problème et peut donc être intégrée dans les propaga-teurs de certaines contraintes globales dans des solveurs de programmation par contraintes. Bien que la réduction de temps de calcul actuelle soit modérée, des recherches futures sur l’amélioration de la stratégie d’entraînement et de l’architecture du modèle devraient per-mettre d’obtenir des gains de performance plus importants.