PhD graduated
Team : RO
Departure date : 12/25/2018

Supervision : Pierre FOUILHOUX

Co-supervision : BENDOTTI Pascale

Combinatorial Aspects of the Unit Commitment Problem

The Unit Commitment Problem (UCP) is solved at EDF on a daily basis. The combinatorial core structure of the UCP, called the Min-up/min-down Unit Commitment Problem (MUCP), is to find a minimum-cost production plan on a discrete time horizon for a set of units producing electric power. At each time period, the total production has to meet a forecast demand. Each unit must satisfy minimum up-time and down-time constraints besides featuring production and start-up costs. We show that the MUCP is strongly NP-hard, thus highlighting that the dynamic coupling of demands by minimum up and down time constraints represents one major source of difficulty. To cope with this difficulty, we introduce interval up-set inequalities, a new class of valid inequalities for the MUCP polytope, generalizing both min-up inequalities and extended cover inequalities from the 0-1 knapsack polytope. Facet defining cases are characterized and a Branch & Cut algorithm is devised. To deal with the symmetries impairing the solution process, we define sub-symmetries, as symmetries arising from a solution subset. We focus on integer linear programs whose (sub-)symmetry groups are symmetric groups acting on (sub-)columns of solution matrices. We propose a general framework to handle sub-symmetries in such problems. On this basis, two symmetry-breaking techniques are introduced. The first technique is an orbitopal fixing algorithm for the full orbitope, defined as the convex hull of binary matrices with lexicographically nonincreasing columns. The second technique is based on sub-symmetry breaking inequalities. Experimental results on MUCP instances show that the proposed techniques outperform state-of-the-art symmetry-breaking techniques. To exploit the UCP intrinsic decomposition structures, we compare various Dantzig-Wolfe formulations for the MUCP. we show that good quality lower bounds can be obtained by dualization of time-coupling constraints. Interval up-set inequalities are useful in this context, as shown in preliminary Branch & Price results.

Defence : 11/14/2018 - 14h - Site Jussieu 55-66/211

Jury members :

Christian ARTIGUES, Directeur de recherche au LAAS-CNRS, Toulouse [rapporteur]
Volker KAIBEL, Professeur à Otto-von-Guericke-Universität, Magdeburg [rapporteur]
Philippe CHRÉTIENNE, Professeur à Sorbonne Université, Paris
Ivana LJUBIC, Professeur à l'ESSEC Business School, Cergy
Pascale BENDOTTI, Ingénieur-Chercheur à EDF R&D, Palaiseau
Pierre FOUILHOUX, Maître de conférence à Sorbonne Université, Paris

2017-2020 Publications