A Hybrid Approach Combining Local Search and Constraint Programming for a Large Scale Energy Management Problem

Haris Gavranović; Mirsad Buljubašić

RAIRO - Operations Research - Recherche Opérationnelle (2013)

  • Volume: 47, Issue: 4, page 481-500
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Gavranović, Haris, and 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 47.4 (2013): 481-500. <http://eudml.org/doc/275031>.

@article{Gavranović2013,
abstract = {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.},
author = {Gavranović, Haris, Buljubašić, Mirsad},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {constraint satisfaction; local search; optimization; scheduling; ROADEF challenge},
language = {eng},
number = {4},
pages = {481-500},
publisher = {EDP-Sciences},
title = {A Hybrid Approach Combining Local Search and Constraint Programming for a Large Scale Energy Management Problem},
url = {http://eudml.org/doc/275031},
volume = {47},
year = {2013},
}

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
PB - EDP-Sciences
VL - 47
IS - 4
SP - 481
EP - 500
AB - 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.
LA - eng
KW - constraint satisfaction; local search; optimization; scheduling; ROADEF challenge
UR - http://eudml.org/doc/275031
ER -

References

top
  1. [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. [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. [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. Zbl1280.90137MR3128010
  4. [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. Zbl1280.90047MR3128009
  5. [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. Zbl1280.90034
  6. [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. Zbl1280.90052MR3128008
  7. [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. Zbl1280.90062
  8. [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. Zbl0930.90063
  9. [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. Zbl1160.68553
  10. [10] R.A. Krzysztof, Principles of constraint programming, vol. 420. Cambridge University press (2003). Zbl1187.68132
  11. [11] IBM ILOG CPoptimizer and Cplex User’s Guide (2009). 
  12. [12] M. Milano and P. Van Hentenryck, Hybrid Optimization, Springer Optimization and Its Applications (2010). Zbl1201.90004MR2663904
  13. [13] G. Pesant and M. Gendreau, A Constraint Programming Framework for Local Search Methods. J. Heuristics5 (1999) 255–279. Zbl1064.90577
  14. [14] Comet, http://dynadec.com/technology/constraint-programming/. 
  15. [15] Mistral, http://www.cs.wm.edu/˜tdillig/mistral/index.html. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.