TASC - Théorie, Algorithmes et Systèmes en Contraintes

Responsable : Nicolas Beldiceanu
Pôle(s) de recherche :
SDD

L’équipe TASC est issue de la fusion en 2006 de l’équipe Contraintes des Mines Nantes fondée par P. Boizumault et d’une partie de l’équipe Contraintes Continues et Applications de l’université de Nantes. Cette nouvelle version de l’équipe TASC tient compte du départ de G. Chabert avec la création de l’équipe OGRE prenant en compte les aspects continus. TASC est équipe-projet commune avec Inria. Thierry Petit, en poste au Worcester Polytechnique et Benoït Rottembourg de la société Eurodécision seront des collaborateurs externes privilégiés de l’équipe.

Le projet scientifique de l’équipe s’inscrit dans le cadre du pôle SDD dans la continuité du quinquennat précédent avec cependant les deux infléchissements suivants :

  • La montée en puissance des aspects contraintes et apprentissage. Ce domaine a été identifié par deux séminaires Dagsthul, à savoir « Constraint Programming meets Machine Learning and Data Mining » et « Constraints, Optimisation and Data ». Notons que ce thème est aussi mentionné dans les « position papers » très récents sur les évolutions dans le domaine des contraintes.
  • Pour faire face à la variété de contraintes métiers, les aspects synthèse de code seront développés pour générer des services pour des contraintes ad hoc.

De part leur capacité à modéliser finement les restrictions d’un problème, à expliquer les résultats et à exprimer le raisonnement qualitatif, les contraintes sont largement utilisées pour faire de l’aide à la décision dans des domaines comme la gestion de crises climatiques ou l’énergie.

Thématiques
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.