Le 18/11/2021 par CecileR :
Contexte
Plusieurs problèmes d’optimisation combinatoire reposent sur un croisement de plusieurs structures
combinatoires. C’est le cas du problème de planification d’unités de production électrique, appelé Unit
Commitment Problem (UCP) qui consiste à décider des marches et arrêts d’unités sous la contrainte
de satisfaire la demande sur un horizon de temps discret (journalier) en respectant des contraintes
techniques. Deux structures se croisent dans le problème de l’UCP : une structure de sac-à-dos à chaque
pas de temps et une structure de planification de chaque unité, ce qui couple ainsi dynamiquement
les pas de temps. D’autres problèmes ont une structure similaire, comme en particulier le problème de
l’UCP pour les vallées hydroélectriques, le problème de multi-flots entiers, le problème du p-médian
ou du sac-à-dos multiple.
Ces problèmes se formulent classiquement par des programmes linéaires de très grande taille. Afin
de résoudre de tels programmes, des techniques de décomposition comme la génération de colonnes ou
la décompostion Lagrangienne s’appuient fortement sur un choix d’inégalités à dualiser, produisant
un nombre exponentiel de variables à prendre en compte.
La décomposition croisée consiste à simultanément considérer plusieurs sous-structures lors de la
même décomposition. La gestion de ces sous-structures peut être réalisée en dupliquant des sous-ensembles
de variables et en les liant par des égalités (ou inégalités) dans le problème maître. Pour
le cas particulier de l’UCP, cette technique a été utilisée avec succès pour améliorer la qualité des
relaxations par rapport à une décomposition classique par unité, i.e. par dualisation de la demande.
La décomposition croisée basée sur la relaxation Lagrangienne est bien connue dans la littérature
et est classiquement appelée “variable splitting” ou “décomposition Lagrangienne" [2]. Cette technique
a été appliquée aux problèmes de flots [1] et au problème de l’affectation généralisée [3]. Elle a été
également appliquée au problème de l’UCP au sein d’EDF [4].
En comparaison, la décomposition croisée basée sur la génération de colonnes est moins classique
et a été assez peu mise en pratique [5, 6].
Objectifs du stage
L’objectif de ce stage est tout autant une étude théorique de la méthode qu’une mise en oeuvre
pratique de décompositions croisées en génération de colonne, sur différents problèmes.
Un précédent stage [8] a proposé une première étude théorique qui pourra constituer une base de
travail. De plus, la prise en main expérimentale sera facilitée par l’existence au sein du projet d’un
code (C++, SCIP) concernant l’UCP, qui a permis d’obtenir une relaxation de bonne qualité [7, 8] et
qui devrait être facilement réutilisable pour d’autres problèmes.
Le stage portera d’une part sur des aspects méthodologiques liés à la décomposition croisée en
génération de colonnes :
• Un travail sur les bornes inférieures obtenues au cours des itérations de génération de colonnes,
ainsi que sur l’amélioration de la convergence, a été amorcé dans [8], et pourrait être étendu à
la fois d’un point de vue pratique et théorique.
• Une autre perspective est de prolonger les relaxations obtenues par décomposition croisée,
soit par une méthode de branchement (Branch&Price), soit par des heuristiques basées sur
des solutions fractionnaires (par exemple Price&Branch) [9]. En effet la bonne qualité de la
relaxation est souvent un facteur clef de la bonne qualité des solutions ainsi obtenues.
L’idée étant de dégager une approche générique pour la mise en oeuvre de la méthode de décomposition
croisée, ces méthodes seront implémentées et testées sur différents problèmes combinatoires :
• Le code développé dans [8] pourra être utilisé pour valider et comparer les différentes méthodes
appliquées à l’UCP. En particulier, différentes structures de décomposition croisée ont
été proposées et mériteraient d’être approfondies et comparées.
• Un autre objectif du stage est d’implémenter la décomposition croisée en génération de colonne
à un autre problème combinatoire, comme par exemple le sac-à-dos multiple ou le multi-flot.
Le sujet de ce stage s’inscrit dans le projet PGMO intitulé “Overlapping decomposition in column
generation” rassemblant des chercheurs de EDF R&D et de deux laboratoires d’informatiques
le LIP6 et le LIPN. Suite à ce stage, une poursuite en thèse n’est pas prévue dans le cadre de ce
projet PGMO. Toutefois, le sujet de recherche implique plusieurs acteurs industriels et universitaires
qui peuvent proposer une suite en thèse sur ce sujet ou un sujet proche.
Conditions matérielles
Ce stage est réalisé dans le cadre d’un projet PGMO en collaboration entre EDF R&D (département OSIRIS)
et le laboratoire LIP6.
Employeur : Laboratoire LIP6 dans le cadre d’une convention de stage académique
Lieu du stage : LIP6, 4 place Jussieu, 75005 Paris
Durée : 5-6 mois entre février et octobre 2022
Rémunération : Gratification stage
Connaissances requises : Deuxième année de Master Recherche ou troisième année d’école d’ingénieur
Profil : Mathématiques appliquées, Informatique, Optimisation combinatoire, RO
Informatique : Programmation orientée objet, C++
Encadrement
Pascale Bendotti (EDF, membre associé LIP6) pascale.bendotti@lip6.fr
Pierre Fouilhoux (LIPN, Sorbonne Paris Nord) pierre.fouilhoux@lipn.fr
Cécile Rottner (EDF) cecile.rottner@edf.fr
Références
[1] Fred Glover and Darwin Klingman. Layering strategies for creating exploitable structure in linear and integer
programs. Mathematical Programming, 40(1-3) :165-181, 1988.
[2] Monique Guignard and Siwhan Kim. Lagrangean decomposition for integer programming : theory and applications.
RAIRO-Operations Research, 21(4) :307-323, 1987.
[3] Kurt Jörnsten and Mikael Näsberg. A new lagrangian relaxation approach to the generalized assignment problem.
European Journal of Operational Research, 27(3) :313-x323, 1986.
[4] A. Renaud. Daily generation management at Electricité de France : From planning towards realtime. IEEE Transactions
on Automatic Control, 38, 1993.
[5] Carina Maria Oliveira Pimentel , Filipe Pereira e Alvelos and José Manuel Valério de Carvalho. Comparing Dantzig–
Wolfe decompositions and branch-and-price algorithms for the multi-item capacitated lot sizing problem. Methods
& Software, 25(2), 299-319, 2010.
[6] Lucas Létocart, Nora Touati Moungla and Anass Nagih. Dantzig-Wolfe and Lagrangian decompositions in integer
linear programming. International Journal of Mathematics in Operational Research, 4(3), 247-262, 2011.
[7] Cécile Rottner. Combinatorial aspects of the Unit Commitment Problem. Doctoral dissertation (2018).
[8] Alexis Schneider. Column generation in overlapping structures (rapport de stage de M2) (2021).
[9] François Vanderbeck. Branching in branch-and-price : a generic scheme. Mathematical Programming, 130(2), 249-
294, 2011.
