TASC - Théorie, Algorithmes et Systèmes en Contraintes
Thématiques de l'équipe
Transformation de modèles et synthèse de code pour des problèmes combinatoires
l’utilisation de langages de haut niveau indépendants de la technologie de résolution
sous-jacente et le besoin de modéliser finement des contraintes métiers très spécifiques
nécessitent de traiter les deux aspects suivants :
- Analyse et transformation de modèles : il y a un besoin fondamental de passer de techniques de modélisation dictées par les services offerts par les technologies et solveurs que l’on utilise, à une modélisation de haut niveau capturant les spécifications du problème traité indépendamment de la technologie sous-jacente. La conséquence est qu’étant donné un modèle de haut niveau il est important (1) de fournir des outils d’analyse de ce modèle, (2) d’identifier et d’extraire automatiquement les sous problèmes combinatoires, (3) de trouver et de casser les symétries du problème pour réduire drastiquement la taille de l’espace de recherche, et (4) de fournir des outils de transformation de modèles vers différentes technologies.
- Synthèse de code pour les contraintes métiers : face au besoin croissant pour fournir des logiciels s’adaptant à des besoins spécifiques et des profils particuliers, les grands acteurs (e.g. IBM, Microsoft, Google) privilégient les méthodes génériques. La conséquence est que si les aspects vérifications de logiciels sont bien entrés dans les mœurs, les aspects synthèses de code sont restés plus cantonnés à des niches tout en provoquant un regain d’intérêt (voir par exemple le séminaire Dagstuhl « Software Synthesis » dans lequel des chercheurs de tout horizon, dont les contraintes, ont participé). D’un point de vue contrainte, face à la diversité des contraintes métiers, il est illusoire d’écrire manuellement un code spécifique pour chaque contrainte potentielle. Le but est donc ici d’identifier des familles de contraintes et de comprendre leur structure, afin de synthétiser des services (propagation de contraintes et accélération de la convergence au point fixe, reformulation en programme linéaire, méta heuristiques, « checkers ») basés sur des propriétés structurelles de ces contraintes. On s’appuiera sur des méthodes formelles, réécriture et interprétation abstraite, pour générer, prouver et simplifier automatiquement les formules associées aux propriétés nous intéressant. Sur ce thème on s’appuiera essentiellement sur l’équipe tout en faisant appel aux collaborations déjà existantes avec A. Minet (Paris 6) dans le domaine de l’interprétation abstraite.
Aide à la décision dynamique
En passant des aspects planification stratégique vers les
aspects planification opérationnelle, un besoin se fait sentir pour prendre en compte les
problèmes d’aide à la décision dynamique dans lesquels les contraintes varient au cours
du temps. Dans un tel contexte il est nécessaire de faire varier un modèle préexistant
dans le temps pour prendre en compte des aléas ou des futurs potentiels. Cela nécessite
au niveau solveur un support spécifique pour la gestion incrémentale de contraintes.
Il est aussi nécessaire de traiter des problèmes de taille importante. Pour ce faire les
méthodes de recherche à large voisinage constituent une méthode de choix avec cependant
la limitation importante concernant le choix d’un voisinage adéquat. Nous comptons
adresser ce problème en s’appuyant simultanément sur des techniques d’apprentissage et
d’explication.
Modèles probabiliste pour maitriser la combinatoire
Dans un moteur de propagation
de contraintes il est connu depuis longtemps que les algorithmes réduisant le domaine des variables en enlevant les valeurs ne conduisant à aucune solution sont la plupart
du temps déclenchés pour ne rien déduire. Un premier travail portant sur la contrainte
« alldifferent » a été initié dans le quinquennat précédent, le but étant de déclencher à bon
escient les algorithmes de filtrage. En continuation avec ces travaux d’autres contraintes
seront considérées. On s’appuiera sur les membres de l’équipe ayant initié ces travaux ainsi
que sur la collaboration avec D. Gardy du PriSM.
Apprentissage de modèles à contraintes, d’heuristiques, de stratégies et d’invariants
Les
techniques d’apprentissage répondent à deux questions, à savoir d’une part la question de
faciliter l’accès à la technologie des contraintes en facilitant la construction de modèles
à partir d’exemples ou en évitant la recherche manuelle d’heuristiques, et d’autre part
la capture automatique de comportements exploitables par les programmes d’aide à
la décision. Dans ce cadre on s’intéresse à l’apprentissage de modèles à contraintes,
d’heuristiques d’énumération et de stratégie de jeux dont des aspects sont décrit par des
contraintes. Ces travaux se situeront dans le cadre de problèmes structurés où l’on ne peut
se baser que sur un nombre très limité d’exemples et où l’on doit apprendre un modèle
paramétré. Ils concernent aussi les problèmes faisant intervenir des séries temporelles
semi-structurées (i.e. on a des mesures par rapport à un processus industriel obéissant
à un certain nombre de règles) pour lesquels les volumes de données sont importants.
