Le problème UCP (Unit Commitment Problem) consiste à planifier la production d'’un parc de centrales électriques de manière à satisfaire un besoin prévisionnel donné sur une échelle de temps discrétisée (besoin horaire sur 24 heures).
L’'objectif consiste à définir à moindre coût

• d’'une part, l’'ordonnancement d’'allumage/extinction de chaque centrale sur toute la période considérée,
• et d’'autre part, la production de chaque centrale pour toute date où elle est allumée,

de façon à satisfaire l’'ensemble des deux contraintes globales (demande prévisionnelle et réserve de 10% modélisant l'’incertitude de la prévision) et de trois contraintes techniques propres à chaque générateur: puissance bornée, temps minimum d’'arrêt avant redémarrage, temps minimum de fonctionnement avant extinction. La fonction de coût d'un générateur comprend un coût de fonctionnement légèrement quadratique auquel s'ajoute un coût de démarrage dépendant de la durée d'arrêt d'une centrale que l'on allume. Nous réalisons une relaxation lagrangienne en dualisant les contraintes globales, et nous résolvons le problème ainsi relâché par programmation dynamique après avoir précalculé pour chaque date la production optimale connaissant les multiplicateurs de Lagrange. La programmation dynamique permet également le calcul du coût réduit nécessaire pour compenser le viol de certaines contraintes pour l’itération suivante. Ceci nous fournit une borne duale additive que nous exploitons d’une part pour améliorer la borne inférieure, et d'autre part pour filtrer des variables par Programmation Par Contraintes en cours du processus d’énumération implicite.
Les coûts réduits sont également exploités pour guider le choix des couples (variable – valeur) dans la phase de séparation du Branch and Bound.