A Hybrid Approach Combining Local Search and Constraint Programming for a Large Scale Energy Management Problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 47 (2013) no. 4, pp. 481-500.

This paper presents a heuristic approach combining constraint satisfaction, local search and a constructive optimization algorithm for a large-scale energy management and maintenance scheduling problem. The methodology shows how to successfully combine and orchestrate different types of algorithms and to produce competitive results. We also propose an efficient way to scale the method for huge instances. A large part of the presented work was done to compete in the ROADEF/EURO Challenge 2010, organized jointly by the ROADEF, EURO and Électricité de France. The numerical results obtained on official competition instances testify about the quality of the approach. The method achieves 3 out of 15 possible best results.

DOI : 10.1051/ro/2013053
Classification : 90-08, 68T20, 90C10, 90C59
Mots-clés : constraint satisfaction, local search, optimization, scheduling, ROADEF challenge 
@article{RO_2013__47_4_481_0,
     author = {Gavranovi\'c, Haris and Buljuba\v{s}i\'c, Mirsad},
     title = {A {Hybrid} {Approach} {Combining} {Local} {Search} and {Constraint} {Programming} for a {Large} {Scale} {Energy} {Management} {Problem}},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {481--500},
     publisher = {EDP-Sciences},
     volume = {47},
     number = {4},
     year = {2013},
     doi = {10.1051/ro/2013053},
     mrnumber = {3143765},
     zbl = {1282.90023},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2013053/}
}
TY  - JOUR
AU  - Gavranović, Haris
AU  - Buljubašić, Mirsad
TI  - A Hybrid Approach Combining Local Search and Constraint Programming for a Large Scale Energy Management Problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2013
SP  - 481
EP  - 500
VL  - 47
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2013053/
DO  - 10.1051/ro/2013053
LA  - en
ID  - RO_2013__47_4_481_0
ER  - 
%0 Journal Article
%A Gavranović, Haris
%A Buljubašić, Mirsad
%T A Hybrid Approach Combining Local Search and Constraint Programming for a Large Scale Energy Management Problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2013
%P 481-500
%V 47
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2013053/
%R 10.1051/ro/2013053
%G en
%F RO_2013__47_4_481_0
Gavranović, Haris; Buljubašić, Mirsad. A Hybrid Approach Combining Local Search and Constraint Programming for a Large Scale Energy Management Problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 47 (2013) no. 4, pp. 481-500. doi : 10.1051/ro/2013053. http://archive.numdam.org/articles/10.1051/ro/2013053/

[1] M. Porcheron, A. Gorge, O. Juan, T. Simovic and G. Dereu, Challenge roadef/euro 2010: A large-scale energy management problem with varied constraints (2009), http://challenge.roadef.org/2010/files/sujetEDFv22.pdf.

[2] F. Gardi and K. Nouioua, Local Search for Mixed-Integer Nonlinear Optimization: a Methodology and an Application, EvoCop: 11th European conference on evolutionary computation in combinatorial optimisation, Torino, Italy (2011).

[3] A. Rozenknop, R. Wolfler Calvo, L. Alfandari, D. Chemla and L. Letocart, Solving the electricity production planning problem by a column generation based heuristic. J. Scheduling (2012) doi: 10.1007/s10951-012-0286-9. | MR | Zbl

[4] S. Godskesen, T.S. Jensen, N. Kjeldsen and R. Larsen, Solving a real-life, large-scale energy management problem. J. Schedulin (2012) doi: 10.1007/s10951-012-0279-8. | MR | Zbl

[5] F. Brandt, R. Bauer, M. Völker and A. Cardeneo, A constraint programming-based approach to a large-scale energy management problem with varied constraints. J. Scheduling (2012) doi: 10.1007/s10951-012-0281-1. | Zbl

[6] V. Jost and D. Savourey, A 01 integer linear programming approach to schedule outages of nuclear power plants. J. Scheduling (2013) doi: 10.1007/s10951-013-0322-4. | MR | Zbl

[7] R. Lusby, L. Muller and B. Petersen, A solution approach based on Benders decomposition for the preventive maintenance scheduling problem of a stochastic large-scale energy system. J. Scheduling (2011) 10.1007/s10951-012-0310-0. | Zbl

[8] F. Fourcade, E. Johnson, M. Bara and P. Cortey-Dumont, Optimizing nuclear power plant refueling with mixed-integer programming. Eur. J. Oper. Res. 97 (1997) 269-280. | Zbl

[9] M. Khemmoudj, M. Porcheron and H. Bennaceur, When constraint programming and local search solve the scheduling problem of Électricité de France nuclear power plant outages, In CP 2006, the 12th International Conference on Principles and Practice of Constraint Programming, edited by F. Benhamou. Lecture Notes in Computer Science, vol. 4204. Springer, Berlin, Germany (2006) 271-283. | Zbl

[10] R.A. Krzysztof, Principles of constraint programming, vol. 420. Cambridge University press (2003). | Zbl

[11] IBM ILOG CPoptimizer and Cplex User's Guide (2009).

[12] M. Milano and P. Van Hentenryck, Hybrid Optimization, Springer Optimization and Its Applications (2010). | MR | Zbl

[13] G. Pesant and M. Gendreau, A Constraint Programming Framework for Local Search Methods. J. Heuristics 5 (1999) 255-279. | Zbl

[14] Comet, http://dynadec.com/technology/constraint-programming/.

[15] Mistral, http://www.cs.wm.edu/˜tdillig/mistral/index.html.

Cité par Sources :