Journées ROC 2022

Présentation des sujets de stages 2024 de l'équipe

Animation scientifique 2024

Année 2023

[Décembre 2023] Bienvenue à Cyrille Equoy, doctorant ROC

Cyrille Equoy débute une thèse sur la conception de méthodes de Recherche Opérationnelle pour des problèmes de vision à large échelle. Il est encadré par Cyril Briand (ROC) et Frédéric Lerasle (RAP). Sa thèse est financée par une allocation ministérielle.

Cyrille est titulaire d’un diplôme Master de l’Université Paul Sabatier, parcours SIA (Signal, Imagerie et Applications). Il a trois ans d’expérience d’ingénieur d’études dans l’équipe RAP pour le développement de méthodes de deep learning pour du traitement d’images.

[11/12/2023] Soutenance de la thèse de Louis Rivière

Louis a soutenu sa thèse intitulée Représentation compacte d’ensemble de solutions pour l’ordonnancement sous incertitude. Le jury était composé de : 

• DIRECTEURS DE THESE : Christian Artigues, Directeur de recherche, CNRS Toulouse - LAAS et Hélène Fargier, Directrice de recherche, CNRS Toulouse - IRIT
• RAPPORTEURS : Antoine Jouglet, Professeur des universités, Université de Technologie de Compiègne et Pierre Marquis, Professeur des universités, Université d'Artois
• EXAMINATEURS : Jean-Charles Billaut, Professeur des universités, Université de Tours et Marie Pelleau, Maîtresse de conférences, Université Côte d'Azur

Résumé : L'objectif de cette thèse est l'étude de méthodes permettant la prise en compte d'incertitude dans des problèmes d'ordonnancements à l'aide de structures de données représentant un ensemble de solutions de façon compacte.

La première partie de cette thèse présente les problèmes d'ordonnancement sous incertitude, et introduit les méthodes de résolution dont nous ferons usage dans cette thèse. La seconde partie s'intéresse à des problèmes d'ordonnancement à une machine et des problèmes de jobshop, où l'incertitude porte sur les dates de disponibilité des tâches ou sur leurs durées. L'incertitude est modélisée par un ensemble de scénarios discrets, et nous supposons un modèle d'information minimaliste, dans lequel l'incertitude est levée lors du fait accompli. Nous considérons des objectifs stochastiques et robustes pour plusieurs critères réguliers, que nous utilisons pour guider la recherche de solution dans une phase hors-ligne, sur un ensemble de scénario d'entraînement; puis nous évaluons ces solutions sur un ensemble de scénarios de test dans une p! hase en ligne. Nous nous intéressons particulièrement aux différent types de décisions partielles qui peuvent être prises lors de la phase hors-ligne, telles que l'heuristique "First-in First-out", guidée par les informations révélées lors de la phase en ligne, complète la décision pour obtenir un ordonnancement. Les décisions partielles que nous considérons restreignent l'espace des solutions à des ensembles de séquences de tâches. Ces ensembles sont décrits par des structures de données comme les simples séquences (comme dans la littérature en ordonnancement stochastique ou robuste), des séquences de groupes d'opérations permutables, ou des diagrammes de décision multivalués. Nous proposons plusieurs méthodes pour prendre la meilleure décision partielle hors-ligne étant donnée la décision heuristique en ligne et le type de structure considérée. Des expérimentations évaluent les différentes approches selon les objectifs et les paramètres ! des instances considérées et montrent l’intérêt des nouvelles approches proposées.

Enfin, la troisième partie vise à formaliser l'étude, à la lumière du formalisme de la compilation de connaissance, des différentes structures utilisées (appelées langages de représentation dans ce contexte). Dans cette partie, nous considérons une variante décisionnelle d'un problème d'ordonnancement à une machine. L'incertitude n'y est pas modélisée explicitement, mais l'objectif est de déterminer, en fonction des structures de données utilisées pour représenter l’ensemble des solutions du problème, quels aléas il est possible de prendre en compte, par exemple en remettant à jour rapidement l’ensemble des solutions face à un aléa. L'objectif étant de calculer dans une phase hors-ligne une représentation du problème, qui serve d'outil à un décideur et permette la prise en compte d'un maximum d'aléas lors de la phase en ligne. Différents langages qui représentent le problème par un e! nsemble de séquences de tâches correspondant à des solutions admissibles sont considérés (parmi lesquels les structures de données de la seconde partie). Les langages sont comparés selon des critères d'expressivité, de compacité, et en fonction des requêtes qu'ils supportent. Les résultats établis permettent de dresser une carte de compilation des langages étudiés et de guider un utilisateur dans le choix d'un langage de représentation. Les résultats de l'étude menée dans cette thèse montrent expérimentalement que le calcul de solution en amont est très difficile, mais utiliser des départs à chaud semble prometteur. Les résultats théoriques permettent de comparer plusieurs langages, mais n'identifient pas de candidat pleinement satisfaisant pour le problème considéré. Enfin, les résultats suggèrent de nombreuses pistes de travail futures, en particulier à l'intersection des domaines de l'ordonnancement et de la compilation de connaissances, q! ui sont rarement considérés conjointement.

[Novembre 2023] Bienvenue à Elouan Blanchard, doctorant ROC

Elouan Blanchard débute une thèse Cifre avec la société Alten. Son sujet porte sur l’assignation dynamique de tâches pour des flottes de robots dans un contexte industriel (approvisionnement de chaînes de production, collecte de produits, …). Il est encadré par Cyril Briand (ROC) ainsi que par Grégoire Milliez et Mohamed Amine Abdeljaouad (société Alten).

Elouan a obtenu un diplôme d’ingénieurs en 2022, spécialité Robotique, à Polytech Sorbonne. Il a travaillé pendant un an comme ingénieur chez Alten sur le développement de logiciels pour des systèmes embarqués.

[30/11/2023] Session ROC invitée - Serdar Kadioglu (Brown University)

Présentation de Serdar Kadioglu intitulée : Multi-level Optimization to Boost Experimentation in Digital Channels

Abstract: In this talk, we formalize a combinatorial optimization problem to speed up live experimentation. In digital channels across the web, mobile, and virtual agents, a large set of content is desirable to increase diversity. In contrast, a smaller set reduces the time it takes to collect training data for machine learning models. We show how to optimize for such conflicting criteria using multi-level optimization. Our approach combines techniques from discrete optimization, unsupervised clustering, and latent text embeddings. More broadly, we present a hybrid framework that shows how to integrate Optimization with NLP and modern Recommender Systems.

Bio: Serdar Kadioglu is Group VP of AI at Fidelity Investments and Adjunct Associate Professor of Computer Science at Brown University. Previously, he led the Advanced Constraint Technology group at Oracle and worked at Adobe. Dr. Kadioglu’s research is at the intersection of AI and Optimization with practical interests in building robust and scalable products while contributing to the open-source ecosystem.

[23/11/2023] Session ROC invitée - Stéphanie Roussel, chercheure à l’ONREA Toulouse

Stéphanie Roussel de l'ONERA interviendra ce jeudi 23 novembre pour une ROC session portant sur l'Optimisation de la conception préliminaire d'une ligne d'assemblage pour un avion. 

Abstract : Dans l'industrie aéronautique, chaque famille d'avions a son propre système de production. Ce système est classiquement conçu une fois que la conception de l'avion est complètement achevée, ce qui peut entraîner des performances médiocres. Pour atténuer ce problème, une stratégie consiste à prendre en compte le système de production le plus tôt possible dans le processus de conception de l'avion. Dans ce travail, nous définissons le problème de conception préliminaire de la ligne d'assemblage, qui consiste à définir, pour une conception d'avion donnée, la meilleure disposition de la ligne d'assemblage ainsi que le type et le nombre de machines équipant chaque station de travail. Nous proposons un encodage en programmation par contraintes pour ce problème, ainsi qu'un algorithme basé sur la contrainte epsilon pour explorer l'ensemble des solutions de Pareto. Nous présentons des expérimentations réalisées sur un ensemble de données industrielles réelles. Les résultats montrent que l'approche est prometteuse et permet aux experts de comparer plusieurs concepts d'avions entre eux.

[22/11/2023] Soutenance de la thèse d’Aloïs Duguet

Aloïs a soutenu sa thèse intitulée Approximation linéaire par morceaux de fonctions de deux variables avec erreur bornée pour la résolution de problèmes d'optimisation non linéaire mixte en nombres entiers. Le jury était composé de : 

• DIRECTEURS DE THESE : Sandra Ulrich NGUEVEU, Maîtresse de conférences HDR, Institut National Polytechnique de Toulouse, LAAS-CNRS
• RAPPORTEURS : Claudia D'AMBROSIO, Directrice de recherche, Laboratoire d'Informatique de l'école Polytechnique et Amélie LAMBERT, Maîtresse de conférences HDR, Conservatoire National des Arts et Métiers
• EXAMINATEURS : Mourad BAIOU, Directeur de recherche, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes et Marcel MONGEAU, Professeur, École Nationale de l'Aviation Civile

Résumé : En optimisation, de nombreuses applications académiques et industrielles se modélisent sous la forme de problèmes de la classe appelée MINLP, pour mixed-integer nonlinear programming. Les problèmes de cette classe sont généralement difficiles à résoudre en l’absence de propriétés particulières sur les fonctions non linéaires, combinée à la présence de variables de décision binaires ou entières. Une méthode classique de résolution consiste à approximer le problème en remplaçant les fonctions non linéaires par des fonctions linéaires par morceaux pour obtenir un problème MILP, pour mixed-integer linear programming. Cela permet de tirer partie de la grande efficacité des solveurs et de toutes les avancées des trente dernières années sur la résolution de programmes linéaires en nombres entiers ou mixtes. Ces approches ont pour inconvénient majeur l’absence de garantie a priori sur la qualité des solutions obtenues. Cette thèse s’inscrit dans la lignée de travaux récents visant à éliminer ce défaut. Nos travaux se focalisent sur l’approximation de fonctions non linéaires de deux variables par des fonctions linéaires par morceaux respectant une borne sur l’erreur d’approximation et minimisant le nombre de morceaux utilisés. Cela permet l’approximation de toute fonction décomposable en somme de termes dépendant de deux variables. Dans un premier temps, nous avons résolu optimalement le cas particulier de la norme euclidienne de deux variables lorsque le domaine de définition est le plan tout entier, et étendu ce résultat aux normes dont les lignes de niveaux sont des ellipses. Dans un second temps nous nous sommes intéressés aux fonctions de deux variables continues définies sur un domaine polygonal. Pour ces dernières, nous avons développé différentes méthodes permettant d’obtenir des solutions réalisables exploitant des propriétés d’approximation que nous avons identifiées, ainsi que des bornes inférieures basées sur une nouvelle famille d’inégalités valides dédiée au problème. Les expériences numériques ont montré que nos méthodes obtiennent de meilleures solutions que l’état de l’art, en particulier pour l’approximation de fonctions non linéairement séparables. Enfin, deux applications à la résolution de problèmes MINLP sont traitées pour illustrer le potentiel pratique de nos travaux, l’une sur un problème de placements de faisceaux de satellites de télécommunication et l’autre sur le calcul d’équilibres de Nash en théorie des jeux.

[02/11/2023] Session ROC invitée - Marianne Defresne, doctorante INRAE Toulouse

Marianne Defresne nous présente des travaux réalisés dans le cadre de sa thèse encadrée par THomas Schiex (INRAE) et Sophie Barbe (TBI).  Le titre de la présentation est  : "Computational Protein Design with Automated Reasoning and Deep Learning"

[26/10/2023] Session ROC invitée - Gabriel Laberge, doctorant Polytechnique Montréal

Gabriel Laberge nous présente des travaux réalisés en collaboration avec Julien Ferry.  Le titre de la présentation est  : "Les Modèles Interprétables Hybrides : Explorer le Compromis entre Transparence et Performance"

[19/10/2023] Session ROC - Camille Lescuyer

Présentation de Camille intitulée : "Computing Bounds for a Direct-To-Home beamforming problem"

[09/10/2023] Soutenance de la thèse de Julien Ferry

Julien a soutenu sa thèse intitulée Adresser l’interprétabilité, l’équité et la protection de la vie privée en apprentissage machine au travers des méthodes d’optimisation combinatoire. Le jury était composé de : 

• DIRECTEURS DE THESE : Marie-José HUGUET, Professeur des universités, INSA Toulouse et Sébastien GAMBS, Professeur, Université du Québec à Montréal
• CO-ENCADRANTS DE THESE : Mohamed SIALA, Maître de conférences, INSA Toulouse
• RAPPORTEURS : Josep DOMINGO-FERRER, Full professor, Universitat Rovira i Virgili et Pierre SCHAUS, Professeur, UCLouvain
• EXAMINATEURS : Elisa FROMONT, Professeur des universités, Université de Rennes, Mathieu SERRURIER, Maître de conférences, Université Toulouse 3 - Paul Sabatier, Thibaut VIDAL, Associate Professor, Polytechnique Montréal et Sylvie THIÉBAUX, Professor, The Australian National University
• INVITES : Ulrich AÏVODJI, Assistant professor, ÉTS Montréal

Résumé : Les approches d'apprentissage automatique sont de plus en plus utilisées pour des problématiques de prise de décisions impactant nos vies, telles que l'admission à l'université, l'attribution de prêts ou la prédiction de récidive. Ainsi, il est crucial de s'assurer que les modèles entraînés peuvent être audités et compris par leurs utilisateurs, ne reproduisent pas ni ne créent de biais discriminatoires, et ne divulguent pas d'informations sensibles sur leurs ensembles d'entraînement.  En effet, l'interprétabilité, l'équité et la protection de la vie privée sont des propriétés indispensables pour le développement de techniques d'apprentissage dignes de confiance. Toutes trois ont été largement étudiées durant la dernière décennie. Cependant, elles sont le plus souvent considérées séparément les unes des autres.

L'objectif de cette thèse est précisément de caractériser les interactions entre ces trois domaines, en utilisant des outils d'optimisation combinatoire et de recherche opérationnelle. Considérant ces trois domaines deux à deux, nous passons en revue la littérature sur leurs compatibilités, tensions et synergies. Nous nous concentrons sur certaines de ces tensions et proposons soit un mécanisme de conciliation, soit des techniques permettant de mettre en exergue ou de quantifier ce conflit.

Nous proposons d'abord une technique d'élagage basée sur la programmation linéaire en nombres entiers pour un algorithme d'apprentissage produisant des modèles équitables et intrinsèquement interprétables. En encodant conjointement précision, taille du modèle et équité, elle améliore l'exploration de l'espace de recherche de l'algorithme et aide à concilier équité et interprétabilité. Forts de la constatation expérimentale que l'équité généralise souvent mal une fois les modèles appliqués sur de nouvelles données, nous proposons une nouvelle approche visant à améliorer la robustesse de l'équité vis-à-vis de l'échantillonnage du jeu de données.

Nous montrons par la suite comment l'information relative à l'équité d'un modèle peut être utilisée pour reconstruire les attributs sensibles de son ensemble d'entraînement. A cet effet, nous proposons des modèles de programmation linéaire en nombres entiers et de programmation par contraintes encodant directement l'information de l'équité afin d'améliorer une reconstruction effectuée en amont par un attaquant quelconque de la littérature. Ce travail illustre une tension intrinsèque entre le fait d'assurer l'équité par rapport à certains attributs sensibles et la nécessité de protéger l'information relative à ces attributs.

Enfin, nous expliquons comment la structure d'un modèle interprétable peut être utilisée pour reconstruire une version probabiliste de son ensemble d'entraînement. En quantifiant précisément la quantité d'information qu'un modèle encode sur ses données d'entraînement, nous illustrons un conflit apparent entre l'interprétabilité et la protection de la vie privée.

[04/10/2023] Soutenance de la thèse de Carla Juvin

Carla a soutenu sa thèse intitulée Méthodes hybrides pour l'ordonnancement disjonctif avec flexibilité de ressources et considération de robustesse. Le jury était composé de: 

• DIRECTEURS DE THESE : Pierre LOPEZ, Directeur de recherche, LAAS-CNRS et Laurent HOUSSIN, Professeur associé, ISAE-SUPAERO
• RAPPORTEURS : Boris DETIENNE, Maître de conférences, Université de Bordeaux et Roel LEUS, Professor, KU Leuven
• EXAMINATEURS : Stéphane DAUZERE-PERES, Professeur, Ecole des Mines de Saint-Étienne et Rosa FIGUEIREDO, Maîtresse de conférences, Université d'Avignon

Résumé : Dans cette thèse, nous étudions les problèmes d'ordonnancement disjonctif, en examinant deux types spécifiques de problème : ceux impliquant la flexibilité des ressources et ceux dont la durée des tâches est entachée d'incertitude. Nous proposons des approches hybrides qui combinent différentes méthodes de résolution, exploitant ainsi les avantages de chacune d'elles.

Dans un premier temps, nous étudions le problème de job-shop flexible, un problème d'atelier qui consiste à déterminer sur quelle machine et dans quel ordre doivent être traitées les opérations. Nous proposons un schéma de décomposition du problème, ainsi qu'une méthode de décomposition de Benders basée sur la logique pour le résoudre. Nous comparons cette approche avec des méthodes de résolution basées sur des formulations directes pour les versions non préemptive et préemptive du problème.  

Dans un second temps, nous nous intéressons à plusieurs problèmes d'ordonnancement robuste dans lesquels la durée des tâches est incertaine. Nous nous concentrons sur la résolution de problèmes à deux étapes, dont l'objectif est de fixer la séquence des opérations sur chaque machine, tout en permettant aux dates de traitement des tâches de s'adapter à leurs durées effectives. Nous proposons différentes formulations directes des problèmes, ainsi que des méthodes de décomposition de Benders basées sur la logique et de génération de colonnes et de contraintes. Des résultats numériques sont présentés afin d'évaluer l’efficacité de chacune de ces méthodes.

[Octobre 2023] Bienvenue à Théo Le Brun, doctorant de l’équipe ROC

Théo démarre  une thèse CIFRE avec la société One-Stock. Son sujet porte sur  la résolution de systèmes décisionnels pour la gestion de commandes omnicanales dans un contexte de e-commerce responsable. Il est encadré par Sandra U. Ngueveu et Marie-Jo Huguet.

En 2022, Théo a obtenu un double diplôme ingénieur ENAC et master en Recherche Opérationnelle. De septembre 2022 à septembre 2023, il a été ingénieur dans l’équipe pour la chaire Retail Responsable.

[Octobre 2023] Bienvenue à Tanguy Terrien, doctorant de l’équipe ROC

Tanguy débute une thèse intitulée “aide à la décision centrée sur l’homme pour la planification dynamique d’activités dans des systèmes de production”. Sa thèse se déroule dans le cadre du projet ANR HIS3, elle est encadrée par Cyrile Briandl et Phillipe Truillet (IRIT). Tanguy est diplômé 2023 du Master ORCO de Grenoble. Il a effectué son stage de master chez Huawei sur l’implémentation d’heuristiques de recherche dans un solver PPC.

[Octobre 2023] Bienvenue à François Lamothe, post-doctorant de l’équipe ROC

François effectue un post-doc d’un an dans l’équipe dans le cadre de la chaire Retail Responsable. Il travaille avec Sandra U. Ngueveu sur des problèmes d’optimisation pour le e-commerce responsable. François a soutenu sa thèse à l’ISAE en 2021 (Le problème de flot insécable : application à la gestion des communications d'une constellation de satellites, sous la direction d’Alain Hait et d’Emmanuel Rachelson. Il a ensuite effectué un post-doc de mars 2022 à septembre 2023 avec Claudio Contardo et Matthieu Gruson sur une étude polyedrale pour un problème de set covering.

[21/09/2023] Session ROC Louis Bonnet

Présentation de Louis intitulée An exact method for the industrial single bar nesting problem.

[07/09/2023] Session ROC Damien Wojtowicz

Présentation de Damien intitulée Optimisation de requêtes en environnements multi-clouds

[6 septembre 2023 - 16 février 2024] Stage de Timothée Ly

Timothée Ly est étudiant en 3e année à Télécom Paris et en double diplôme avec l'université KTH (Suède). Il effectue un stage sur la conception et le développement de méthodes d’apprentissage interprétables et respectueuses de la vie privée. Le stage de Timothée est encadré par Marie-José Huguet et Julien Ferry. Il s’inscrit dans le cadre de collaborations scientifiques avec Sébastien Gambs (UQAM) et avec Ulrich Aivodji (ETS).

[01/09/2023] Bienvenue à Louis Bonnet, doctorant ROC

Louis Bonnet débute sa thèse financée par l’ANR AD-LIB. Son sujet traite de méthodes d’agrégation et de désagrégation de commodités pour les problèmes de conception de réseaux. Louis était auparavant ingénieur développement dans la société Top Solid. Il est ingénieur N7 en informatique et diplômé du M2RO.

[01/09/2023] (re)Bienvenue à Valentin Antuori, post-doc ROC

Valentin Antuori débute un post-doc d’un an sur le projet JAPETUS. Il travaille avec Emmanuel Hébrard et Damien Wojtowicz sur la planification d’acquisitions et de vidages d’images pour une constellation de nano-satellites.

[Septembre 2023] Carla Juvin, ATER à l’ENAC

Carla Juvin est en poste d’ATER à l’ENAC. Elle intègre l’équipe d’optimisation. Félicitations de l’équipe !

[27 - 31 août 2023] ROC à la conférence CP 2023 (Toronto, Canada)

L’équipe a participé à la conférence international CP 2023 : Principles and Practice of Constraint Programming avec la présentation de deux articles : 

• An Efficient Constraint Programming Approach for Scheduling Interruptible Tasks Requiring Disjoint Disjunctive Resources - Carla Juvin, Emmanuel Hebrard, Laurent Houssin and Pierre Lopez
• Partially Preemptive Multi Skill/Mode Resource-constrained Project Scheduling with Generalized Precedence Relations and Calendars - Guillaume Poveda, Nahum Alvarez and Christian Artigues

[23-29 juillet 2023] ROC à la conférence ICML 2023 (Hawaï)

Emmanuel Hébrard participe à ICML (International Conference on Machine Learning) pour présenter son papier : 

• Blossom: an Anytime Algorithm for Computing Optimal Decision Trees - Emir Demirović, Emmanuel Hebrard, Louis Jean

[13 juillet 2023] ROC Session invitée - Tomasz Kloda

Tomasz Kloda (équipe Vertics) a présenté ses travaux sur l’analyse d’ordonnancement et l’optimisation des systèmes temps réels

Abstract : Dans cet exposé, suite à une brève présentation des algorithmes d’ordonnancement temps réels, je voudrais aborder deux thématiques. Tout d’abord, le partitionnement de cache qui entraîne un problème d'optimisation mathématique où des segments de cache doivent être alloués aux processeurs ou aux tâches afin de satisfaire les contraintes temporelles. Ensuite, je parlerai de l’ordonnancement non préemptif des tâches parallèles (gang scheduling) sur l’exemple des unités de traitement de tenseur utilisées pour l’accélération matérielle des réseaux de neurones.

[11 juillet 2023] Journée des stagiaires de l’équipe ROC

Présentation des stagiaires de l’équipe : 

• Bryan Chen, Brenda Tonleu, Alice Devilder, Mohamed Yassine Loulou : "Tell me how you rank, I'll tell you what you like"
• Hannes Van Overloop : "Séquencement de tâches et planification de mouvements pour un robot manipulateur mobile"
• Joséphine Gobert : "Ordonnancement cyclique des tâches sur le nanosatellite NIMPH"
• Karim Terfasse : "Optimisation des tournées sans collisions de véhicules autonomes dans un port"

[10-14 juillet 2023] ROC à l’ACP Summer School (Leuven, Belgique)

Tim Lucherhand, Loïc Robert et Julien Rouzot ont partcipé à la summer school 2023 de l’ACP sur le thème : Machine Learning for Constraint Programming

[9-14 juillet 2023] ROC à la conférence IFAC Wolrd COngres (Yokohama, Japon)

L’équipe ROC a participé (en hybride) au 22nd World Congress of the International Federation of Automatic Control. Matthieu Masson présente l’article : 

• Multi-Maneuver Algorithms for Multi-Risk Collision Avoidance Via Nonconvex Quadratic Optimization - Matthieu Masson, Denis Arzelir, Mioara Joldes, Bruno Revelin JérômeThomassin.

[8-13 juillet 2023] Papier à la conférence ICAPS 2023 (Prague Czech Republic)

Un papier de l’équipe a été présenté à ICAPS (International Conference on Automated Planning and Scheduling) : 

• Fast and Robust Resource-Constrained Scheduling with Graph Neural Networks - Florent Teichteil-Königsbuch, Guillaume Povéda, Guillermo Gonzalez de Garibay Barba, Tim Luchterhand and Sylvie Thiebaux

[7-8 juillet 2023] ROC au workshop IWPSS 2023 (Prague Czech Republic)

L’équipe ROC a participé en hybride au workshop IWPSS (International Workshop on Planning and Scheduling for Space). 

• Global Constraint for scheduling data transfer in space missions - Julien Rouzot, C. Artigues, P. Garnier, E. Hébrard, P. Lopez

[7 juillet 2023] Soutenance de la thèse de Walid Khellaf

Walid a soutenu sa thèse préparée sous la responsabilité de Jacques Lamothe (Centre Génie Industriel, IMT Mines Albi) et Romain Guillaume (IRIT). L’intitulé est : Modélisation des incertitudes en horizon glissant et compilation de solutions de problèmes de lot sizing pour la planification tactique d’une chaîne logistique décentralisée. A la rentré universitaire, Walid sera en post-doc aux Mines d’Albi. Toutes les félicitations de l’équipe !

[3-7 juillet 2023] ROC aux journées PFIA 2023 (Strasbourg, France)

L’équipe ROC a participé aux journées de la Plate-Forme Intelligence Artificielle (PFIA) en contribuant aux conférences : 

• JFPC (3 au 5 juillet 2023) : Julien Rouzot a présenté l’article : Une contrainte globale pour l’ordonnancement des transferts de données dans les missions spatiales - Julien Rouzot, Christian Artigues, Philippe Garnier, Emmanuel Hebrard and Pierre Lopez :
• RJCIA (6 et 7 juillet 2023) : Julien Ferry a présenté l’article : Exploiter l'équité d'un modèle d'apprentissage pour reconstruire les attributs sensibles de son ensemble d'entraînement. Julien Ferry, Ulrich Aïvodji, Sébastien Gambs, Marie-José Huguet and Mohamed Siala

[22 juin 2023]  Séminaire ROC - Axel Parmentier

Axel Parmentier est chercheur au CERMICS et maître de conférences à l’Ecole des Ponts depuis 2016. Il est également le fondateur d’une chaire en intelligence artificielle pour le transport aérien en collaboration avec la société Air-France. https://axelparmentier.github.io/

Son exposé s’intitule : “Learning with combinatorial optimization layers and applications to dynamic vehicle routing”.

Résumé : Combinatorial optimization (CO) layers in machine learning (ML) pipelines are a powerful tool to tackle data-driven decision tasks, but they come with two main challenges. First, the solution of a CO problem often behaves as a piecewise constant function of its objective parameters. Given that ML pipelines are typically trained using stochastic gradient descent, the absence of slope information is very detrimental. Second, standard ML losses do not work well in combinatorial settings. A growing body of research addresses these challenges through diverse methods. Unfortunately, the lack of well-maintained implementations slows down the adoption of CO layers.

Building upon previous works, we introduce a probabilistic perspective on CO layers, which lends itself naturally to approximate differentiation and the construction of structured losses. We recover many approaches from the literature as special cases, and we also derive new ones.

Based on this unifying perspective, we present InferOpt.jl, an open-source Julia package that 1) allows turning any CO oracle with a linear objective into a differentiable layer, and 2) defines adequate losses to train pipelines containing such layers.

Our library works with arbitrary optimization algorithms, and it is fully compatible with Julia's ML ecosystem. In the second part of the talk, we focus on the dynamic vehicle routing problem of the  2022 EURO-NeurIPS challenge https://euro-neurips-vrp-2022.challenges.ortec.com/

[15 juin 2023]  ROC Session invitée - Juan Cortes

Juan Cortes (équipe RIS) présente une synthèse de ses travaux en “Algorithmics of Motion. From Robotics Through Structural Biology Toward Atomic-Scale CAD”.

[8 juin 2023]  Séminaire ROC et Département DO - Thibaut Vidal

Thibaut Vidal est professeur au département de Mathématiques et Ingénierie Industrielle. Il est titulaire de la chaire SCALE-AI Chair traitant de gestion logistique guidées par les données. polymtl.ca/expertises/en/vidal-thibaut/

Son séminaire s’intitule “Explainable Machine Learning and Stochastic Optimization: From Context to Decision and Back Again”.

Résumé : Contextual stochastic optimization combines auxiliary information and machine learning to solve problems subject to uncertainty. While this integrated approach can improve performance, it leads to complex decision pipelines that lack transparency. Yet, practitioners need to understand and trust new solutions in order to replace an existing policy. To explain the solutions of contextual stochastic problems, we revisit the concept of counterfactual explanations introduced in the classification setting. We identify minimum changes in the features of the context that lead to a change in the optimal decisions. We formalize the explanation problem and develop mixed-integer linear models to find optimal explanations of decisions obtained through random forests and nearest-neighbor predictors. We apply our approach to selected operations research problems, such as inventory management and routing, and show the value of the explanations obtained.

https://arxiv.org/abs/2301.10074 - International Conference on Machine Learning ICML 2023 (July 23rd - July 29th)

[05 juin - 04 août 2023] Stage de Bryan Chen, Alice Devilder, Branda Tonleu et Mohamed Yassine Loulou 

Bryan Chen, Alice Devilder et Brenda Tonleu sont étudiants en 2e année à l’N7 (Toulouse), dans le département Sciences du Numérique, filière HPC eet Big Data. Mohamed Yassine Loulou est étudiant en 2e année à l’ENSTA (Palaiseau) en filière Mathématiques Appliquées (le stage de Yassine est du 1er juin au 17 août). Ils travaillent sur différentes approches pour approximer une fonction objectif par la résolution interactive de problèmes d'optimisation combinatoire.  Leurs stages sont encadrés par Mohamed Siala.

[29 mai - 1er juin 2023] ROC à la conférence CPAIOR 2023 (Nice, France)

L’équipe ROC participe à la 20th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR). Carla Juvin a présenté l’article : 

• Constraint Programming for the Robust Two-machine Flow-shop Scheduling Problem with Budgeted Uncertainty - Carla Juvin, Laurent Houssin and Pierre Lopez

[27 mai - 04 septembre 2023] Stage de Joséphine Gobert

Joséphine Gobert est étudiante en 2e année à l’ENAC (Toulouse) dans la filière Opérations Aériennes et Sécurité. Son stage porte sur la résolution de problèmes d'ordonnancement de tâches sur un nano-satellite. Elle est encadrée par Pierre Lopez et son travail s’intègre avc celui de la thèse de Julien Rouzot.

[25 mai - 1er Juin 2023] Séjour invité de Sébastien Gambs, Professeur UQAM

Sébastien Gambs est professeur à l’Université du Québec à Montréal (Québec, Canada). Il est titulaire d’une chaire canadienne de recherche en “Privacy-preserving and Ethical Analysis of Big Data”. Sébastien est codirecteur de la thèse de Julien Ferry. Son séjour est financé par le projet PRIMAL (LabeX CIMI).

[25 mai et 1er juin 2023]  ROC Session - Tim Luchterhand et Emmanuel Hébrard

Tim Luchterhand nous présentera "Modern C++ best practices and a short introduction to git" dans cette ROC session orientée outils dev. 

Emmanuel Hebrard nous (re)-présentera rapidement l'outil ROC'n'run qui permet de lancer facilement des expériences sur la plateforme de calcul du LAAS.

[11 mai - 25 Juin 2023] Séjour invité de Thibaut Vidal, Professeur invité LabeX CIMI

Thibaut Vidal est professeur au département de Mathématiques et Ingénierie Industrielle. Il est titulaire de la chaire SCALE-AI Chair traitant de gestion de chaïnes logistiques guidées par les données.http://polymtl.ca/expertises/en/vidal-thibaut/

Thibaut réalise un séjour scientifique dans l’équipe sur le développement de méthodes de RO pour la conception d’attaques par inférence contre des modèles d’apprentissage automatique. Son séjour est financé par le LabeX CIMI (Université de Toulouse).

[11 mai 2023]  ROC Session - Laurent Houssin

Laurent Houssin nous parlera de l'algorithme d'Howard pour l'ordonnancement cyclique.

Les slides des présentations des ROC sessions sont disponibles dans le dossier partagé ROC session de l'outil laas-cnrs partage (accès limité). Vous pouvez le trouver en suivant ce lien : https://partage.laas.fr/index.php/apps/files/?dir=/ROC-Partage/ROC-Sessions&fileid=956543 

[Mai 2023] Bienvenue à Damien Wojtowicz, post-doctorant de l’équipe ROC

Damien Wojtowicz, docteur 2023 de l'Université Paul Sabatier à Toulouse, démarre un post-doc dans l’équipe pour une durée de 1 an. Il travaille avec Emmanuel Hébard pour le projet JAPETUS sur la résolution de problèmes de planification réactive pour une constellation de nano-satellites. La thèse de Damien s’intitule “Optimisation de requêtes en environnements multi-clouds”.

[11-13 avril 2023]  Workshop du Département DO

Le workshop du département DO s'est déroulé à Albi avec des présentations des 4 équipes du département. Pour ROC, il s'agit de :

• Laurent Houssin : Hybrid methods for a robust scheduling problem
• Matthieu Masson : Fast and reliable computation of the instantaneous orbital collision probability
• Emmanuel Hebrard : Tree Search for Combinatorial Problems
• Tim Luchterhand : Applications of Graph Neural Networks for solving Resource Constrained Project Scheduling Problems

[3 avril - 15 septembre 2023] Stage de Hannes Van Overloop

Hannes Van Overloop est étudiant en 3e année à l’Ecole des Ponts (Marne la Vallée) dans la filière Ingénieur Mathématique et Informatique. Son stage porte sur  le séquencement de tâches couplé à la planification de mouvements d’un robot. Il est co-encadré par Florent Lamiraux (équipe Gepetto) ainsi que Cyril Briand et Christian Artigues (équipe ROC).

[3 avril - 18 août 2023] Stage de Amel  Farah Benzeghimi

Amel Farah Benzeghimi est étudiant en M2 à Montpellier (en informatique Théorique, Algorithmique). Elle effectue un stage avec Mohamed Siala pour approximer une fonction objectif par la résolution interactive de problèmes d'optimisation combinatoire. Elle s’intéresse plus précisément aux heuristiques de choix de variables et de valeurs dans les solveurs PPC en lien avec interaction avec les classements de solutions donnés par un utilisateur.

[Avril 2023] Thèse CIFRE de Liantsoa-O. Randriambololona (TBI / LAAS-ROC)

Liantsoa O-Randriambololona a débuté sa thèse CIFRE avec la société Solvay dans le cade d'une collaboration entre TBI (Arnaud Cocks) et l'équipe ROC du LAAS (Marie-Jo Huguet). Le sujet de la thèse est “Approche duale modélisation Multiphysique d’un procédé industriel et Apprentissage Machine”. Liantsoa est ingénieure INSA en Génie des procédés : eau, énergie et environnement, spécialité énergie.

[Avril 2023] Thèse CIFRE de Loïc Robert (TSF/ROC)

Loïc Robert, Ingénieur Informatique et Réseaux de l’INSA de Toulouse démarre sa thèse CIFRE intitulée “Nouvelles méthodes et outils semi-automatiques pour l’évaluation de la sécurité des systèmes avioniques fondés sur des approches formelles et de l'IA” en partenariat avec Airbus. La thèse est co-encadrée par l’équipe TSF (Vincent Nicomette) et l’équipe ROC (Emmanuel Hébrard et Marie-José Huguet).

[16 mars 2023]  ROC Session invitée - François Clautiaux

Cette session ROC sera dédiée au premier séminaire en commun avec Bordeaux en lien avec le projet ANR ADLIb. François Clautiaux (IMB, Institut de Mathématiques de Bordeaux) nous parlera de Synergies between dynamic programming and mixed integer programming. Voilà un résumé : In this talk, we describe the strong relationship between mixed-integer programming (MIP) and dynamic programming (DP). We show two case studies. In the first one (a variant of knapsack problem) valid inequalities are used to improve a method based on DP. In the second one (a variant of vehicle routing problem) a DP is used to produce a stronger MIP formulation, which is solved using an iterative method inspired from techniques used for DP

[06 mars - 05 septembre 2023] Stage de Karim Terfasse 

Karim Terfasse, étudiant du M2 RO, effectue un stage dans l’équipe. Il s’intéresse à la résolution du problème de calcul de chemins sans collision pour des véhicules autonomes et va développer des modèles de PLNE ainsi que des méthodes approchées.  Ses encadrants sont Ghassen Chérif et Marie-José Huguet.

[2 mars 2023]  ROC Session brainstorming - Louis Rivière

Louis nous propose une session brainstorming "Diagramme de décision multi-valué comme solution à deux étages pour des problèmes d'ordonnancement"

[20-23 Février 2023] ROC à la conférence ROADEF (Rennes)

Participation de 14 personnes de l’équipe aux journées de la ROADEF à Rennes auxquelles s’ajoutent Laurent, Simon et Jean-Charles. On y a retrouvé d’anciens stagiaires, doctorants ou post-doctorants (Stéphane, Yasemin, Catherine, Gilles, Murat, Sébastien, Yacine, Oliver, Léa, Jean-Thomas, Mikael, Estèle, Tom, Hugo, Alexandre, Léonie). L’équipe a contribué à 11 présentations et a animé des sessions.

[8-10 Février 2023] ROC à la conférence SaTML 23 (Raleigh, North Carolina, USA)

Julien Ferry participe à la conférence internationale IEEE Conference on Secure and Trustworthy Machine Learning pour y présenter l’article : 

• Exploiting Fairness to Enhance Sensitive Attributes Reconstruction - Julien Ferry, Ulrich Aïvodji, Sebastien Gambs, Marie-José Huguet and Mohamed Siala

[7-14 Février 2023] ROC à la conférence AAAI 23 (Washington DC, USA)

Mohamed Siala participe à la conférence internationale AAAI (Association for the Advancement of Artificial Intelligence). Il présente l’article “Improving Fairness Generalization Through a Sample-Robust Optimization Method” - Julien Ferry, Ulrich Aïvodji, Sebastien Gambs, Marie-José Huguet and Mohamed Siala, publié dans Machine Learning (2022) dans la session “Journal Track”. 

L’article MurTree: Optimal Decision Trees via Dynamic Programming and Search - Emir Demirović, Anna Lukina, Emmanuel Hebrard, Jeffrey Chan, James Bailey, Christopher Leckie, Rao Kotagiri and Peter J. Stuckey publié dans Journal of Machine Learning Research sera également présenté lors de cette session “Journal Track”.

Mohamed participe également au Bridge Program on Constraint Programming and Machine Learning pour y présenter ce même travail.

[Février 2023] Bienvenue à Jean-Charles Billaut, chercheur affilié, équipe ROC 

Jean-Charles Billlaut, professeur à l’Université de Tours, est chercheur affilié dans l’équipe. Jean-Charles travaille sur la résolution de problèmes d’ordonnancement et de tournées.

[26 janvier 2023] ROC Session invitée - Arthur Bit-Monnot

Arthur Bit-Monnot, équipe RIS, a présenté un exposé sur le thème Explanation-based Search for Disjunctive Scheduling

Disjunctive scheduling problems such as the jobshop and openshop are at the heart of many real world scheduling instances as well as a key subproblem in AI temporal planning. In this paper, we frame such problems as disjunctive temporal networks associated with a makespan minimization objective. For those, we propose an hybrid approach between SMT and CP solvers. In particular, we keep from SMT solvers the aggregated constraint propagation in decision procedures as well as the explanations and clause learning mechanisms upon conflict. However, like all CP solvers, we maintain an explicit domain representation of integer variables, tightly integrated with clause learning. Automated search exploits explanations to derive activity-based heuristics combined with more classical value-based heuristic of CP solvers. The resulting solver is compared to state-of-the-art exhaustive search solvers on the classical benchmarks for jobshop and openshop problems.

[09-11 Janvier 2023] ROC à la conférence ICIEA-EU (Rome, Italie)

Ghassen Cherif participe à la 10th International Conference on Industrial Engineering and Applications (Europe)(ICIEA 2023) pour y présenter l’article : 

• Modelling and optimization approaches for advanced manufacturing systems - Ghassen Cherif and Dimitri Lefebvre.

[7 janvier - 7 Février 2023] Séjour en mobilité de Louis Rivière à la Carnegie Mellon University (Pittsburgh, Etats-Unis)

Louis Rivière effectue une mobilité à la Tepper School of Business de Carnegie Mellon University à Pittsburgh (Etats-Unis) pour travailler avec Willem Van Hoeve. Le séjour sera consacré à sur la résolution de problèmes d’ordonnancement sous incertitudes en utilisant les diagrammes de décision.

[2 janvier 2023] Emmanuel Hébrard devient responsable de l'équipe ROC

Toutes nos félicitations Emmanuel !