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