Programme de Doctorat en informatique
Département d’informatique et de génie logiciel
Faculté des sciences et de génie
Présentation de la proposition de projet de thèse (IFT-8004)
de
Jovial Cheukam Ngouonou
Le vendredi 15 décembre 2023 à 9h
Local PLT-3904
Lien Zoom : https://ulaval.zoom.us/j/3054862029
« Apprentissage automatique de cartes d’invariants
d’objets combinatoires, avec une application pour la
synthèse d’algorithmes de filtrage »
Membres du comité d’encadrement
Claude-Guy Quimper, Ph.D. (Directeur de recherche)
Département d’informatique et de génie logiciel
Remi Douence (Co-directeur)
IMT Atlantique, France
Nicolas Beldiceanu (Co-directeur)
IMT Atlantique, France
Nadia Tawbi, Ph.D. (Examinatrice)
Département d’informatique et de génie logiciel
Pascal Tesson, Ph.D. (Examinateur)
Département d’informatique et de génie logiciel
Résumé
Pour résoudre un problème d’optimisation combinatoire, on peut généralement faire appel à la programmation par contraintes. Les informaticiens par le biais de la programmation par contraintes identifient sous forme de contraintes globales les interactions qui existent entre les variables d’un problème. Puis, ils les exploitent pour réduire l’espace de recherche des solutions, en concevant des algorithmes de filtrage dédiés. Cependant, il arrive généralement que les interactions les plus importantes pour une résolution efficace d’un problème d’optimisation combinatoire échappent aux informaticiens.
Pour répondre donc à cette insuffisance, nous proposons de faire intervenir la machine pour assister l’informaticien dans la tâche de conception des algorithmes de filtrage. Plus précisément, nous faisons l’apprentissage automatique de cartes d’invariants d’objets combinatoires que sont les graphes orientés, les forêts enracinées, les partitions d’ensemble. Ces cartes sont des ensembles structurés d’invariants qui capturent un grand nombre d’interactions existant entre les variables d’un problème qui peut être modélisé à l’aide d’un objet combinatoire. Une fois que ces invariants sont générés, ceux qui rendent la résolution du problème combinatoire plus efficace sont automatiquement sélectionnés et peuvent être utilisés pour améliorer les solveurs à contraintes.
Le but de cette recherche est défini selon les points suivants :
– faire la découverte automatique de nouvelles conjectures pouvant conduire à des théorèmes utiles pour le calcul des bornes ;
– prouver formellement les théorèmes découverts ;
– utiliser ces théorèmes pour améliorer les solveurs à contraintes en assistant l’humain dans la conception des algorithmes de filtrage des contraintes globales. Ces contraintes globales sont utilisées dans la résolution des problèmes d’optimisation combinatoires.
Nous avons testé notre approche sur les problèmes de partitionnement équilibré où la structure combinatoire sous-jacente constitue les partitions d’ensemble. Les résultats montrent que la méthode est effective et bénéfique pour les solveurs à contraintes.
Abstract
To solve a combinatorial optimization problem, constraints programming can generally be used. Computer scientists use constraints programming to identify, in the form of global constraints, the interactions that exist between the variables of a problem. Then, they exploit them to reduce the solution search space, by designing dedicated filtering algorithms. However, it is generally the case that the most important interactions leading to an efficient resolution of a combinatorial optimization problem escape the attention of computer scientists.
To address this issue, we propose to use the computer in order to assist the computer scientist in the task of designing filtering algorithms. More precisely, we design a program that learns conjectures and connect them under the form of a map of invariants for combinatorial objects such as directed graphs, rooted forests, and partitions of a set. These maps are structured sets of invariants that catches a large number of interactions existing between the variables of a problem when the problem can be modeled using a combinatorial object. Once these invariants are generated, those that help to solve efficiently the combinatorial problem are automatically selected and can be used to improve a constraint solver.
The aim of this research is defined according to the following points:
– to automate the discovery of new conjectures that can lead to theorems which are useful to compute bounds;
– to prove the discovered theorems;
– to use these theorems to improve constraint solvers by assisting humans in the design of global constraint filtering algorithms. These global constraints are used in solving combinatorial optimization problems.
We tested our approach on a balanced academic curriculum problem where the underlying combinatorial structure is a partition of a set. The results show that the method is effective and beneficial for constraint solvers.
Note: La présentation sera donnée en français.
Bienvenue à tous !
