Séminaires ROSP 2022-2023

Sylvain Bouveret est maitre de conférences à l'ENSIMAG à Grenoble et chercheur au LIG (Laboratoire d'Informatique de Grenoble). En 2021 il a pris un CPP (Congé pour Projet Pédagogique), destiné à élaborer une offre de formation prenant en compte les impacts environnementaux du numérique (analyse de la consommation électrique, élaboration d'algorithmes et de programmes sobres énergétiquement, cycle de vie des équipements). Dans ce cadre il a notamment créé un amphi-quiz de 2h à destination des étudiant.es de 3ème année, qu'il nous fera tester le 22 septembre (en version accélérée d'une heure environ). La présentation sera suivie d'un temps de discussion pour ceux qui le souhaitent. C'est un format facilement intégrable dans nos maquettes pour parler des impacts environnementaux du numérique et d'une transition vers un numérique plus responsable.

La programmation linéaire est aujourd'hui largement utilisée pour concevoir, simuler voire piloter différents types de systèmes énergétiques, et ce à plusieurs échelles . En effet, l'intégration de sources intermittentes comme le solaire, l'éolien ou la chaleur fatale nécessite le recours à des moyens de flexibilité comme le stockage (journalier jusqu'à saisonnier). Il en résulte des problèmes opérationnels complexes, où des décisions de production d'énergie doivent anticiper variations météorologiques, phénomènes sociaux, prix de l'énergie et tenir compte de comportements parfois non-linéaires. Pour la pré-conception de systèmes énergétiques, les modèles incluent décisions de dimensionnement au coté des décisions opérationnelles. Il est alors courant de modéliser le fonctionnement du système heure par heure à l'échelle d'une année : la dimension temporelle explose. Des heuristiques peuvent être utilisées en fonction de la typologie du problème. La complexité et le haut niveau d'abstraction de ces modèles questionne les compromis entre réalisme opérationnel, performances et temps de calcul.

Les récentes avancées en apprentissage profond et par renforcement ont ravivé l'intérêt d'étudier la résolution de problèmes d'Optimisation Combinatoire sous l'angle de l'apprentissage automatique. Ces approches permettent de s'affranchir de la limitante définition manuelle et explicite d'heuristiques spécifiques au problème traité, en visant à apprendre des procédures (politiques) de résolution implicite à partir d'analyses d'instances du problème. Dans cet exposé, nous nous intéressons à l'application de ce type d'approche aux problèmes de tournées de véhicules. La présentation sera axée sur les perspectives offertes par ce paradigme, les limites identifiées et les pistes de recherches étudiées dans le cadre de mes travaux de thèse. Une première approche vise à la réutilisation d'une politique de résolution d'un problème à un autre, via l'apprentissage par transfert est présentée. Dans un second temps, un nouvel algorithme de résolution hybridant apprentissage par renforcement et un oracle exacte à base de programmation dynamique est introduit avec un cas d'étude sur le problème de tournées de véhicules avec contrainte de capacité.

LocalSolver est un solveur global qui combine des techniques exactes et heuristiques. Un élément différenciant du solveur est l'existence de variables ensemblistes qui permettent de modéliser facilement les problèmes d'ordonnancement disjonctifs en représentant la liste ordonnée des tâches à effectuer sur une machine. LocalSolver 11.5 introduit des techniques dédiées pour la recherche de solutions en ordonnancement : heuristiques constructives, recherche locale couplée à de la propagation ainsi que des techniques pour le calcul de bornes : Simple Temporal Network et reformulation en PLNE. Ce séminaire fera un tour des techniques utilisées par LocalSolver et illustrera les résultats obtenus avec des benchmarks de la littérature.

Créée en 2003, Probayes (www.probayes.com) est une société issue d'un essaimage de plusieurs laboratoires français de renommée internationale (CNRS, INRIA, UJF) dans le but de devenir un des principaux acteurs du développement logiciel et de conseil dans les domaines de la modélisation bayésienne, l'apprentissage automatique (de l'anglais "machine learning"), l'inférence statistique et l'aide à la décision (optimisation). Dans ce Midi ROSP, nous présenterons l'équipe Recherche Opérationnelle de Probayes ainsi que différents projets réalisés par l'équipe. Nous nous concentrerons sur deux projets actuels : un projet de planification d'arrimage et un projet de planification de ressources humaines. Nous terminerons par des bonnes pratiques de développement mises en place pour les projets de RO.

Dans cette présentation nous verrons un panorama des différents sujets traités par l'équipe de recherche opérationnelle de la R&D d'EDF avant de rentrer plus en détails sur deux sujets liés aux problèmes de gestion du parc nucléaire. Le premier concerne l'optimisation du planning d'arrêts pour entretien et rechargement des réacteurs nucléaires. Il consiste à déterminer un planning respectant les contraintes de fonctionnement des réacteurs nucléaires et les contraintes de ressources limitant le nombre d'arrêts en parallèles. Ce problème présente des aspects stochastiques, incertitude sur la disponibilité des réacteurs et sur la structure de l'équilibre offre/demande futur, sur lesquels travaille notre équipe adapter la prise en compte de ces aspects à l'horizon d'optimisation considéré. Le second concerne la planification des chantiers de prolongation de la durée de vie des réacteurs nucléaires. Ces grands chantiers peuvent être modélisés par un problème d'ordonnancement sous contraintes de ressources (RCPSP) dans lequel les durées des tâches et la disponibilité des ressources sont incertaines. Notre équipe travaille en collaboration avec des académiques sur le développement de méthodes robustes permettant d'assurer la date de début de certaines tâches afin de fiabiliser les plannings industriels.

Pour aborder les fêtes avec légèreté, nous discuterons d'un casse-tête numérique et logique connu sous le nom de cryptarithme. Il consiste en une équation mathématique où les lettres représentent des chiffres distincts à trouver. L'exemple le plus connu est l'équation SEND+MORE=MONEY dont la solution est 9567+1085=10652. Ce problème combinatoire est classique pour l'enseignement des mathématiques et de l'informatique depuis l'école primaire jusqu'à l'université. Il est réputé facile en décimal même s'il est NP-complet pour une base quelconque. Cependant, cette réputation est exagérée, car les approches classiques sont limitées et il n'existe aucun logiciel qui les résout efficacement. Nos travaux en cours visent leur résolution efficace, mais surtout la génération de nouveaux cryptarithmes qui constitue un véritable défi. Nous terminerons sur quelques perspectives de diffusion et médiation scientifique.
 

Dans cet exposé, je présenterai mes travaux liés à l'analyse statistique de données temporelles. L'objectif est, à partir d'une représentation dans une base  fonctionnelle, d'extraire la structure  des données,  ou de  la  prendre  en  compte dans le développement de procédures statistiques  (estimation  de densité, régression, classification). Je distinguerai deux axes d'analyse. Le premier axe considère que les données présentent de la régularité et cherche  à exploiter celle - ci pour extraire de manière concise l'information. Le second axe cherche à modéliser la dépendance temporelle sous forme de séries temporelles. Ce travail est principalement motivé par une application en neuroscience, où des séries temporelles mesurant l'activité cérébrale sont associées à des régions cérébrales. Ces données présentent des dépendances temporelles dites à longue mémoire. L'objectif du travail mené est de  proposer l'inférence de ces propriétés de mémoire,  ainsi que de la connectivité fractale, c'est-à-dire des corrélations spatiales entre les activités des différentes régions cérébrales.
 

Primal-dual is an elegant and powerful method in optimization, operations research, and algorithm design. The method consists of interactively constructing primal and dual solutions, then an algorithm and its analysis are guided naturally by the primal-dual interaction. In this talk, I will present a primal-dual approach as a unified technique for developing algorithms and establishing performance guarantees in the different fields when the nature is non-linear.
 

Les systèmes sont nécessaires au fonctionnement de notre société. Ils sont présents dans tous les secteurs et aspects de notre vie. Les systèmes se dégradent avec l'âge et l'utilisation. Une défaillance de certains systèmes complexes critiques peut avoir des conséquences dramatiques sur la sûreté et la sécurité. De plus, des pertes économiques et des dommages environnementaux peuvent être encourus. En raison de la nature du comportement vieillissant des systèmes, une stratégie de maintenance adaptée doit être conçue et appliquée pour réduire le risque de défaillances. Les compagnies sont de plus en plus conscientes de l'importance de la gestion de la maintenance des actifs. La plupart d'entre elles sous-traitent cette fonction à des sociétés spécialisées en raison de leurs compréhension de la complexité de sa gestion et de son exécution. C'est également l'opportunité pour eux de se concentrer sur leur cœur de métier. Le fournisseur des services de maintenance vise à fournir des approches efficientes pour gérer la maintenance grâce à une planification continue pour obtenir les meilleurs résultats au moindre coût. Il doit également s'assurer de la gestion du transport pour effectuer la maintenance pour ses différents clients. Cette thèse s'intéresse à la planification conjointe de la maintenance et des tournées des techniciens. Ce problème consiste à définir le routage des techniciens pour effectuer les opérations de maintenance au bon moment sur des installations géographiquement distribuées et sujettes à des défaillances aléatoires. Premièrement un modèle mathématique a été proposé pour l'intégration du problème de la planification de la maintenance avec le routage des techniciens. Le modèle détermine simultanément le plan de maintenance et de routage optimal. Trois fonctions objectifs qui intègrent à la fois des considérations de défaillance, de maintenance et de routage ont été proposées. Des heuristiques constructives basées sur le comportement de la défaillance et de la maintenance ont été conçus pour générer des solutions initiales suivies d'une métaheuristique de recherche à voisinage variable pour la résolution du problème. Ensuite, des algorithmes multi-objectifs basée sur la descente à voisinage variable, la recherche générale à voisinage variable et la dominance de Pareto ont été proposés pour traiter le problème bi- objectifs où chaque objectif de maintenance est associé avec l'objectif du routage. Les nouveaux mécanismes utilisés sont détaillés notamment la méthode d'amélioration, la méthode d'exploration de voisinage, le critère d'acceptation, le critère d'arrêt et la procédure de changement de voisinage. Troisièmement, une extension du problème précédent intégrant la maintenance opportuniste a été proposée. Ce nouveau problème considère l'existence des fenêtres d'arrêt de production programmés comme une contrainte à prendre en compte. Le problème intégrant les pertes possibles de production a été modélisé et résolu à l'aide d'une recherche adaptative à voisinage large qui intègre une heuristique dédiée et des opérateurs spécifiques. Finalement, la variante bi-objectifs du problème a été modélisée et traitée. Les objectifs de minimisation du coût de routage, de maintenance, des pénalités de non-respect des intervalles de maintenance, et de pertes en production ont été considérés. Des algorithmes multi-objectifs intégrant de nouveaux mécanismes et basés sur la recherche locale de Pareto, la recherche adaptative à voisinage large et la dominance de Pareto ont été proposés. La performance des modèles et des algorithmes proposés a été évaluée à l'aide de plusieurs instances générées. Les algorithmes surpassent le solveur commercial et des algorithmes de la littérature.
 

Ce séminaire est un entrainement pour un cours à des élèves ingénieurs (bac+4) dans une UE de RO avancée. L'objectif est de proposer une refléxion sur comment mettre en œuvre un algorithme d'aide à la décision (qui fonctionne et qui est utilisé) en étant conscient/sensibilisé/averti (aware) sur les conflits et enjeux éthiques ? Après une rapide présentation sur ce qu'est le questionnement éthique et comment il s'instancie en recherche opérationnelle, nous traiterons une étude de cas. Le cadre considéré est :

L'application considérée est la cas d'un logiciel d'aide à la navigation connecté (type Waze) :service qui propose des alternatives de plus court chemin entre une origine et une destination pour des utilisateurs motorisés. N'hésitez pas à réfléchir et à vous documenter avant le séminaire. Vous devrez proposer des pistes de réflexions que nous approfondirons. Nous traiterons en particulier: 1. Conception de l'outil qui maximise l'utilité de chaque individu 2. Questions posées par cette solution pour les différentes parties prenantes.

La recherche opérationnelle a permis depuis des décennies de nombreuses avancées dans la construction d'outils de gestion et de planification des emplois du temps scolaires, sportifs, mais aussi pour beaucoup de professionnels. Sur un autre versant pourtant, les sciences humaines et sociales font état de vastes effets délétères sur les individus et les collectifs de travail, de ce que l'on peut nommer le management algorithmique. A l'heure où l'éthique des algorithmes est si largement discutée, la planification de personnel constitue donc un point de croisement privilégié pour étudier les enjeux soulevés et tenter de proposer d'autres approches. L'écoute des différentes parties prenantes en fait émerger une importante variété sans épuiser les pistes de réflexion, dont on ébauchera un panorama.

Cette présentation aura pour objet de présenter les grands enjeux du système énergétique français, en se focalisant sur l'effet que pourrait avoir le déploiement massif des énergies renouvelables intermittentes (PV et éolien) en France. Nous nous intéresserons tout particulièrement au potentiel des moyens de stockage d'énergie (électricité et chaleur) pour répondre au besoin dit 'de flexibilité' du système électrique, pour mettre en phase la demande et la production. Nous dresserons tout d'abord le panorama des principales méthodologies mathématiques qui permettent d'aborder cette question, avant de présenter une approche qui se focalise sur les différentes échelles de temps du système électrique et du stockage - des fluctuations journalières, hebdomadaires à la variabilité saisonnière. Les méthodologies présentées sont basées sur des optimisation en programmation linéaires et des décompositions mathématique en ondelettes.
 

Le problème des ordonnancements collectifs consiste à ordonnancer un ensemble de n tâches commune à un ensemble de v individus, aussi appelés agents, chacun ayant des préférences sur l'exécution de ces tâches. Les tâches peuvent représenter des travaux publics, des présentations dans une conférence ou même les étapes d'un projet partagés par des collègues ou les membres d'une association. On considérera que les tâches ont toutes la même durée. Le but du problème est alors de trouver un ordonnancement des n tâches sur une machine et satisfaisant les agents le plus possible. On étudie deux algorithmes retournant une solution minimisant deux critères, chacun généralisant un critère classique en ordonnancement : un critère de distance et un critère dit ``binaire". On s'intéresse à des contraintes classiques en ordonnancement : les dates de disponibilité, les deadlines et les contraintes de précédence. On considérera deux contextes, un dans lequel les préférences respectent ces contraintes et un dans lequel elles ne les respectent pas. Dans ces deux cas, le but est d'étudier la complexité et les propriétés mathématiques des algorithmes. Finalement, on étudie une heuristique pour un cas particulier de notre problème en terme d'approximation pour le critère de distance et de propagation des contraintes depuis un ensemble de préférences vers la solution retournée.