Direction de recherche : Pierre FOUILHOUX

Co-encadrement : BENDOTTI Pascale, CHRÉTIENNE Philippe

Ancrage de solutions en optimisation robuste

Si les données d'un problème d'optimisation combinatoire changent, une solution initiale peut devenir sous-optimale ou infaisable. Il est alors nécessaire de calculer une nouvelle solution, mais aussi souhaitable de maintenir les décisions prises dans la solution initiale. Dans cette thèse nous proposons le critère d'ancrage pour favoriser les décisions inchangées entre solutions. En réoptimisation, il s'agit de trouver une solution conservant un nombre maximal de décisions d'une solution initiale. En optimisation robuste à deux étapes, nous proposons l'approche robuste-ancrée, qui consiste à calculer en avance une solution baseline et un sous-ensemble de décisions dites ancrées. Pour toute réalisation des données dans l'ensemble d'incertitude considéré, on peut réparer la solution baseline en une nouvelle solution sans changer les décisions ancrées. Cette approche permet un compromis entre le coût de la solution et les garanties sur les décisions. Les problèmes d'ancrage sont formalisés et déclinés sur deux classes de problèmes. La première est celle des programmes linéaires en variables binaires, et notamment des problèmes polynomiaux classiques comme l'arbre couvrant. La deuxième est celle des problèmes d'ordonnancement de projet, où des tâches doivent être ordonnancées sous des contraintes de précédences ou de ressources. La complexité algorithmique des problèmes d'ancrage est analysée. Les propriétés combinatoires des solutions ancrées sont étudiées, et permettent la conception d'approches algorithmiques et polyédrales dédiées. Des techniques de programmation linéaire en nombres entiers sont mises en œuvre, démontrant l'implémentabilité des problèmes d'ancrage.

Publications 2018-2024

• 2024
  • A. Pass‑Lanneau, P. Bendotti, L. Brunod‑Indrigo : “Exact and heuristic methods for Anchor-Robust and Adjustable-Robust RCPSP”, Annals of Operations Research, vol. 337 (2), pp. 649-682, (Springer Verlag) (2024)
• 2022
  • Th. Ehrhard, S. Attias, E. Bampis, V. Cohen‑Addad, B. Escoffier, C. Mathieu, F. Pascual, A. Pass‑Lanneau, D. Saulpic : “Découpage électoral des circonscriptions législatives en France: déséquilibres démographiques et contraintes territoriales”, Revue Française de Science Politique, vol. Vol. 72 (3), pp. 333-364, (Presses de Sciences Po) (2022)
  • A. Pass‑Lanneau, P. Bendotti, Ph. Chrétienne, P. Fouilhoux : “Anchored solutions in robust combinatorial optimization: PGMO Phd Award 2022”, PGMO Days 2022, Palaiseau, France (2022)
  • A. Pass‑Lanneau, P. Bendotti, Ph. Chrétienne, P. Fouilhoux : “Ancrage et robustesse pour le RCPSP: outils exacts et heuristiques”, 23^e congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Villeurbanne - Lyon, France (2022)
• 2021
  • A. Pass‑Lanneau : “Anchored solutions in robust combinatorial optimization”, soutenance de thèse, soutenance 16/03/2021, direction de recherche Fouilhoux, Pierre, co-encadrement : Bendotti, Pascale, Chrétienne, Philippe (2021)
  • P. Bendotti, Ph. Chrétienne, P. Fouilhoux, A. Pass‑Lanneau : “Dominance-based linear formulation for the Anchor-Robust Project Scheduling Problem”, European Journal of Operational Research, vol. 295 (1), pp. 22-33, (Elsevier) (2021)
• 2020
  • P. Bendotti, Ph. Chrétienne, P. Fouilhoux, A. Pass‑Lanneau : “Anchored Rescheduling Problems Under Generalized Precedence Constraints”, Combinatorial Optimization, 6^th International Symposium, ISCO 2020, Montreal, QC, Canada, May 4–6, 2020, vol. 12176, Lecture Notes in Computer Science, Montreal, QC, Canada, pp. 156-166 (2020)
  • B. Escoffier, H. Gilbert, A. Pass‑Lanneau : “Iterative Delegations in Liquid Democracy with Restricted Preferences”, AAAI Technical Track: Game Theory and Economic Paradigms, vol. 34 (2), New-York, NY, United States, pp. 1926-1933 (2020)
  • P. Bendotti, Ph. Chrétienne, P. Fouilhoux, A. Pass‑Lanneau : “Outils de résolution exacte pour l’ancrage de solutions en ordonnancement de projet”, ROADEF - 21^e congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision, Montpellier, France (2020)
• 2019
  • P. Bendotti, L. Brunod‑Indrigo, Ph. Chrétienne, P. Fouilhoux, A. Pass‑Lanneau : “Anchor-Robust Solutions for the Resource-Constrained Project Scheduling Problem”, PGMO Days 2019, Palaiseau, France (2019)
  • B. Escoffier, H. Gilbert, A. Pass‑Lanneau : “The Convergence of Iterative Delegations in Liquid Democracy in a Social Network”, Lecture Notes in Computer Science, vol. 11801, Athènes, Greece, pp. 284-297 (2019)
  • P. Bendotti, Ph. Chrétienne, P. Fouilhoux, A. Pass‑Lanneau : “The Anchor-Robust Project Scheduling Problem”, 14^th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), Renesse, Netherlands (2019)
  • P. Bendotti, Ph. Chrétienne, P. Fouilhoux, A. Pass‑Lanneau : “The Anchor-Robust Project Scheduling Problem”, Operations Research, (INFORMS) (2019)
  • P. Bendotti, Ph. Chrétienne, P. Fouilhoux, A. Pass‑Lanneau : “Stabilisation de solutions en optimisation combinatoire par des modèles d’ancrage; application à l’arbre couvrant”, ROADEF - 20^e congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision, Le Havre, France (2019)
• 2018
  • P. Bendotti, Ph. Chrétienne, P. Fouilhoux, A. Pass‑Lanneau : “Robust proactive maintenance planning with a deadline”, PGMO Days 2018, Palaiseau, France (2018)
  • P. Bendotti, Ph. Chrétienne, P. Fouilhoux, A. Pass‑Lanneau : “Ancrage de solutions en ordonnancement PERT”, ROADEF - 19^e congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision, Lorient, France (2018)