Modélisation et résolution de grands problèmes stochastiques combinatoires, application à deux problèmes de gestion de production d’électricité

Autor: Dupin, Nicolas
Přispěvatelé: Université de Lille, Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Université Lille 1 - Sciences et Technologies, Talbi El-Ghazali(talbi@lifl.fr)
Jazyk: francouzština
Rok vydání: 2015
Předmět:
Zdroj: Informatique [cs]. Université Lille 1-Sciences et Technologies, 2015. Français
Popis: Mixed Integer Linear Programming (MILP) is a very popular and useful framework to model industrial optimization problems. A reason of this success comes with the facility to model complex optimization problems, with numerous sets of constraints and variables including discrete variables. The work can be focused on modeling, with a black box generic resolution with the tree search algorithm Branch&Bound(B&B). The drawback is that resolution is usually limited, dealing with real world size instances. To solve big size instances of optimizations problems, heuristic and meta-heuristic methods are commonly used to find good quality solutions, using special structures of optimization problems. These approaches are focused on finding quickly good quality solutions, without any guarantee to reach the optimum. This paper addresses complex industrial problems described with a MILP formulation. We develop a methodology to combine Variable Neighborhood Search (VNS) and Branch&Bound(B&B) resolution, where B&B resolution is operated inside a VND Local Search. Key point is the neighborhoods definition. The approach allows to define numerous types of large neighborhoods, for an efficient application of VNS framework. Neighborhoods from the generic MILP primal heuristics can be incorporated in our scheme, as well as specific neighborhoods using specific structures of the problem. This approach was successfully applied on two energy management problems, with different structures and resolution characteristics. First application is a daily Unit Commitment Problem of thermal power plants with specific dynamic constraints. Second application comes from the EURO/ROADEF 2010 challenge, scheduling of nuclear power plants’ outages for maintenances and refueling, a big size industrial problem. In both applications, VND scheme allowed to increase the resolution limits of B&B resolution method, improving quickly primal solutions found with the MILP resolution after a long resolution time.; Le formalisme de la Programmation Linéaire en Nombres Entiers (PLNE) est couramment utilisé dans le monde industriel pour modéliser des problèmes d’optimisation complexes. Ce succès provient de la facilité à modéliser globalement des problèmes d’optimisation avec de nombreux jeux de contraintes et de variables décisionnelles dont des variables discrètes. La résolution générique en PLNE par l’algorithme deBranch&Bound permet de concentrer le travail sur les questions de modélisation, pour une résolution de type boı̂te noire. Malgré les importants progrès réalisés par la PLNE ces dernières décennies, la résolution est souvent limitée pour des problèmes de taille réelle. Les méthodes heuristiques sont alors utilisées pour trouver des solutions de bonne qualité sans preuve d’optimalité, ni même de majoration de l’écart à lasolution optimale.Il était question d’étudier les limites de la résolution exacte et des heuristiques sur des problèmes industriels d’optimisation d’EDF R&D à modéliser en PLNE, en vue de leur insertion dans le processus décisionnel opérationnel. L’application principale concerne la planification des arrêts de maintenance et de rechargement des centrales nucléaires, qui a fait l’objet du Challenge EURO/ROADEF 2010. Nous avons aussi traité un problème discrétisé de production journalière d’un parc thermique à flamme. Ces deux problèmes d’applications ont des structures et des caractéristiques de résolution frontale Branch&Bound très différentes. La méthodologie suivie est analogue pour les deux cas. On modélise tout d’abord le problème avec une formulation compacte PLNE, pour en analyser les limites de la résolution frontale par Branch&Bound. Des méthodes de décomposition peuvent alors être étudiées. On dérive ensuite les méthodes exactes en matheuristiques pour résoudre des instances de taille réelle. Dans cette optique, l’hybridation de Variable Neighborhood Search (VNS) avec des voisinages définis par PLNE a donné des résultats très probants sur les deux problèmes en termes de qualités de solutions. Le fait d’avoir travaillé avec des méthodes exactes a permis également de chiffrer l’impact d’hypothèses de résolution, de répondre à des considérations opérationnelles, mais également d’obtenir des bornes inférieures. Pour le problème du Challenge EURO/ROADEF 2010, nous avons pu obtenir des bornes qui amélioraient les meilleurs bornes de l’état de l’art.
Databáze: OpenAIRE
Externí odkaz: