|
|
Vidéos des présentations
Plénières Plénière 1 : Définition d'une Recherche Opérationnelle Quantique
Intervention du Pr. Eric Bourreau, Université de Montpellier
lundi 26 avril 2021 à 9h30h
Présidents de session : Dr. HDR C. Prodhon & Pr. Ph. LacommeLes ordinateurs quantiques promettent depuis quelques années de résoudre efficacement les problèmes NP difficiles en offrant un nouveau paradigme de résolution. Cette présentation va présenter l'informatique quantique sous la forme d'une introduction accessible à tous ceux qui souhaitent comprendre de quoi se compose une machine quantique et comment écrire des algorithmes tirant partie de ses machines quantiques. Suffit-il simplement de passer d'une vision séquentielle à une vision quantique ? Quelles sont les briques qui composent un programme quantique ? Existe t'il plusieurs voies possibles ? Avec quelles performances théoriques et pratiques ? Autant de questions simples auxquelles cet exposé va tenter de répondre.
Plénière 2 : The Fixed-Partition Policy Inventory Routing Problem
Intervention du Pr. Claudia Archetti, ESSEC Business School in Paris, FR
mardi 27 avril à 9h
Président de session : Pr. Dominique FeilletIn this plenary, we formally introduce a variant of the inventory-routing problem (IRP) which we call the Fixed-Partition Policy IRP (FPP-IRP). In contrast to the classical IRP where delivery routes are arbitrary, the FPP-IRP partitions customers into mutually exclusive clusters that are fixed throughout the optimization horizon, and distribution is performed separately for each cluster. By restricting the flexibility inherent in the classical IRP, the FPP-IRP attains many potential advantages. First, partitioning reduces the operational complexity of the system and allows a simpler organization of the distribution service. Second, it improves the robustness of the system by isolating disruptions to affected clusters. Third, it can fit the needs and requirements of specific applications where consistency in the distribution policy, like familiarity between customers and drivers and route invariance, is required. We present two fixed-partition policies for the IRP together with mathematical formulations and valid inequalities. We also present a worst-case analysis on the performance of these policies. Extensive computational results are presented to show the behavior of these policies and glean insights into their potential benefits.
Plénière 3 : Learning to Optimise: Online and Offline Hyperheuristics for Operational Research Présidente de session : Pr. Laetitia JourdanOptimisation problems exist in many areas of business including logistics, scheduling, design, vehicle routing etc. Metaheuristics have frequently been applied to these problems but hyperheuristics offer an alternative approach that adapt themselves using learning techniques to create a bespoke optimiser for the search problem at hand. In this talk, I will describe the learning optimisation approach that is central to hyperheuristics and will cover my group’s research on the development of online and offline learning of sequences of heuristics to solve problems in the operational research and water distribution network design spaces. The talk will conclude by demonstrating that sequence-based hyperheuristics are capable of generating high-quality solutions to these problems and also can reveal important information about the mapping between the problem domain, the maturity of the optimisation process and the search strategy employed.
Plénière 4 : Scheduling tasks with precedence constraint, release times and due dates on parallel processors: Présidente de session : Pr. Nadia Brauner
Tutoriels du GDR RO Tutoriel de l’axe ”Complexité, Approximation et Graphes pour la Décision et l'Optimisation" (CAGDO)
Responsables scientifiques : d'Evripidis Bampis, Cédric Bentz, Bruno Escoffier, Valia Mitsou, Alantha Newman
Tutoriel de Christoph Dürr, Sorbonne Université, France
Dans les problèmes en ligne, les données de l'instance sont révélées au fur à mesure à l'algorithme, typiquement sous forme d'une séquence de requêtes. L'algorithme doit servir chaque requête par une décision irrévocable, pour maintenir une solution à l'instance révélée. Ces décisions engendrent un coût, qui aurait pu être optimisé, si toute l'entrée était connue à l'avance. L'analyse compétitive mesure la perte d'optimalité qui résulte de cette contrainte d'information cachée. Le but est de concevoir un algorithme au meilleur ratio de compétitivité pour le problème considéré. Les concepts de base seront introduits à l'aide du problème acheter-ou-louer. Puis nous verrons comment l'approche primale-duale peut aider à analyser et concevoir des algorithmes pour le problème de couverture par ensembles. L'introduction terminera par un modèle de problème en ligne avec conseil sans confiance. Tutoriel spécial du Groupe de Travail META de l’axe MH2PPC
Responsables scientifiques : Laurent Deroussy, Patrick Siarry, El Ghazali Talbi
Tutoriel de Maurice Clerc. France
"Cet optimiseur itératif est efficace car il garantit un bon équilibre entre exploration et exploitation"
Tutoriel de l’axe Optimisation Mathématique/Programmation Mathématique Non Linéaire (OM/PMNL)
Responsables scientifiques : Claudia D’Ambrosio, Sonia Cafieri, Amélie Lambert, Frédéric Messine, Frédéric Roupin, Gilles Trombettoni
Tutoriel de Sébastien Le Digabel, Polytechnique Montréal, Canada
NOMAD est un code gratuit pour l’optimisation de boîtes noires. Il implémente l’algorithme d’optimisation sans dérivées MADS (mesh adaptive direct search, ou recherche directe sur treillis adaptatifs). NOMAD est conçu pour résoudre des problèmes industriels, et il inclut donc plusieurs caractéristiques pratiques comme le traitement des contraintes, la possibilité de traiter plusieurs objectifs, des évaluations bruitées, etc. Ce tutoriel introduit le problème de l’optimisation sans dérivées, l’algorithme MADS et l’utilisation pratique de NOMAD, ainsi que des cas-tests réalistes, avec emphase sur l’optimisation des hyperparamètres des réseaux de neurones, pour laquelle NOMAD est naturellement adapté grâce à sa capacité à considérer les variables de catégorie. Tutoriel de l’axe “Decision, Modélisation, Evaluation, Incertitudes” (DMEI)
Responsables scientifiques : Jean Philippe Gayon, Emmanuel Hyon, Laeticia Jourdan, Stefano Moretti, Patrice Perny
Tutoriel de Nicolas Maudet, Sorbonne Université FrancePartage équitable de biens indivisibles Résumé: Allouer équitablement des ressources à des agents dotés de préférences sur les lots obtenus est un problème important, rencontré dans de nombreuses applications, et largement étudié en économie comme en informatique. Dans ce tutoriel, nous discuterons plusieurs définitions possibles de l'équité dans le cadre du partage équitable de bien indivisibles. Nous présenterons également certains algorithmes et protocoles visant à satisfaire ces propriétés, avant de conclure en évoquant quelques thématiques émergentes et questions ouvertes du domaine.
Tutoriel de l’axe Méthodes Hybrides, (Méta)Heuristiques, Programmation Par Contraintes (MH2PPC)
Responsables scientifiques : Laurent Deroussi, Arnaud Liefooghe, Pierre Lopez, Arnaud Malapert, Margaux Nattaf
Tutoriel de Jin-Kao HAO, Université d’Angers, France
Les métaheuristiques sont un outil pertinent pour l’exploration d’un espace combinatoire complexe de grande dimension. Dans ce tutoriel, nous présentons l’application de métaheuristiques à la résolution de problèmes sous contraintes. Nous partageons nos expériences sur la conception de tels algorithmes pour traiter des problèmes de satisfaction de contraintes, ainsi que des problèmes d’optimisation sous contraintes. Nous nous focalisons sur les composants les plus critiques de ces métaheuristiques qui, mis ensemble, permettent de concevoir un algorithme performant (de type recherche locale ou hybride). Ces composants sont notamment des fonctions d’évaluation, des calculs de distance ainsi que des opérateurs de voisinage ou de recombinaison. Pour illustrer ces idées, nous abordons des exemples concrets qui apparaissent pour différents problèmes : k-coloring, weighted coloring, Latin square completion, etc. Tutoriel de l’axe Ordonnancement, Plabification et Applications (OPA)
Responsables scientifiques : Jean-Charles Billaut, Nabil Absi, Safia Kedad-Sidhoum, Alix Munier, Jean-Marc Nicod
Tutoriel de Alessandro Agnetis, Università degli Studi di Siena, Italia
Most classical scheduling problems and models describe situations in which a single decision-maker has to compute the best way to arrange jobs and resources over time. In this tutorial, we present the basic notions on multiagent scheduling problems, in which a number of distinct agents, each owning a subset of all jobs, share common processing resources. The analysis in this case focuses on finding efficient and, possibly, fair solutions. After presenting some motivation, we review basic properties, illustrate the main complexity results, discuss fairness issues and point out future research directions. Tutoriel de l’axe Réseaux, Energie, Services, Transport (REST)
Responsables scientifiques : Dominique Feillet, Yannick Kergosien, Sandra Ulrich Ngueveu, Nancy Perrot, Sonia Vanier
Tutoriel de Martine Labbé, Université Libre de Bruxelles - INRIA, Lille
Un problème de tarification consiste à déterminer les prix d’un ensemble de produits ou services de façon à maximiser le revenu obtenu par la vente de ceux-ci sachant que les acheteurs potentiels effectuent leur choix en accord avec leur propre fonction d’utilité. Ce problème peut se formuler comme un problème d’optimisation biniveau dans lequel l’entité déterminant les prix constitue le premier niveau et le ou les acheteurs le second niveau. Dans ce tutoriel, je présenterai cette classe de problèmes hiérarchiques d'un point de vue théorique et algorithmique puis je me concentrerai sur certains cas particuliers dans le domaine du transports et des télécommunications. Entre autres, je présenterai des résultats de complexité et proposerai des formulations linéaires en nombres mixtes entiers.
Tutoriel de l’axe Optimisation Mathématique / Optimisation Combinatoire et Programmation en Nombres Entiers (OM/OCPE)
Responsables scientifiques : Mourad Baiou, François Clautiaux, A. Ridha Mahjoub, Ivana Ljubic
Tutoriel de Fatiha Bendali-Mailfert, LIMOS, Université Clermont Auvergne, France
La recherche de structures particulières dans un graphe est souvent modélisée par la maximisation (ou minimisation) d'une fonction linéaire, sous des contraintes linéaires, utilisant des variables binaires associées aux sommets ou aux arêtes du graphe. Cette optimisation est généralement NP-difficile. Une méthode efficace pour formuler et résoudre ce type de questions est l'approche polyèdrale. Celle-ci consiste à ramener le problème d'optimisation en nombres entiers à la résolution d'un programme linéaire sur un polyèdre décrivant l'enveloppe convexe des solutions et défini par un système d'inégalités linéaires. Pour un graphe quelconque, il est souvent difficile d'obtenir une description complète de ce polyèdre. Mais si le graphe peut être décomposé en parties à la suite de l'application de certaines opérations de décomposition : 1-sum, 2-sum, ajout ou suppression de sommets ou d'arêtes par exemple, alors il est parfois possible de donner une description complète du polyèdre à partir des polyèdres associés à ces parties. Une telle technique a été utilisée dans le cas du polyèdre des coupes, des stables ou des dominants pour des classes de graphes décomposables.
|
Personnes connectées : 28 | Vie privée |