Forum 'Stages' - Sujet créé le 2025-11-03 par Pascale Bendotti
Application au problème de plus court chemin contraint en ressource et au problème de coloration de graphe
En management d’énergie, le Unit Commitment Problem (UCP), consiste à définir les plans de production des unités de production d’électricité de coût minimum. Le temps est discrétisé en pas de temps sur un horizon borné. Le plan doit satisfaire des contraintes locales liées au fonctionnement des unités et des contraintes globales de demande
à chaque pas de temps. Compte tenu de la taille des instances, des algorithmes de décomposition sont utilisés. Le sous-problème est typiquement résolu par programmation dynamique en se ramenant au Resource-Constrained Shortest Path Problem (RCSPP) [1]. Des limites en espace et temps sont atteintes pour prendre en compte certaines contraintes. En management d’énergie, le Unit Commitment Problem (UCP), consiste à définir les plans de production des unités de production d’électricité de coût minimum. Le temps est discrétisé en pas de temps sur un horizon borné. Le plan doit satisfaire des contraintes locales liées au fonctionnement des unités et des contraintes
globales de demande `a chaque pas de temps. Compte tenu de la taille des instances, des algorithmes de décomposition sont utilisés. Le sous-problème est typiquement résolu par programmation dynamique en se ramenant au Resource-Constrained Shortest Path Problem (RCSPP). Compte tenu de limites en espace et temps, certaines contraintes ne peuvent pas être prises en compte comme en particulier une capacité sur une ressource.
En smart-charging, un problème émergent est l’affectation des bornes de recharge pour des véhicules électriques. Ce problème a été étudié comme cas d’usage pour des algorithmes de Quantum Annealing (QAA) avec expérimentation sur une machine à atomes neutres dans le cas particulier à une borne. Dans le cas à plusieurs bornes, le problème se ramène à un problème de coloration de graphe (GC). Ce problème étant NP-difficile au sens fort à partir de 3 couleurs pour un graphe quelconque, une amélioration de performance par rapport aux algorithmes classiques est nécessaire pour résoudre des instances de grande taille. Un résultat de la littérature propose un avantage quantique dans le cas de problèmes NP-difficile pour lesquels les meilleurs algorithmes classiques de programmation dynamique sont en temps exponentiel. La technique proposée consiste à intégrer dans un calcul de programmation dynamique une recherche de Grover, ce qui suppose de recourir à une mémoire quantique (QRAM). Un résultat plus récent étend ce résultat au problème de recherche par branchement dans le cas du problème de coloration de graphe. Deux variantes sont proposées, dont un algorithme polynomial en espace n’utilisant pas de QRAM.
A partir des résultats de la littérature, l’objectif du stage est d’analyser en détail les algorithmes proposés, de les adapter aux deux problèmes identifiés du RCSPP et de GC et d’évaluer leurs performances.
Contact: