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.
Two matheuristic approaches were designed for the ROADEF Challenge. A simplified MIP problem is solved, and the solution is repaired to ensure the feasibility for all the constraints and computing the cost in the full model. In both cases, the MIP model is solved heuristically using truncated exact methods, the simplified MIP being too difficult to be solved in one hour. We note that (2010) provided an exact and compact MIP formulation for the full problem, introducing binaries for all time steps, cycle and production mode @math @cite_8 . This size of problem is not reasonable for a B &B search, even in a truncated mode, this work was a preliminary work before a Column Generation (CG) work similar with @cite_6 .
@cite_6 @cite_8
2059695025 1583833469
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. 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).