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.
Keywords: 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, Volume 47 (2013) no. 4, pp. 481-500. doi : 10.1051/ro/2013053. http://archive.numdam.org/articles/10.1051/ro/2013053/
[1] Challenge roadef/euro 2010: A large-scale energy management problem with varied constraints (2009), http://challenge.roadef.org/2010/files/sujetEDFv22.pdf.
, , , and ,[2] 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).
and ,[3] Solving the electricity production planning problem by a column generation based heuristic. J. Scheduling (2012) doi: 10.1007/s10951-012-0286-9. | MR | Zbl
, , , and ,[4] Solving a real-life, large-scale energy management problem. J. Schedulin (2012) doi: 10.1007/s10951-012-0279-8. | MR | Zbl
, , and ,[5] 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
, , and ,[6] 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
and ,[7] 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
, and ,[8] Optimizing nuclear power plant refueling with mixed-integer programming. Eur. J. Oper. Res. 97 (1997) 269-280. | Zbl
, , and ,[9] 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
, and ,[10] Principles of constraint programming, vol. 420. Cambridge University press (2003). | Zbl
,[11] IBM ILOG CPoptimizer and Cplex User's Guide (2009).
[12] Hybrid Optimization, Springer Optimization and Its Applications (2010). | MR | Zbl
and ,[13] A Constraint Programming Framework for Local Search Methods. J. Heuristics 5 (1999) 255-279. | Zbl
and ,[14] Comet, http://dynadec.com/technology/constraint-programming/.
[15] Mistral, http://www.cs.wm.edu/˜tdillig/mistral/index.html.
Cited by Sources: