Vidéos des présentations

 Les 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.

In 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
Intervention du Pr. Edward Keedwell, Exeter University, UK
Jeudi 29 avril 2021 à 9h

Optimisation 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:
Bounds and approximations
Intervention du Pr. Claire Hanen, Sorbonne University, FR
vendredi 30 avril 2021 à 9h

In 1976, Garey and Johnson proposed a polynomial algorithm for scheduling unit execution time tasks with precedence relations and due-dates, minimizing the maximum latency on two processors. The- defined an iterative procedure to adjust deadlines of the underlying decision problem until a fixed point is reached,before using a list scheduling algorithms. The adjustment algorithm considered both precedence and resource constraints. They extended the idea in a new algorithm to solve the same problem with release dates. The question of the interleaving of precedence and resource constraints for the computation of bounds and approximated solutions of scheduling problems with parallel processors have been investigated since by different authors providing polynomial algorithms for special cases, or approximation algorithms. In the meanwhile many work has been done to derive efficiently bounds for problems without prececence constraints on parallel processors, using mainly energetic reasoning and preemptive relaxation. Can these ideas be used in a context with precedence constraints and how? This talk will present some of the results of the field and list the open questions raised by them.

Introduction à l'algorithmique en ligne

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.

Voir la vidéo

Tutoriel de Maurice Clerc. France

Équilibre entre exploration et exploitation. Nécessité ou mantra ? (Slides)

"Cet optimiseur itératif est efficace car il garantit un bon équilibre entre exploration et exploitation"
Des affirmations de ce genre sont fréquentes dans la littérature, mais presque toujours trop vagues pour être convaincantes. Nous devons donc d'abord définir rigoureusement ce que sont exploration et exploitation, de telle manière qu'elles soient mesurables et suivre l'évolution de leur rapport lors de l'exécution de l'algorithme, évolution qui peut être vue comme un « profil » de comportement. Ensuite nous devons définir ce qu'est un bon profil. Doit-il être constant ? Descendant, ascendant, en cloche ou autre ? Deux séries d'expériences sont présentées, sur des problèmes de différentes difficultés. Dans la première on définit a priori un profil et on examine son influence en forçant l'algorithme à le suivre au plus près. Dans la seconde on se contente d'observer les profils générés par de bons optimiseurs et d'essayer d'en déduire quelques règles. La conclusion la plus importante est sans doute que garantir l'équilibre n'est pas toujours nécessaire et peut même être contre-productif. Mais cette étude suggère aussi quelques idées pour améliorer les algorithmes existants ou en créer de nouveaux.

 

 

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 Voir la vidéo

Optimisation de boîtes noires avec l’algorithme MADS et le solveur NOMAD     (Slides)

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é France Voir la vidéo

Partage é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 Voir la vidéo

Métaheuristiques et contraintes  (Slides)

 

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 Voir la vidéo

Multiagent scheduling problems

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 Voir la vidéo

Approches d’optimisation biniveau pour les problèmes de tarification

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

Décomposition de graphes et composition de polyèdres associés (Slides)

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.
Au cours de cet exposé, nous présentons des opérations classiques sur un graphe et quelques cas de polyèdres obtenus par cette approche. En particulier, nous nous focaliserons sur la question de recherche d'un dominant indépendant qui se pose dans le cadre des réseaux sans fil.