– ARS

La problématique principale de ce projet porte sur les méthodes automatiques permettant d'obtenir des formulations alternatives pour un problème d'optimisation donné. Ces problèmes sont généralement définis en fonction de leurs paramètres, des variables de décision (entières et/ou continues), de(s) fonction(s) objectif et des contraintes. Des formulations équivalentes peuvent fournir des descriptions d'égale qualité, mais les algorithmes de résolution dépendent eux nettement de la formulation utilisée dans leur comportement et leur efficacité. Ces différences peuvent notamment porter sur plusieurs ordres de grandeur. Cela permet de souligner l'importance d'une étude systématique de techniques de reformulation et de la recherche de techniques originales. - - L'implantation de ces reformulations est également une phase importante car une reformulation peut-être évaluée par ses performances pratiques. Jusqu'à maintenant, les seules librairies de reformulation existantes sont les librairies de pré-traitement des solveurs commerciaux de programmation linéaire (LP) et de programmation linéaire en variables mixtes (MIPL) et ces libraires présentes de nombreux inconvénients: (a) aucune étude théorique systématique n'est fournie avec le code; (b) elles ne peuvent pas être utilisées séparément des solveurs; (c) le nombre de configurations d'utilisation qu'elles offrent est limité; (d) elles ne peuvent pas être étendues par l'utilisateur. En d'autres termes, elles sont implantées en dur dans les programmes. Néanmoins, leur importance est cruciale et elles permettent de faire la différence entre un outil de recherche et un code commercial en ce qui concerne la fiabilité des solveurs, Telle est la situation pour les solveurs LP et MILP. - - Pour les autres champs de l'optimisation, la situation est peu satisfaisante, voire catastrophique. Bien que la reformulation soit déjà un sous-thème de l'optimisation globale, de nombreux développements sont nécessaires avant de voir émerger un véritable solveur d'optimisation globale fiable par exemple. Les solveurs MILP commerciaux sont généralement capables de fournir une solution à la plupart des problèmes MILP exprimés sous la forme d'un programme mathématique, sans prendre en compte la structure du problème, à part la linéarité de la fonction objectif et des contraintes. Cela est dû à la fois aux avancées algorithmiques et à la phase de pré-traitement, autrement dit, la reformulation du problème précède la recherche de solutions. Pour les problèmes issus de la programmation non linéaire en variables mixtes (MINLP), la littérature actuelle fournit des algorithmes satisfaisants mais encore trop peu de techniques de reformulation. - - Le besoin en reformulations automatiques ainsi que la validité de celles-ci suggèrent une approche complémentaire à l'algorithmique qui n'a pas encore été explorée en profondeur: à savoir l'inclusion de la formulation elle-même dans les éléments du problème qui sont autorisés à varier pendant le processus d'optimisation. Plus précisément, la recherche d'une solution optimale ne se fait pour l'instant que dans ce qui est appelé l'espace des solutions , alors qu'une possibilité intéressante serait de permettre également le parcours de l'espace des formulations , c'est-à-dire que les algorithmes pourraient eux-mêmes modifier, pendant la recherche, la formulation en accord avec le problème qu'ils éprouvent. L'implantation de cette idée requiert un ensemble d'outils logiciels très avancés. En particulier, l'implantation logicielle pourrait modifier symboliquement les expressions algébriques de la fonction objectif et des contraintes, et pourrait manipuler les entités (paramètres, variables, fonction objectif et contraintes) d'ensembles de problèmes comme des structures combinatoires plutôt que numériques. - - Ce projet se propose de fournir une étude systématique des reformulations existantes, d'en ajouter de nouvelles, de développer des algorithmes capables d'explorer l'es...