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.
We distinguish three types of approaches for the ROADEF challenge. The first category gathers using MIP models to tackle a simplified and reduced MIP problem before a reparation procedure to build solutions for the original problem, as in @cite_1 @cite_14 @cite_2 . The second category gathers . In this category, we find the two best approaches of the Challenge in terms of solution quality, @cite_6 for an aggressive Local search with the methodology of @cite_15 , @cite_7 having similar results with a Simulated Annealing approach. The third category, as in @cite_12 @cite_13 @cite_16 @cite_17 , gathers solving iteratively two types of subproblems. The high-level problem schedule outage dates and refueling decisions with constraints CT7-CT11 and CT13-CT21 can be solved with MIP or Constraint Programming approaches. Low-level subproblems optimize independently for all scenario the production plans fulfilling the constraints CT1-CT6 and CT12 with fixed fuel levels and maintenance dates.
@cite_14 @cite_7 @cite_1 @cite_6 @cite_2 @cite_15 @cite_16 @cite_13 @cite_12 @cite_17
2055066666 2036434250 2806180587 2059695025 1965513150 1963524746 2501937168 2178167101 1499047025
This paper describes a Benders decomposition-based framework for solving the large scale energy management problem that was posed for the ROADEF 2010 challenge. The problem was taken from the power industry and entailed scheduling the outage dates for a set of nuclear power plants, which need to be regularly taken down for refueling and maintenance, in such a way that the expected cost of meeting the power demand in a number of potential scenarios is minimized. We show that the problem structure naturally lends itself to Benders decomposition; however, not all constraints can be included in the mixed integer programming model. We present a two phase approach that first uses Benders decomposition to solve the linear programming relaxation of a relaxed version of the problem. In the second phase, integer solutions are enumerated and a procedure is applied to make them satisfy constraints not included in the relaxed problem. To cope with the size of the formulations arising in our approach we describe efficient preprocessing techniques to reduce the problem size and show how aggregation can be applied to each of the subproblems. Computational results on the test instances show that the procedure competes well on small instances of the problem, but runs into difficulty on larger ones. Unlike heuristic approaches, however, this methodology can be used to provide lower bounds on solution quality. We address the problem of planning outages of nuclear power plants submitted by EDF (Electricite De France) as the challenge EURO ROADEF 2010. As our team won the first prize of the contest in the senior category, our approach may be of interest: it is conceptually simple, easy to program and computationally relatively fast. We present both our method and some ideas to improve it. This paper presents a heuristic method based on column generation for the EDF (Electricite De France) long-term electricity production planning problem proposed as subject of the ROADEF EURO 2010 Challenge. This is to our knowledge the first-ranked method among those methods based on mathematical programming, and was ranked fourth overall. The problem consists in determining a production plan over the whole time horizon for each thermal power plant of the French electricity company, and for nuclear plants, a schedule of plant outages which are necessary for refueling and maintenance operations. The average cost of the overall outage and production planning, computed over a set of demand scenarios, is to be minimized. The method proceeds in two stages. In the first stage, dates for outages are fixed once for all for each nuclear plant. Data are aggregated with a single average scenario and reduced time steps, and a set-partitioning reformulation of this aggregated problem is solved for fixing outage dates with a heuristic based on column generation. The pricing problem associated with each nuclear plant is a shortest path problem in an appropriately constructed graph. In the second stage, the reload level is determined at each date of an outage, considering now all scenarios. Finally, the production quantities between two outages are optimized for each plant and each scenario by solving independent linear programming problems. This paper introduces LocalSolver 1.x, a black-box local-search solver for general 0-1 programming. This software allows OR practitioners to focus on the modeling of the problem using a simple formalism, and then to defer its actual resolution to a solver based on efficient and reliable local-search techniques. Started in 2007, the goal of the LocalSolver project is to offer a model-and-run approach to combinatorial optimization problems which are out of reach of existing black-box tree-search solvers (integer or constraint programming). Having outlined the modeling formalism and the main technical features behind LocalSolver, its effectiveness is demonstrated through an extensive computational study. The version 1.1 of LocalSolver can be freely downloaded at http: www.localsolver.com and used for educational, research, or commercial purposes. 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. The demand for electrical energy is globally growing very quickly. For this reason, the optimization of power plant productions and power plant maintenance scheduling have become important research topics. A Large Scale Energy Management (LSEM) problem is studied in this paper. Two types of power plants are considered: power plants of type 1 can be refueled while still operating. Power plants of type 2 need to be shut down from time to time, for refueling and ordinary maintenance (these are typically nuclear plants). Considering these two types of power plants, LSEM is the problem of optimizing production plans and scheduling of maintenances of type 2 plants, with the objective of keeping the production cost as low as possible, while fulfilling the customers demand. Uncertainty about the customers demand is taken into account in the model considered. In this article, a matheuristic optimization approach based on problem decomposition is proposed. The approach involves mixed integer linear programming and simulated annealing optimization methods. Computational results on some realistic instances are presented. This paper introduces a three-phase hybrid heuristic for a large-scale energy management and maintenance scheduling problem. The problem is to schedule maintenance periods and refueling amounts for nuclear power plants with a time horizon of up to five years, and handling a number of scenarios for future demand and prices. The goal is to minimize the expected total production cost. The first phase of the heuristic solves a constraint programming model of a simplified version of the problem, the second performs a local search, and the third handles overproduction in a greedy fashion. This work was initiated in the context of the ROADEF EURO Challenge 2010. In the concluding phase of the competition, our team ranked second in the junior category and sixth overall. After correcting a small implementation bug in the program that was submitted for final evaluation, our solver ranks first in the overall results from the competition.