The EURO ROADEF 2010 Challenge aimed to schedule the maintenance and refueling operations of French nuclear power plants, ranking the approaches in competition for the quality of primal solutions. This paper justifies the high quality of the best solutions computing dual bounds with dual heuristics. A first step designs several Mixed Integer Programming (MIP) relaxations with different compromises between computation time and quality of dual bounds. To deal with smaller MIPs, we prove how reductions in the number of time steps and scenarios can guarantee dual bounds for the whole problem of the Challenge. Several sets of dual bounds are computable, improving significantly the former best dual bounds of the literature. Intermediate results allow also a better understanding of the problem and offer perspectives to improve some approaches of the Challenge.
One of the main difficulties of the challenge is the big size of the instances. It was a natural and common idea to reduce the sizes of the instances with aggregations. On one hand, the power production in the time steps @math can be aggregated to their weekly average value. On the other hand, the stochastic scenarios were often aggregated into one deterministic scenario considering the average values of T1 power bounds and production costs. In order to reduce the number of scenarios, @cite_16 focused on 3 scenarios including the average scenario and the scenarios with the minimal and maximal accumulated demands. Their tests conclude that it is a good compromise of the scenarios reduction which does not degrade the quality of the solutions. None of the previous work studied the impact of such aggregations in terms of dual bounds.
@cite_16
1963524746
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 Electricite 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.