AD-Lib : une bibliothèque d'agrégation/désagrégation pour des modèles de décisions séquentielles – AD-LIB

L'omniprésence des solveurs SAT, de programmation par contraintes (CP) et de programmation linéaire en nombres entiers (MIP) dans la communauté optimisation a démontré l'importance des algorithmes génériques capables de résoudre tout problème qui peut s'exprimer dans un paradigme spécifique.

Dans ce projet, on s'intéresse à tout problème qui peut être exprimé comme un processus de décisions séquentielles. Ces problèmes admettent des formulations mathématiques fortes, et un grand nombre d'algorithmes dédiés.

Un inconvénient important de ces formulations est le nombre généralement exponentiel ou pseudo-polynomial de variables et de contraintes. Pour surmonter cette limitation, plusieurs méthodes basées sur l'agrégation/désagrégation de variables/contraintes ont été introduites dans différentes communautés.

Les conclusions d'une étude préliminaire de la littérature est que des techniques similaires sont utilisées sous différents noms dans différents domaines, conduisant à une littérature scientifique non connexe. En outre, les algorithmes pour contrôler le processus d'agrégation restent relativement sommaires.

Nos principaux objectifs dans ce projet relèvent de trois groupes : un formalisme générique qui englobe les techniques susmentionnées ; des algorithmes plus efficaces pour contrôler l'agrégation ; des codes open-source qui intègrent ces algorithmes pour résoudre différents problèmes difficiles.

Nous étudierons conjointement deux types d'approches, MIP et SAT, pour atteindre nos objectifs. Leur complémentarité sera déterminante pour le succès de nos algorithmes.

Nos tâches : 1) confronter les littératures pour identifier les idées communes et celles qui peuvent apporter des contributions dans l'autre champ ; 2) améliorer les stratégies génériques d'agrégation ; 3) appliquer les techniques d'agrégation aux méthodes d'apprentissage de clauses en CP ; 4) des implémentation open-source de nos algorithmes ; 5) leur application à des problèmes complexes.