Programme > Tutoriels

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

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.

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

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

"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

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

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

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

Métaheuristiques et contraintes

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

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

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

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.

Personnes connectées : 2

Vie privée