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
2807125841 2126662120 2963351303 1948613015
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. SAT solvers are often challenged with very hard problems that remain unsolved after hours of CPU time. The research community meets the challenge in two ways: (1) by improving the SAT solver technology, for example, perfecting heuristics for variable ordering, and (2) by inventing new ways of constructing simpler SAT problems, either using domain specific information during the translation from the original problem to CNF, or by applying a more universal CNF simplification procedure after the translation. This paper explores preprocessing of circuit-based SAT problems using recent advances in logic synthesis. Two fast logic synthesis techniques are considered: DAG-aware logic minimization and a novel type of structural technology mapping, which reduces the size of the CNF derived from the circuit. These techniques are experimentally compared to CNF-based preprocessing. The conclusion is that the proposed techniques are complementary to CNF-based preprocessing and speedup SAT solving substantially on industrial examples. In the period 1991–2015, algorithmic advances in Mixed Integer Optimization (MIO) coupled with hardware improvements have resulted in an astonishing 450 billion factor speedup in solving MIO problems. We present a MIO approach for solving the classical best subset selection problem of choosing k out of p features in linear regression given n observations. We develop a discrete extension of modern first-order continuous optimization methods to find high quality feasible solutions that we use as warm starts to a MIO solver that finds provably optimal solutions. The resulting algorithm (a) provides a solution with a guarantee on its suboptimality even if we terminate the algorithm early, (b) can accommodate side constraints on the coefficients of the linear regression and (c) extends to finding best subset solutions for the least absolute deviation loss function. Using a wide variety of synthetic and real datasets, we demonstrate that our approach solves problems with n in the 1000s and p in the 100s in minutes to provable optimality, and finds near optimal solutions for n in the 100s and p in the 1000s in minutes. We also establish via numerical experiments that the MIO approach performs better than Lasso and other popularly used sparse learning procedures, in terms of achieving sparse solutions with good predictive power. Lagrangian relaxation (LR) and general mixed integer programming (MIP) are two main approaches for solving unit commitment (UC) problems. This paper compares the LR and the state of art general MIP method for solving UC problems based on performance analysis and numerical testing. In this paper we have rigorously proved that UC is indeed an NP complete problem, and therefore it is impossible to develop an algorithm with polynomial computation time to solve it. In comparison with the general MIP methods, the LR methodology is more scaleable and efficient to obtain near optimal schedules for large scale and hard UC problems at the cost of a small percentage of deviation from the optimal solution. In particular, solving hydro generation subproblems within the LR framework can take advantages of both LR and general MIP methods and provide a synergetic combination of both approaches.