Section 06 Sciences de l'information : fondements de l'informatique, calculs, algorithmes, représentations, exploitations

V. Aide à la décision et recherche opérationnelle

La recherche opérationnelle et l'aide à la décision (RO-AD) forment une discipline par nature interdisciplinaire, couvrant plusieurs champs scientifiques comme les mathématiques, l'informatique, la gestion et l'économie. Cette discipline a pour objet l'étude générale des problèmes de décision (modéliser, analyser, prévoir, optimiser, simuler, évaluer, etc.) issus de contextes applicatifs. Elle a pour vocation non seulement d'obtenir des résultats fondamentaux mais également de fournir des réponses concrètes aux problèmes complexes posés en pratique, notamment sous la forme de logiciels. Au-delà des systèmes de production, de la logistique industrielle, ou de la conception et l'exploitation des grands réseaux physiques (transport, énergie, télécommunications), depuis la fin des années 90, le champ d'application de la RO-AD s'est étendu à de nouveaux secteurs tels la logistique hospitalière, la génétique, la conception de circuits micro-électroniques, l'ordonnancement d'architectures de calcul massivement parallèles, la robotique, et la finance.

En France, la RO-AD est historiquement centrée sur les problèmes d'optimisation mathématique et rejoint ainsi naturellement les mathématiques discrètes et appliquées, ainsi que l'informatique fondamentale.

A. Heuristiques et modèles

Dans ce contexte, nous observons deux tendances fortes. La première est relative à l'approximation, au caractère heuristique des approches algorithmiques. Les modèles s'enrichissent et leur échelle augmente à mesure que les succès de la discipline se déploient dans le monde économique. La masse exponentiellement croissante des données à disposition tend à renforcer cet effet. Simultanément les besoins en réactivité se sont accrus, limitant souvent les temps de résolution à quelques minutes, parfois quelques secondes. Ainsi, nous assistons depuis une dizaine d'années à l'avènement des heuristiques, pour lesquelles on s'emploie à caractériser les temps d'exécution, au regard de la qualité des solutions produites. Cette tendance s'observe autant en optimisation combinatoire avec les algorithmes dits de recherche locale et les algorithmes évolutionnaires, qu'en optimisation continue avec les algorithmes à base de gradient approché voire stochastique. Ces approches algorithmiques heuristiques itératives permettent aujourd'hui de traiter de façon satisfaisante en pratique des problèmes de très grande taille (jusqu'à des millions de variables de décision dans certains cas). Néanmoins, leur caractère heuristique, hybride (c'est-à-dire mélangeant plusieurs paradigmes algorithmiques), itératif, souvent randomisé et parallélisé (voire distribué), les rend extrêmement complexes à analyser que ce soit dans le pire des cas ou plus encore pour des instances réalistes. Les heuristiques avec garantie de performance permettent de pallier ce défaut mais n'offrent généralement pas un bon comportement moyen. Un défi dans ce domaine reste donc de parvenir à de bonnes heuristiques en pratique qui ont aussi des garanties de performance.

La seconde tendance concerne les modèles de décision et d'optimisation eux-mêmes, qui initialement déterministes et simplistes sont devenus plus riches. Des modèles d'optimisation stochastique traitant les aléas dans les données du problème ont été développés, ainsi que des modèles d'optimisation robuste visant à gérer les risques dans la prise de décision. Il est également davantage fait appel à la notion de ré-optimisation, qui permet d'appréhender le caractère dynamique des contextes d'optimisation sous un angle plus opérationnel. Bien que peu mis en œuvre jusqu'à présent, les modèles d'optimisation multicritère connaissent un regain d'intérêt. Ils s'inscrivent dans un courant plus large, visant à étudier et intégrer les modèles produits par les sciences humaines et sociales, permettant de prendre plus finement en compte les facteurs humains et de situation dans la prise de décision. Ce courant rejoint ainsi les préoccupations d'une partie de la recherche effectuée en intelligence artificielle.

B. CSP et SAT

Les modèles de satisfaction se rencontrent principalement dans le paradigme de la programmation par contraintes (CSP) et la satisfaisabilité de clauses logiques (SAT). Les travaux menés dans ce contexte ont été particulièrement intenses ces dernières années à la fois sur les plans théorique et pratique, et ont été associés au développement de solveurs de plus en plus performants. Citons en premier des résultats théoriques importants faisant le pont entre toute une famille de résultats d'inapproximabilité et la conjecture des jeux uniques posée par Khot (une variante plus puissante du théorème PCP), de nouveaux résultats de dichotomie sur de nouvelles classes de CSP (ces CSP sont alors soit dans P soit NP-complets), ou encore sur les phénomènes de seuils de SAT.

Les approches algorithmiques ont vu l'avènement de méthodes d'optimisation convexe pour des problèmes de très grande taille présentant d'excellentes garanties de convergence. En optimisation robuste, où là aussi on s'intéresse à des problèmes de très grande taille, des travaux récents permettent de garantir certains types de complexité algorithmique en fonction du modèle d'incertitude utilisé. Ces avancées ainsi que le raffinement des modèles se sont concrétisés par un déploiement massif de logiciels d'optimisation dans les entreprises de tous les secteurs et de toutes les tailles, avec même une accélération ces dernières années. Ils sont entre autres devenus un outil indispensable du praticien en RO-AD. Tirée par des besoins économiques forts, la tendance est à l'hybridation voire l'unification des différentes techniques d'optimisation au sein de solveurs de programmation mathématique toujours plus génériques, aussi appelés solveurs d'optimisation globale, qui apparaissent aujourd'hui comme le nouveau graal de la discipline. Encore à l'état de prototypes, un challenge scientifique et technologique est de parvenir à rendre ces solveurs opérationnels.

Ces avancées ont aussi eu un impact fort sur plusieurs domaines en intelligence artificielle comme la planification d'actions où les nouveaux planificateurs utilisent des solveurs SAT. Les langages de programmation logique ont aussi bénéficié de ces travaux, notamment ASP (« Answer Set Programming »). Aujourd'hui, par la disponibilité de plusieurs solveurs performants, l'ASP apparaît comme une implantation effective du raisonnement non monotone comme il avait été théorisé par Reiter en 1980 en logique des défauts. Mais bien au-delà du raisonnement non monotone, l'ASP est également un formalisme adapté à de nombreux domaines de la représentation des connaissances en intelligence artificielle (raisonnement de sens commun, web sémantiques...) et à la résolution de problèmes combinatoires (planification, problèmes de théorie des graphes, configuration, bioinformatique...). Ce dernier aspect, certainement le plus prometteur pour l'ASP, est basé sur l'idée de coder chaque problème à l'aide d'un programme logique dont les modèles correspondent aux solutions du problème.

C. Rayonnement et transfert

La RO-AD française jouit d'une bonne visibilité internationale dans le domaine de l'optimisation, discrète ou continue. Contribuant peu aux avancées en programmation linéaire en variables mixtes, elle se distingue en optimisation combinatoire, optimisation convexe et en optimisation globale. Elle est également à la pointe dans le domaine des techniques SAT et à base de contraintes. Les activités de transfert sont bien développées. De nombreuses grandes entreprises et institutions françaises disposent ainsi de compétences voire d'un département de RO-AD : Airbus, Air France, Air Liquide, Bouygues, Dassault Aviation, EDF, Google France, GDF SUEZ, Michelin, Orange, Renault, SNCF, Thales, Veolia, etc. La France compte également un réseau de plusieurs dizaines de PME et TPE fournissant des services spécialisés dans le domaine. Enfin citons le cas de la société française ILOG, leader mondial dans l'édition de logiciels en RO-AD, qui a récemment été acquise par IBM.