ROTTNER Cécile
Direção de pesquisa : Pierre FOUILHOUX
Co-supervisão£o : 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.
Defesas : 14/11/2018
Membros da banca :
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
Publicações 2017-2024
-
2024
- A. Heintzmann, P. Bendotti, C. Rottner : “Handling polyhedral symmetries with a dedicated Branch&Cut: application to a knapsack variant”, (2024)
-
2022
- P. Bendotti, P. Fouilhoux, C. Rottner, Th. Vignon : “Overlapping decomposition in column generation”, PGMODAYS 2022, Palaiseau, France (2022)
-
2021
- P. Bendotti, P. Fouilhoux, C. Rottner : “Orbitopal fixing for the full (sub)-orbitope and application to the Unit Commitment Problem”, Mathematical Programming, vol. 186 (1-2), pp. 337-372, (Springer Verlag) (2021)
-
2020
- P. Bendotti, P. Fouilhoux, C. Rottner : “Symmetry-breaking inequalities for ILP with structured sub-symmetry”, Mathematical Programming, vol. 183 (1-2), pp. 61-103, (Springer Verlag) (2020)
-
2019
- P. Bendotti, P. Fouilhoux, C. Rottner : “Sub-Symmetry-Breaking Inequalities for ILP with Structured Symmetry”, Lecture Notes in Computer Science, vol. 11480, Lecture Notes in Computer Science, Ann Arbor, Michigan, United States, pp. 57-71, (Springer) (2019)
- P. Bendotti, P. Fouilhoux, C. Rottner : “On the complexity of the Unit Commitment Problem”, Annals of Operations Research, vol. 274 (1-2), pp. 119-130, (Springer Verlag) (2019)
- C. Rottner, P. Bendotti, P. Fouilhoux : “Breaking structured symmetries and sub-symmetries in Integer Linear Programming”, ROADEF 2019 - 20e congrès annuel de la société Française de Recherche Opérationnelle et d’Aide à la Décision, Le Havre, France (2019)
-
2018
- C. Rottner : “Combinatorial Aspects of the Unit Commitment Problem”, tese, defesas 14/11/2018, direção de pesquisa Fouilhoux, Pierre, co-supervisão£o : Bendotti, Pascale (2018)
- P. Bendotti, P. Fouilhoux, C. Rottner : “The min-up/min-down unit commitment polytope”, Journal of Combinatorial Optimization, vol. 36 (3), pp. 1024-1058, (Springer Verlag) (2018)
- P. Bendotti, P. Fouilhoux, C. Rottner : “Breaking full-orbitopal symmetries and sub-symmetries”, ISMP International Conference on Mathematical Programming (ISMP 2018), Bordeaux, France (2018)
- P. Bendotti, P. Fouilhoux, C. Rottner : “Breaking symmetries for the UCP by intersecting the full orbitope with an hypercube face”, International Symposium on Combinatorial Optimization (ISCO 2018), Marrakesh, Morocco (2018)
- P. Bendotti, P. Fouilhoux, C. Rottner : “Casser les symétries dans les PLNE à deux indices”, ROADEF - 19e congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision, Lorient, France (2018)
-
2017
- P. Bendotti, P. Fouilhoux, C. Rottner : “Aspects polyédraux du Min-up/min-down Unit Commitment Problem”, Journées Polyèdres et Optimisation Combinatoire (JPOC10), Villetaneuse, France (2017)
- P. Bendotti, P. Fouilhoux, C. Rottner : “Formulations PLNE et Branch & Cut pour le Min-up/Min-down Unit Commitment Problem”, ROADEF - 18e congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision, Metz, France (2017)