Presentation

Ce thème concerne la modélisation et la recherche d’algorithmes efficaces pour différents problèmes d’optimisation issus de la recherche opérationnelle et des mathématiques appliquées. Le contexte applicatif est très large, allant du continu au discret, du déterministe au stochastique, des graphes aux modèles variationnels.
La nature des problèmes d’optimisation étudiés est :

• Combinatoire : trouver le plus petit ou le plus grand élément parmi un ensemble fini d’éléments. Les variables prennent alors des valeurs entières.

• Continue : trouver le plus petit ou plus grand point d’un ensemble infini non-dénombrable. Les variables peuvent prendre des valeurs réelles.

Les problèmes d’optimisation combinatoire sont étudiés à travers plusieurs approches selon leurs difficultés et leurs structures :

• Approches polyédrales : il s’agit de ramener le problème à la résolution d’un programme linéaire. Cette tâche est impossible quand le problème en question est NP-complet, mais la détermination d’un programme linéaire relaxé est facile et offre en général des bornes très utiles pour entamer la résolution par des algorithmes de branch-and-bound-and-cut. Ce sont les algorithmes exactes les plus performants pour résoudre les problèmes d’optimisation combinatoire difficiles. Cette approche est aussi utilisée pour décrire des instances où un problème NP-complet devient polynomial. Ceci est réalisé en décrivant complètement le polytope associé au problème par un programme linéaire avec des contraintes faciles à séparer (nous pouvons introduire en un temps polynomial les contraintes nécessaires à l’optimisation malgré leur nombre exponentiel dans la plupart des cas).

Les principaux résultats obtenus sont :

• Des caractérisations complètes de polytopes et des résultats expérimentaux basés sur les algorithmes de plans-coupants pour des problèmes de connexité issus des télécommunication [ACL-RI-1-22, ACL-RI-1-23, ACL-RI-1-155].

• Des résultats polyédriques sur des questions liées aux graphes parfaits [ACL-RI-1-21, ACL-RI-1-73, ACL-RI-1-107, ACL-RI-1-111, ACL-RI-1-123].

• La caractérisation de toutes les instances où la relaxation linéaire classique du problème du « facility location » et celle du p-médian définie un polytope entier [ACL-RI-1-29, ACL-RI-1-30].

• Des résultats plus récents concernent une nouvelle formulation du problème du dominant de poids minimum qui a permis la résolution d’une question ouverte [C-ACTI-LN-1-50], et la résolution d’un autre problème ouvert depuis 25 ans issu de la conception des circuits VLSI [C-ACTI-LN-1-51]. Ce travail a été effectué dans le cadre d’une collaboration avec IBM T.J. Watson Research Center, NY, USA (en partie dans le cadre d’un PICS 2011-2014).

• Algorithmes d’approximation : il s’agit de développer des algorithmes polynomiaux dont la valeur de la solution trouvée est comparable analytiquement à la valeur de la solution optimale. La mesure prise est le rapport d’approximation en pire cas, entre la valeur trouvée et la valeur de l’optimal. Des mesures de rapports d’approximation en moyenne sont aussi considérées lorsque cela peut être défini. Les approches développées sont principalement sur le problème du « vertex cover » (connexe ou pas), sur l’arbre de Steiner et sur l’indépendant maximal. Les résultats obtenus sont, d’une part, des études analytiques des performances des algorithmes et de la qualité des solutions qu’ils retournent, et d’autre part des résultats expérimentaux [ACL-RI-1-15, ACL-RI-1-33, ACL-RI-1-95, ACL-RI-1-96].

• Optimisation robuste : Dans de nombreuses applications les données ne sont pas connues avec exactitude. L’incertitude associée est souvent représentée par plusieurs scénarios. Ces différents scénarios sont en général modélisés par l’ajout de nouvelles variables et contraintes. L’optimisation robuste est étudiée à travers des applications au routage dans l’internet [ACL-RI-1-148].

Les problèmes étudiés en optimisation continue se concentrent sur les aspects suivants :

• Les extensions de la notion de convexité, la relation entre optimalité globale et optimalité locale. On s’attache ici à rapprocher les modèles non convexes des modèles combinatoires par différentes reformulations.

• Les schémas de décomposition primale et duale des systèmes complexes. On s’intéressera plus particulièrement aux méthodes d’éclatement d’opérateurs pour la décomposition de problèmes d’optimisation convexe et leur parallélisation sur GPU [ACL-RI-1-51].

• Méthodes de type Lagrangien/Lagrangien augmenté, pour la simulation des déformations d'édifices volcaniques en présence d'une fracture. Application à l'identification de fracture à partir des des déformations de surface. Ce travail est affectué dans le cadre du Labex ClerVolc an collaboration avec le laboratoire mathématiques de de l’université Blaise Pascal et le laboratoire Magma et Volcans [C-ACTI-1-134].

• L'optimisation et, plus généralement l'aide à la décision, lorsque les critères sont coûteux en calcul.

Les problèmes étudiés sont issus de divers domaines : réseaux de transport (en liaison avec le labex Imobs3 et le projet transversal STIC mobilité), réseaux de télécommunication, réseaux électriques, bio-informatique (en liaison avec le projet transversal STIC Vivant-Environnement), réseaux de capteurs, localisation des infrastructures, nucléaire, automobile. On peut observer une forte collaboration entre ce thème, notamment à travers les travaux autour de l’optimisation continue, et le thème « Image et Apprentissage ». Cette collaboration s’est traduite par plusieurs publications communes sur des problèmes liés à la reconstruction d’images bruitées [C-ACTI-1-26, ACL-RI-1-85, C-ACTI-LN-1-26, C-ACTI-LN-1-43]. Notons en particulier la référence [C-ACTI-1-26] qui a eu le prix du meilleur article dans la conférence internationale VISAPP 2010 à Angers.

Par ailleurs, l’intégration des chercheurs de l’EMSE a permis l’élargissement de ce thème aux modèles probabilistes pour l'aide à la décision. Les modèles probabilistes étudiés sont le plus souvent spatiaux et de type processus Gaussiens. Les recherches réalisées visent à en spécifier les fonctions de corrélations (ou noyaux) de manière à représenter au mieux les phénomènes simulés. Ainsi, les recherches développées dans MAAD se sont intéressées aux processus monotones [C-ACTI-1-130], additifs, avec des contraintes d'égalité fonctionnelles [ACL-RN-1-5]. L'essentiel des applications ici concerne l'exploitation de simulateurs numériques physiques (ex., simulateurs pour des systèmes d’équations aux dérivées partielles, résolution par éléments finis) : ces simulateurs sont de véritables prototypes virtuels et ont un coût computationnel qui en restreint beaucoup l'utilisation; il s'agit alors de développer des méthodes mathématiques et informatiques pour pouvoir les utiliser à des fins de plans d'expériences, de calage [ACL-RI-1-85], de propagation d'incertitudes et d'optimisation [ACL-RI-1-160]. Récemment, les approches probabilistes proposées par les chercheurs de MAAD ont été appliquées aux données recueillies par capteurs à des fins de diagnostic et de prévision. Les travaux réalisés ont comme originalité d'intégrer le modèle probabiliste dans la méthode d'aide à la décision: par exemple, des méthodes d'optimisation avec prise en compte des incertitudes [ACL-RI-1-56]. En prolongement de ces travaux, un projet de chaire industrielle, chaire OQUAIDO, portée par l’EMSE (O. ROUSTANT et N. DURRANDE) a été proposé. Le sujet de la chaire OQUAIDO porte sur la problématique des "computer experiments" (plans d'expériences avec des simulateurs numériques coûteux en calcul, Meta modélisation, optimisation, analyse de sensibilité, ... ) et se trouve en forte interaction avec le thème 4 (Modélisation, Intégration, Simulation).

En optimisation combinatoire comme en optimisation continue, les chercheurs ont souvent recours aux heuristiques pour aborder des problèmes difficiles à résoudre, par exemple non-convexes, ou quand la structure des variables entières est difficile à caractériser, ou lorsque tout simplement la taille des instances à étudier est très grande. Les heuristiques n’offrent pas de garantie sur la solution trouvée, mais lorsqu’elles sont combinées avec la solution obtenue par la relaxation du problème étudié, il est possible alors d’espérer au moins des garanties empiriques, c’est-à-dire une garantie par instance. Dans ce cadre, plusieurs heuristiques ont été développées par MAAD [ACL-RI-1-14, ACL-RI-1-59, ACL-RI-1-87, ACL-RI-1-96, C-ACTI-LN-1-25].