Direction de recherche : Pierre FOUILHOUX

Co-encadrement : BENDOTTI Pascale

Aspects combinatoires du "Unit Commitment Problem"

Le Unit Commitment Problem (UCP) est un problème de planification électrique résolu quotidiennement à EDF. Le Min-up/min-down Unit Commitment Problem (MUCP), structure combinatoire de l'UCP, consiste à trouver un plan de production de coût minimum pour un ensemble d’unités de production électrique considérées sur un horizon de temps discrétisé. A chaque pas de temps, la production totale doit satisfaire la demande prévue. Chaque unité doit respecter des temps minimum de marche et d’arrêt. Nous montrons que le MUCP est NP-difficile au sens fort, mettant ainsi en valeur l’impact du couplage dynamique des contraintes de demande sur la difficulté du problème. Pour appréhender cette difficulté, nous introduisons une nouvelle classe d’inégalités valides nommées interval up-set, généralisant à la fois les contraintes de min-up et les extended cover du polyèdre du sac à dos binaire. Une caractérisation des facettes est donnée, et un algorithme de Branch & Cut est implémenté. Afin de casser les symétries qui compromettent la résolution par Branch & Bound, nous définissons les sous-symétries comme des symétries apparaissant dans des sous-ensembles de solutions. Nous considérons des programmes linéaires en nombres entiers dont les groupes de sous-symétrie sont des groupes symétriques agissant sur certaines sous-colonnes des matrices solutions. Nous proposons un cadre générique pour gérer les sous-symétries apparaissant dans ce type de problèmes. Sur cette base, deux techniques pour briser les (sous-)symétries sont proposées : la première est un algorithme de fixing orbitopal pour le full sub-orbitope, la seconde est basée sur des inégalités. Les résultats expérimentaux sur des instances du MUCP montrent que les techniques proposées sont plus performantes que les techniques de la littérature. Enfin, nous comparons différentes structures de décomposition pour le MUCP. Nous montrons que des bornes de bonne qualité sont obtenues par dualisation des contraintes dynamiques. Les résultats de notre algorithme de Branch & Price montrent que les inégalités interval up-set sont utiles dans ce contexte.

Publications 2017-2024

• 2024
  • A. Heintzmann, P. Bendotti, C. Rottner : “Handling polyhedral symmetries with a dedicated Branch&Cut: application to a knapsack variant”, (2024)
• 2022
  • P. Bendotti, P. Fouilhoux, C. Rottner, Th. Vignon : “Overlapping decomposition in column generation”, PGMODAYS 2022, Palaiseau, France (2022)
• 2021
  • P. Bendotti, P. Fouilhoux, C. Rottner : “Orbitopal fixing for the full (sub)-orbitope and application to the Unit Commitment Problem”, Mathematical Programming, vol. 186 (1-2), pp. 337-372, (Springer Verlag) (2021)
• 2020
  • P. Bendotti, P. Fouilhoux, C. Rottner : “Symmetry-breaking inequalities for ILP with structured sub-symmetry”, Mathematical Programming, vol. 183 (1-2), pp. 61-103, (Springer Verlag) (2020)
• 2019
  • P. Bendotti, P. Fouilhoux, C. Rottner : “Sub-Symmetry-Breaking Inequalities for ILP with Structured Symmetry”, Lecture Notes in Computer Science, vol. 11480, Lecture Notes in Computer Science, Ann Arbor, Michigan, United States, pp. 57-71, (Springer) (2019)
  • P. Bendotti, P. Fouilhoux, C. Rottner : “On the complexity of the Unit Commitment Problem”, Annals of Operations Research, vol. 274 (1-2), pp. 119-130, (Springer Verlag) (2019)
  • C. Rottner, P. Bendotti, P. Fouilhoux : “Breaking structured symmetries and sub-symmetries in Integer Linear Programming”, ROADEF 2019 - 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
  • C. Rottner : “Combinatorial Aspects of the Unit Commitment Problem”, soutenance de thèse, soutenance 14/11/2018, direction de recherche Fouilhoux, Pierre, co-encadrement : Bendotti, Pascale (2018)
  • P. Bendotti, P. Fouilhoux, C. Rottner : “The min-up/min-down unit commitment polytope”, Journal of Combinatorial Optimization, vol. 36 (3), pp. 1024-1058, (Springer Verlag) (2018)
  • P. Bendotti, P. Fouilhoux, C. Rottner : “Breaking full-orbitopal symmetries and sub-symmetries”, ISMP International Conference on Mathematical Programming (ISMP 2018), Bordeaux, France (2018)
  • P. Bendotti, P. Fouilhoux, C. Rottner : “Breaking symmetries for the UCP by intersecting the full orbitope with an hypercube face”, International Symposium on Combinatorial Optimization (ISCO 2018), Marrakesh, Morocco (2018)
  • P. Bendotti, P. Fouilhoux, C. Rottner : “Casser les symétries dans les PLNE à deux indices”, 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)
• 2017
  • P. Bendotti, P. Fouilhoux, C. Rottner : “Aspects polyédraux du Min-up/min-down Unit Commitment Problem”, Journées Polyèdres et Optimisation Combinatoire (JPOC10), Villetaneuse, France (2017)
  • P. Bendotti, P. Fouilhoux, C. Rottner : “Formulations PLNE et Branch & Cut pour le Min-up/Min-down Unit Commitment Problem”, ROADEF - 18^e congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision, Metz, France (2017)