Sessions plénières

Les conférences plénières seront données par les orateurs suivants :

Résumés

Des bornes de complexité de type simplexe pour les méthodes de points intérieurs (Xavier Allamigeon)

La méthode du simplexe et les méthodes de points intérieurs jouent un rôle central en programmation linéaire, tant en théorie qu’en pratique. Ces deux familles d’algorithmes sont de nature assez différente : le simplexe pivote sur les sommets et arêtes du polyèdre, tandis que les méthodes de points intérieurs suivent le chemin central, une courbe lisse passant par l’intérieur.
Dans cet exposé, je montrerai que la complexité des méthodes de points intérieurs est régie par des bornes analogues à celle de la méthode du simplexe. Je présenterai tout d’abord un cube combinatoire, rappelant celui de Klee et Minty, sur lequel les méthodes de points intérieurs doivent réaliser au moins 2^n itérations (où n est la dimension), indépendamment de la fonction barrière utilisée. Cela implique que les méthodes de points intérieurs ne sont pas polynomiales au sens fort, et clôt un problème ouvert depuis quarante ans. J’introduirai ensuite une nouvelle méthode de points intérieurs, reliée à la méthode du shadow-vertex (une règle de pivotage du simplexe), dont le nombre d’itérations est, à un facteur polynomial près, optimal et borné par 2^n.
La pierre angulaire de ces travaux est le chemin central tropical, qui provient de l’étude par la géométrie tropicale d’approximations linéaires par morceaux du chemin central. Ces résultats sont issus de travaux réalisés en collaboration avec Pascal Benchimol, Daniel Dadush, Stéphane Gaubert, Michael Joswig, Georg Loho, Bento Natura, Nicolas Vandame et László Végh.

Modèles et algorithmes proactifs et réactifs en ordonnancement sous incertitudes (Christian Artigues)

La réalisation d’activittés dans une organisation s’appuie la plupart du temps sur un plan établi à l’avance mais il est fréquent que ce plan doive être revu au cours de son exécution en raison d’événements imprévus. L’ordonnancement proactif et réactif désigne un ensemble de modèles et de méthodes qui visent d’une part à établir un ordonnancement initial des tâches à réaliser en anticipant aux mieux, c’est-à-dire de manière proactive, les aléas qui vont survenir. D’autre part il s’agit de concevoir des politiques de réaction qui indiquent quand et comment cet ordonnancement initial est modifié lors de son exécution pour faire face aux perturbations.
Cet exposé présente une revue des approches proactives et réactives en ordonnancement sous contraintes de ressources, en établissant les liens avec la programmation mathématique stochastique avec recours, l’optimisation discrète robuste ajustable et les processus de décision Markoviens. On s’intéresse au cas où les modèles de réaction ou de recours s’appuient sur des structures de solution flexibles qui cadrent les possibilités d’adaptation de l’ordonnancement à chaque instant de décision. En particulier, trois structures sont détaillées : les graphes potentiels-tâches, les arbres de décision et  enfin les séquences de groupes de tâches permutables issues des contributions pionnières de François Roubellat (1941-2022). Des modèles et des algorithmes proactifs/réactifs utilisant ces structures sont décrits pour différents types d’incertitudes et de contextes d’ordonnancement sous contraintes de ressources avec un objectif de minimisation de la durée totale de réalisation des tâches ou du plus grand retard de livraison. Quelques résultats de complexité positifs et négatifs sont donnés. Des comparaisons expérimentales montrent l’intérêt de l’exploitation de ces structures pour l’ordonnancement robuste et ou stochastique par rapport aux approches classiques. Un exemple d’application dans un atelier d’assemblage est présenté.

Online Stochastic Matching (Ana Busic)

The theory of matching has a long history in economics, operations research, and computer science, with applications in many other fields. Most of the research considers the static setting. With the increased popularity of online advertising, various online matching models have been proposed that consider random arrivals of one population, while the other is known. In this talk we will survey extensions to fully online stochastic matching models, in which both populations arrive according to a stochastic process, as well as general (non-bipartite) item compatibility graphs. This line of work combines classical matching theory with queuing and inventory theory. The main departure from traditional queueing networks is that there is no notion of servers. Instead of service, activities correspond to instantaneous matching of compatible items. Applications include assemble-to-order systems, rental services, ride-hailing systems, and organ donation.

Optimization-Augmented Machine Learning (Maximilian Schiffer)

In this talk, we will bridge the gap between combinatorial optimization and machine learning to derive policies for contextual multi-stage decision-making problems that arise in various stochastic problem settings in transportation, control, and supply chain management. We will discuss how to encode effective policies by embedding combinatorial optimization layers into neural networks and training them with decision-aware learning techniques. Specifically, I will provide an overview of the underlying algorithmic pipelines and foundations, and elucidate two paradigms – learning by experience and learning by imitation – to train the pipeline’s statistical models in an end-to-end fashion. I will demonstrate the efficacy of optimization-augmented machine learning pipelines for selected application cases, among others discussing its winning performance on the 2022 EUROMeetsNeurIPS dynamic vehicle routing challenge. Finally, we will put the presented paradigms into perspective and learn how they can also be used to approximate (static) equilibrium problems, focusing on traffic equilibria as a use case.

 

Biographies

Xavier Allamigeon

Xavier Allamigeon est chercheur à Inria (centre de Saclay) et professeur chargé de cours à l’Ecole polytechnique. Ses travaux de recherche se rapportent à l’optimisation, la combinatoire, la théorie des jeux, la géométrie tropicale, la vérification formelle et la formalisation mathématique à l’aide d’assistants de preuve. Il a reçu le prix Inria – Académie des sciences du jeune chercheur (2022), un prix SIGEST (2021) de la société SIAM (2020), et le prix Gilles Kahn de la Société Informatique de France (2010).

Christian Artigues

Christian Artigues est Ingénieur de l’Institut National des Sciences Appliquées de Toulouse. Il a été doctorant CIFRE puis ingénieur recherche et développement dans le société ORDO Software de 1994 à 1998 et effectué une thèse, soutenue en 1997, en ordonnancement en temps réel d’atelier sous la direction de François Roubellat au LAAS-CNRS.  Il a été attaché temporaire d’enseignement et de recherche à l’Ecole Centrale de Lille de 1998 à 1999, puis maître de conférences à l’Université d’Avignon et des Pays de Vaucluse de 1999 à 2006, où il a passé en 2004 son habilitation à diriger des recherches en informatique. Il a été ensuite recruté comme chargé de recherche au LAAS-CNRS de Toulouse  en 2006. Il est actuellement directeur de recherche au LAAS-CNRS dans l’équipe Recherche Opérationnelle Optimisation Combinatoire et Contraintes (ROC). Ses activités de recherche concernent l’ordonnancement et les méthodes hybrides de programmation linéaire en nombres entiers et de programmation par contraintes pour l’optimisation combinatoire. Il a un intérêt particulier pour la prise en compte des incertitudes et les applications pratiques dans les domaine spatiaux, énergétiques et industriels. Il a publié ses travaux dans 75 revues internationales et 61 conférences avec actes. Il a effectué des séjours comme chercheur invité au Centre de Recherche sur les Transports de Montréal, à l’Université de Concepción au Chili et à l’Université de Technologie Tchèque de Prague. Il a coeencadré 22 thèses de doctorat et plusieurs postdocs. Il a été responsable du département Décision et Optimisation et de l’équipe ROC au LAAS, membre du bureau de la ROADEF et directeur du GDR Recherche Opérationnelle et Aide à la Décision.

Ana Busic

Ana Busic est chargée de recherche à Inria (Centre de Paris) et au Département Informatique de l’École Normale Supérieure (DI ENS), et professeure attachée IA à l’Université PSL. Elle est responsable de l’équipe-projet commune ARGO (Apprentissage, graphes, optimisation distribuée). Ses activités de recherche se situent à la frontière entre la recherche opérationnelle stochastique et l’apprentissage. Ses contributions concernent la modélisation stochastique, l’évaluation de performances, la simulation, les processus markoviens de décision, l’apprentissage par renforcement, l’optimisation et le contrôle distribué, avec des applications aux réseaux de communication et aux réseaux électriques. Elle est membre du LINCS (Laboratory of Information, Networking and Communication Sciences), laboratoire de recherche et d’innovation commun académie-industrie, entre Inria, l’Institut Mines-Télécom, l’UPMC Sorbonne Universités, Nokia Bell Labs et SystemX. Elle a reçu le prix Google Faculty Research Award (2014).

Maximilian Schiffer

Maximilian Schiffer is a tenured Professor (Universitätsprofessor W3) of Business Analytics & Intelligent Systems in the School of Management and a Core Member of the Munich Data Science Institute at the Technical University of Munich. Moreover, Maximilian is an Associate Member of the GERAD. Maximilian’s research lies at the intersection of business information systems, artificial intelligence, and optimization. He focuses on data-driven decision-making and interpretable machine learning motivated by timely research questions that evolve within the context of logistics, transportation, and supply chain management. He develops algorithms for quantitative decision support in various application fields such as digital transformation and big data, e-commerce, supply chains, and transportation systems. Among others, his research currently focuses on realizing sustainable logistics and transportation networks as well as understanding algorithmic collusion, where AI-based algorithms tacitly agree on supra-competitive prices, although not being programmed to do so. Within this context and for general contextual decision-making problems, he focuses on developing algorithms that combine machine learning and optimization. He received several awards, including the INFORMS TSL Dissertation Prize and the GOR Doctoral Dissertation Prize. He serves on the editorial boards of Transportation Science, Service Science, Business & Information Systems Engineering, OR Spectrum, and Transportation Research Part C & Part E.