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.
Le probleme de placement sur deux dimensions consiste a decider s'il existe un rangement d'objets rectangulaires dans une boite donnee. C'est un probleme combinatoire difficile (a la complexite du respect des capacites s'ajoute celle du positionnement des objets). Nous considerons les variantes sans rotation des objets et avec ou sans optimisation de la valeur des objets places. Nous menons une etude exploratoire des methodologies qui peuvent etre developpees a l'interface de la programmation mathematique, de l'optimisation combinatoire et de la theorie des graphes. Nous comparons les formulations de la litterature et en proposons de nouvelles. Nous developpons et testons deux approches de resolution innovantes. L'une est basee sur la decomposition de Dantzig-Wolfe (avec un branchement sur les contraintes disjonctives de non recouvrement des objets). L'autre constitue en une approche combinatoire basee sur diverses caracterisations des graphes d'intervalles (modelisant le chevauchement des objets selon chaque axe).