– LMCO

Ce projet à 3 ans rassemble des chercheurs travaillant en mathématiques discrètes, optimisation combinatoire, programmation mathématiques et systèmes embarqués, répartis sur 3 laboratoires : - le LIP6, à Paris VI (Equipe ordonnancement de P.CHRETIENNE) ; - HEUDYASIC, de l'UTC, équipe Recherche Opérationnelle (J.CARLIER, A.MOUKRIM) ; - le LIMOS, à Clermont-Ferrand, fortmeent impliqué en programmation mathématiques. - - Il est pluridisciplinaire au sens où il rassemble des chercheurs porteurs de formalismes et d'applications de natures différentes, et au sens où, en focalisant la notion de réactivité pour des problèmes de Recherche Opérationnelle, il rapproche cette communauté de celle des systèmes embarqués (notion de Recherche Opérationnelle Embarquée) - - Ce projet vise d'abord à rapprocher les formalismes prévalant en optimisation combinatoire (problèmes d'ordonnancement : heuristiques, propagation de contraintes, contraintes temporelles...) de ceux hérités de la programmation mathématiques (problèmes de synthèse de réseaux : flots, convexité, méthodes polyédrales, dualité...). - - Il vise aussi à articuler les approches destinées à traiter les versions statiques de problèmes de routage et ordonnancement (toutes les données sont connues à l'avance), avec celles destinées à traiter leur version dynamique ou réactive (prise en compte des aspects temps réel et intercommunication). - - Il inclut une partie théorique, dédiée aux modèles et aux algorithmes, et une partie appliquée, focalisée sur le développement, le test, et l'étude d'applications réelles. - - Le premier point traité (working package) consistera en une analyse de la façon dont le facteur temps peut être introduit dans le formalisme de la synthèse de réseaux. Nous introduiront une notion de flot temporisé, ainsi qu'un problème d'ordonnancement de référence P-SCH, incluant des contraintes de disjonction généralisée et d'un critère d'optimisation non standard. Nous comparerons ainsi les approches « optimisation combinatoire » classiques avec celles découlant du formalisme de la programmation mathématique. Au niveau expérimental, nous focaliserons notre attention sur l'analyse de complexité « à postériori », en recherchant les moyens d'identifier de façon rigoureuse quelles sont les instances difficiles d'un problème et le pourquoi du comportement (sensibilité, performances...) des différentes approches algorithmiques. - - Le deuxième point traité portera sur l'étude d'une extension temporisée du problème CFA (Capacitated Flow Assignment), et sur sa mise en référence avec un problème P-ROUT de routage, planification et gestion de charges synchronisées. Nous mettrons à nouveau en analogie les méthodes standard de la synthèse de réseau (décomposition de Benders, de Lagrange, coupes...) avec les approches combinatoires de la communauté des problèmes d'ordonnancement. - - Le problème P-ROUT ayant vocation à être traité dans un contexte dynamique, nous étudierons (3° point) l'articulation entre l'analyse statique d'un tel problème et la façon dont on peut en déduire de façon formalisée des règles de décision et des heuristiques rapides adaptables à un contexte dynamique et réactif. Là encore, la partie expérimentale se focalisera sur les modes de tests et de développement susceptible de permettre une analyse rigoureuse de la complexité pratique des problèmes étudiés et une compréhension du comportement des algorithmes. - - Une dernière phase de l'étude portera sur l'identification des applications potentielles des deux problèmes de référence P-SCH et P-ROUT. ...