Optimality for Tough Combinatorial Hydro Valley Problems

The project has been accepted in the context of the Gaspard Monge Program for Optimization (PGMO), launched by EDF and the Jacques Hadamard Mathematical Foundation (FMJH).

Research Topic

In Energy Management, the Unit commitment problem aims at computing the optimal production schedule for a hydro-thermal energy mix. This schedule is then executed to meet customer demand in real time the next day. As such, feasibility of the schedule is a key requirement. In order to solve the unit-commitment problem efficiently in finite time, decomposition methods based on Lagrangian relaxation are employed. These methods then require that various smaller sub-problems are resolved quickly. One such a sub-problem is optimization of a hydro valley (on a price signal). When continuous, such a problem is easily solved to optimality by any current LP solver. However, the introduction of combinatorial elements as a result of the quest for feasible schedules, leads to far tougher hydro valley problems. This is especially true for some of the larger French Hydro valleys. Indeed, solving some of these up to several % of optimality might already require several minutes. Multiplying this with the number of iterations of the global decomposition schedule, one ends up with too much computation time for the optimization software to be of operational use. It therefore becomes apparent that efficient reformulations, or further decomposition should be looked into. This is exactly the objective of the current post-doc program.

The plan

Literature survey.
Data collecting on real-world instances and publication if confidentiality issues permit.
Modeling.
Reformulations.
Matheuristics, i.e., heuristic algorithms based on mathematical formulations.

The Team

Thanks to the PGMO funding we hired as post-doc:

Raouia Taktak

who is now assistant professor at ISIMS (Higher Institute of Computer Science and Multimedia of Sfax).

Other members:

Wim van Ackooij, EDF Research and Development (France)

Claudia D'Ambrosio, CNRS and LIX, Ecole Polytechnique (France)

Grace Doukopoulos, EDF Research and Development (France)

Antonio Frangioni, DI, University of Pisa (Italy)

Claudio Gentile, IASI, CNR (Italy)

Frederic Roupin, LIPN, Paris XIII (France)

Sonia Toubaline, LIX, Ecole Polytechnique (France)

Former member:

Tomas Simovic, EDF Research and Development (France) now at Sapient Global Markets (UK)

Publications and Technical Reports

R. Taktak and C. D'Ambrosio "An Overview on Mathematical Programming Approaches for the Deterministic Unit Commitment Problem in Hydro Valleys", Energy Systems (accepted). A first version of the paper can be found here.

Conference Talks and Seminars

R. Taktak, C. D'Ambrosio, S. Toubaline "Problème de gestion de production électrique à court-terme dans les vallées hydrauliques", talk at Roadef 2016. Compiegne, France, February 2016.

R. Taktak et al. "Optimal Short-term Hydro Unit Commitment in Hydro Valleys", talk at INFORMS Conference 2014. San Francisco, USA, November 2014.

R. Taktak et al. "Optimal Short-term Unit Commitment Problem in Hydro Valleys", talk at PGMO-COPI Conference 2014. Palaiseau, France, October 2014.

C. D'Ambrosio et al. "Optimality for Tough Combinatorial Hydro Valley Problems", talk at Roadef 2013. Troyes, France, February 2013.

C. D'Ambrosio "Optimality for Tough Combinatorial Hydro Valley Problems", PGMO seminars, France, 2012.

Posters

R. Taktak et al. "Optimality for Tough Combinatorial Hydro Valley Problems", Poster at IPCO XVII, Bonn, Germany, June 2014.

R. Taktak et al. "Optimality for Tough Combinatorial Hydro Valley Problems", Poster at PGMO-COPI Conference 2014. Palaiseau, France, October 2014.

C. D'Ambrosio et al. "Optimality for Tough Combinatorial Hydro Valley Problems", Poster at PGMO Conference 2013. Palaiseau, France, September 2012.