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.
Several MIP based approaches noticed that scheduling constraints from CT14 to CT21 are modeled efficiently with MIP formulations using time indexed formulation of constraints. Jost and Savourey (2013) used only these constraints in a two stage heuristic, computing production and stock levels for solutions of the high level scheduling MIP with constraints CT13 to CT21 @cite_1 . Such formulation cannot provide dual bounds for the Challenge ROADEF because it does not model the production costs. Solving MIP problems with scheduling constraints CT13 to CT21 and only binaries for outage dates in @cite_1 induce fast resolutions for all the instances of the Challenge.
@cite_1
2036434250
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.