Scheduling the maintenances of nuclear power plants is a complex optimization problem, formulated in 2-stage stochastic programming for the EURO ROADEF 2010 challenge. The first level optimizes the maintenance dates and refueling decisions. The second level optimizes the production to fulfill the power demands and to ensure feasibility and costs of the first stage decisions. This paper solves a deterministic version of the problem, studying Mixed Integer Programming (MIP) formulations and matheuristics. Relaxing only two sets of constraints of the ROADEF challenge, a MIP formulation can be written using only binary variables for the maintenance dates. The MIP formulations are used to design constructive matheuristics and a Variable Neighborhood Descent (VND) local search. These matheuristics produce very high quality solutions. Some intermediate results explains results of the Challenge: the relaxation of constraints CT6 are justified and neighborhood analyses with MIP-VND justifies the choice of neighborhoods to implement for the problem. Lastly, an extension with stability costs for monthly reoptimization is considered, with efficient bi-objective matheuristics.
Les recherches presentees dans cette these portent sur la modelisation et la resolution de systemes de contraintes, en considerant aussi bien l'aspect theorique que l'aspect pratique. La partie theorique a comme objectif de proposer des methodes generiques qui exploitent des techniques de la Programmation Par Contraintes et de la Programmation Mathematique pour modeliser et resoudre des systemes de contraintes binaires. Nous avons propose une formulation lineaire agregee pour les CSP binaires et une methode de filtrage combinant la relaxation Lagrangienne et la consistance d'arc. Pour les CSP sur-contraints, nous avons introduit la notion d'inegalite binaire valide. Nous avons egalement montre comment exploiter cette notion pour ameliorer les bornes inferieures qui se basent sur la consistance d'arc et proposer de nouvelles bornes inferieures ainsi qu'une technique de pretraitement de WCSP. Dans la partie appliquee, nous avons traite le probleme de placement des arrets et de la production des reacteurs nuclaires d'Electricite de Fance(EDF). Nous avons ameliore la modelisation mathematique actuelle de certaines contraintes du probleme et nous avons propose une nouvelle modelisation en Programmation Par Contraintes pour tout le probleme. Nous avons, par la suite, concu le solveur OSOPAN pour la satisfaction et l'optimisation de ce probleme. Ce solveur fait cooperer la Programmation Par Contraintes, la Programmation Mathematique ainsi que la Recherche Locale.