Biographie du Professeur Alain Quilliot

Alain Quilliot, 68 ans, marié, 2 enfants : Manuel (39 ans) et Daniel (36 ans).

Professeur Emérite à l’Université Clermont-Auvergne (ex Blaise Pascal), rattaché au Laboratoire LIMOS CNRS/UCA, UMR 6158.

A contribué à l’animation du GDR Recherche Opérationnelle 5002 du CNRS, INS2I, de 2005 à 2020. S’est intéressé, au plan scientifique, à la Théorie des Graphes, à la Théorie des Jeux, aux Mathématiques pour l’Economie, à l’Intelligence Artificielle (logique, générations de plans, raisonnement automatique), et à la Recherche Opérationnelle.

Thème de la journée

Le laboratoire LIMOS organise le jeudi 13 octobre une journée scientifique, à l'occasion du départ à la retraite d'Alain Quilliot, professeur à l'Université Clermont Auvergne.

Les exposés seront donnés par des spécialistes de la Recherche Opérationnelle et de l’Algorithmique. Les thèmes abordés sont en lien avec la riche carrière scientifique d’Alain : théorie des jeux, optimisation combinatoire, réseaux, ordonnancement, modélisation, programmation mathématique, algorithmique. Cette journée permettra de faire un tour d’horizon de la recherche opérationnelle. Elle est ouverte à toutes les personnes intéressées par ce domaine.

L’inscription est gratuite mais obligatoire pour des raisons logistiques (inscription à la fin de cette page).

Programme

Planning détaillé de la journée

La conférence se déroule en Amphi 1 du Pôle Commun ISIMA / Polytech (rez-de-chaussée).

9h00 - 9h25 Accueil : café / croissants – Cafétéria du Pôle Commun (entrée face à l'ISIMA)
9h30 - 9h55 Mourad BAIOU, directeur du LIMOS : Présentation de la journée
10h00 - 10h45 Philippe CHRETIENNE : Solutions Ancrées en Optimisation Robuste
10h45 - 11h30 Michel HABIB : Routages de voiliers une approche issue de la géométrie algorithmique
11h30 - 12h15 Jean-Charles BILLAUT : Production de chimiothérapies à Tours. Où en sommes-nous ?
12h20 - 14h00 Buffet
14h05 - 14h50 Ridha MAHJOUB : Le problème de ramassage et livraison préemptif
14h55 - 15h40 Yan GERARD : Les heuristiques géométriques des Shadoks (*)
15h40 - 16h00 Pause café
16h00 - 16h45 Jacques CARLIER : Constructive and destructive bounds for the m-machine scheduling problem
16h45 - 17h30 Aziz MOUKRIM : Problèmes de tournées sélectives
17h30 - 18h Clôture
(*) Nous accueillons des lycéens pour cet exposé dans le cadre de la fête de la science.

Résumé des exposés

Conférencier : Jean-Charles BILLAUT (LIFAT, Université de Tours)
Titre et résumé de l'exposé : "Production de chimiothérapies à Tours. Où en sommes-nous ?"

Conférencier : Jacques CARLIER (Laboratoire Heudiasyc, Université de Technologie de Compiègne)
Titre et résumé de l'exposé : Constructive and destructive bounds for the m-machine scheduling problem
Joint work with Abderrahim Sahli (Laboratoire d'Informatique Gaspard-Monge, Université Paris-Est), Antoine Jouglet (Heudiasyc) and Eric Pinson (LARIS, Université Bretagne Loire)

The aim of this talk is to present some new results on constructive and destructive bounds for the m-machine scheduling problem. Recently we have characterized mathematically the three main constructive bounds which are the preemptive bound, the energetic bound and the JPPS makespan. These characterizations give insights to their similarities and differences. It explains why these bounds are generally equal in practice. Moreover our characterization of the energetic bound permits to build a 0(n alpha(n) logn) ( alpha(n Ackermann coefficient) checker. It is the best one in theory and in practice in literature, as it is confirmed by the numerical results we report.

Conférencier : Philippe CHRETIENNE (LIP6, Sorbonne Université)
Titre et résumé de l'exposé : Solutions Ancrées en Optimisation Robuste

Cet exposé rappellera les principes de l’Optimisation Robuste et situera la problématique de l’Ancrage dans cet environnement. On présentera les résultats récents obtenus pour le problème PERT qui en fournissent une application pertinente. On terminera en évoquant le caractère générique de l’approche en Optimisation Combinatoire.  

Conférencier : Yan GERARD (LIMOS, Université Clermont-Auvergne)
Titre et résumé de l'exposé : Les heuristiques géométriques des Shadoks (Les Shadoks : Loïc Crombez, Guilherme Da Fonseca, Aldo Gonzales-Lorenzo et Yan Gerard, plus Pascal Lafourcade et Luc Libralesso en 2021)

Sous le nom des Shadoks, nous avons participé à 4 challenges d'optimisation géométrique CG:SHOP (Computational Geometry: Solving Hard Problems https://cgshop.ibr.cs.tu-bs.de/) qui se déroulent dans le cadre des éditions de SoCG depuis 2019. Le thème de cet exposé est de présenter les heuristiques que nous avons développées pour ces problèmes NP-durs, heuristiques que l'on pourrait sous-titrer "comment des idées simples peuvent parfois fournir des algorithmes efficaces".
  • 2019 - Le problème "Optimal Area Polygonalization" est une variante de TSP (input: un ensemble de points du plan noté S/output: un polygone P simple de sommets S) dont l'objectif est de maximiser/minimiser l'aire intérieure de P au lieu de son périmètre.
  • 2020 - Le problème "Minimum Convex Partition" ressemble au problème en cours (couverture convexe minimale) mais nous passerons vite...
  • 2021 - Le problème "Coordinated Motion Planning" est un problème de routage d'agents "Multi-Agent Path Finding". Un ensemble de robots mobiles (des carrés unité) et un certain nombre d'obstacles fixes est positionné sur une grille carrée (2D). Chaque robot est donné avec une position initiale et une position finale. Le problème consiste à déplacer la flotte de robots, de case en case en évitant les collisions. L'objectif est de minimiser la durée entre le premier déplacement et le dernier (les robots se déplacent simultanément).
  • 2022 - Le problème "Minimum Partition into Plane Subgraphs" consiste à colorer un ensemble de segments du plans de façon à ce que deux segments qui se croisent aient des couleurs différentes et cela, en utilisant le moins de couleurs possible. Comme pour les robots, nous n'avons pas utilisé les algorithmes de l'état de l'art, car ils se sont avérés inférieurs à l'optimisation par conflit introduite sur les robots.


Conférencier : Michel HABIB (IRIF, Université Paris Cité)
Titre et résumé de l'exposé : Routages de voiliers une approche issue de la géométrie algorithmique
Travail commun avec Christian Dumard (Hokulea Marine Weather), Maxime Dupuy (Dice-engineering) et Laurent Viennot (Inria)

Conférencier : Ridha MAHJOUB (LAMSADE, Université Paris-Dauphine)
Titre et résumé de l'exposé : Le problème de ramassage et livraison préemptif
Travail commun avec : Hervé Kerivin (LIMOS, UCA), Mathieu Lacroix (LIPN, Université Paris 13), Alain Quilliot, (LIMOS, UCA).

Nous considérons le problème de ramassage et livraison préemptif. Certaines variantes sont examinées, lorsque la flotte est composée de plusieurs véhicules et quand elle consiste en un seul véhicule, lorsque le fractionnement des demandes est autorisé et quand cela n’est pas le cas, lorsqu’un véhicule ne peut transporter qu’une seule demande à la fois et quand il peut transporter plusieurs… Nous discutons de leurs complexités, et de leurs formulations en termes de programmes en nombres entiers mixtes. Nous décrivons des familles d’inégalités valides et discutons de leurs problèmes de séparations associés. En utilisant ces résultats, nous proposons des algorithmes de coupes et branchements, et présentons des résultats expérimentaux montrant l’efficacité des formulations et des contraintes décrites.

Conférencier : Aziz MOUKRIM (Laboratoire Heudiasyc, Université de Technologie de Compiègne)
Titre et résumé de l'exposé : Problèmes de tournées sélectives
  Avec Quentin Peña (Heudiasyc/UTC) et Mehdi Serairi (Heudiasyc/UTC)

Les problèmes de tournées sélectives constituent une famille de problèmes de tournées de véhicules (VRP) où a priori il n’est pas possible de servir tous les clients à cause de certaines contraintes de limitation de ressources. Dans sa version de base, le problème consiste à organiser les visites, avec profits associés, afin de maximiser la somme des profits collectés tout en respectant un temps de trajet limite imposé pour chaque véhicule. Plusieurs variantes ont vu le jour en fonction de la complexité des contextes. Nous développerons en particulier une application liée à la protection d’infrastructures menacées par l’avancée de feux de forêts avec des visites synchronisées et une flotte hétérogène (projet européen H2020 RISE GEO-SAFE). Il s’agit de replanifier les tournées pour tenir compte de différents aléas et déterminer un compromis entre protection et déviation par rapport à une planification initiale donnée. Nous proposons une reformulation d’une modélisation linéaire en nombres entiers et développons des inégalités valides dont nous montrons l’intérêt sur les instances de la littérature.

Inscription

Les inscriptions sont closes. Pour plus de renseignements, merci de contacter Hélène Toussaint (helene.toussaint AT uca.fr).

Voir la liste des inscrits

Restauration

Si les conditions sanitaires le permettent, un buffet sera offert aux participants inscrits le jeudi midi.

Comité d'organisation

Mourad Baiou, Fatiha Bendali, Jonas Koko, Philippe Lacomme, Jian-Jin Li, Jean Mailfert, Hélène Toussaint.