  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.
