Letteratura scientifica selezionata sul tema "Optimisation Combinatoire Robuste et Probabiliste"

A cause du réchauffement climatique, le nombre et l’intensité des feux de forêts augmentent autour du globe. Dansce contexte, la construction de refuges contre le feu est une solution de plus en plus envisagée. Le problème consisteessentiellement à localiser p refuges de sorte à minimiser la distance maximale qui sépare un usager du plus procherefuge accessible en cas de feux. Le territoire considéré est divisé en zones et est modélisé comme un graphe auxarêtes pondérées. Un départ de feux sur une seule zone (c’est-à-dire sur un sommet). La principale conséquence d’unfeu est que les chemins d’évacuation sont modifiés de deux manières. Premièrement, un chemin d’évacuation ne peutpas traverser le sommet en feu. Deuxièmement, le fait qu’une personne proche de l’incendie puisse avoir un choix limitéde direction d’évacuation, ou être sous stress, est modélisé à l’aide d’une stratégie d’évacuation nouvellement définie.Cette stratégie d’évacuation induit des distances d’évacuation particulières qui rendent notre modèle spécifique. Selon letype de données considéré et l’objectif recherché, nous proposons deux problèmes avec ce modèle: le Robust p-CenterUnder Pressure et le Probabilistic p-Center Under Pressure. Nous prouvons que ces deux problèmes sont NP-difficilessur des classes de graphes pertinentes pour notre contexte. Nous proposons également des résultats d’approximationet d’inapproximation. Finalement, nous développons des algorithmes polynomiaux sur des classes de graphes simples,et nous développons des algorithmes mathématiques basés sur la programmation linéaire
The location of shelters in different areas threatened by wildfires is one of the possible ways to reduce fatalities in acontext of an increasing number of catastrophic and severe forest fires. The problem is basically to locate p sheltersminimizing the maximum distance people will have to cover to reach the closest accessible shelter in case of fire. Thelandscape is divided in zones and is modeled as an edge-weighted graph with vertices corresponding to zones andedges corresponding to direct connections between two adjacent zones. Each scenario corresponds to a fire outbreak ona single zone (i.e., on a vertex) with the main consequence of modifying evacuation paths in two ways. First, an evacuationpath cannot pass through the vertex on fire. Second, the fact that someone close to the fire may have limited choice, ormay not take rational decisions, when selecting a direction to escape is modeled using a new kind of evacuation strategy.This evacuation strategy, called Under Pressure, induces particular evacuation distances which render our model specific.We propose two problems with this model: the Robust p-Center Under Pressure problem and the Probabilistic p-CenterUnder Pressure problem. First we prove hardness results for both problems on relevant classes of graphs for our context.In addition, we propose polynomial exact algorithms on simple classes of graphs and we develop mathematical algorithmsbased on integer linear programming

La norme 3G/UMTS a permis de développer les premières applications multimédia pour téléphones et tablettes mobiles. Le nouveau standard 4G/LTE (Long Term Evolution) a pour objectif le très haut débit mobile. Dans ce standard, beaucoup d'efforts ont portés sur la reconfiguration automatique des réseaux en fonction de la demande des clients dans un processus appelé Self-Organizing Network (SON). Le travail de cette thèse s'inscrit dans cette direction. La reconfiguration de réseaux est comprise principalement dans le sens des modèles, des méthodes et des outils pour analyser les indicateurs remontés du réseau et configurer automatiquement les paramètres. Nous avons essentiellement travaillé sur les paramètres des aériens, l'allocation des fréquences, des puissances d'émission et des inclinaisons verticales.Dans cette optique, étant donné la forte variabilité des données d'entrée de l'optimisation issues des remontées de réseau, cette thèse porte sur les modèles et algorithmes d'optimisation robuste dans le contexte de l'optimisation sous contraintes. L'optimisation robuste fait référence à un ensemble de procédés pour proposer des solutions à des problèmes combinatoires dans un contexte de données incertaines et de scénarios variables dans le temps. Une première partie est dédiée à l'état de l'art et présente les principes des Self-Organizing Network (SON). La deuxième partie est consacrée à l'état de l'art des méthodes en optimisation robuste. En troisième partie nous présentons la modélisation mathématique du problème d'optimisation pour lequel les données de trafic (répartitions des clients sur la zone de service et leurs demandes respectives) prennent des valeurs variables dans le temps. Une phase de diagnostic sur le fonctionnement du réseau à partir des données, et une étude de sensibilité des solutions vis-à-vis des variations dans la réalisation des données ont été faites en quatrième partie avec des algorithmes de recherche locale. La cinquième partie présente le travail de conception, développement et test sur scénarios, d'une Recherche Tabou ainsi qu'une analyse approfondie sur les méthodes de pilotage envisagées pour les SON en 4G.

Les roues aubagées sont des composants dont le comportement dynamique est très sensible au désaccordage involontaire causé par les tolérances de fabrication qui rendent les aubes légèrement différentes les unes des autres. Cette sensibilité se traduit généralement par une amplification des vibrations. L'objectif de ce travail de recherche est de proposer de nouvelles méthodologies permettant d'optimiser la conception en vibration des roues aubagées vis à vis du désaccordage involontaire. L'optimisation est faite pour la réponse forcée et sous une contrainte de marge à la stabilité aéroélastique. Dans ce contexte, le désaccordage intentionnel par modification géométrique des aubes est utilisé. Pour réduire les temps de calcul, une nouvelle méthode de réduction de modèles de roues aubagées désaccordées intentionnellement par modification géométrique est développée et validée. La modélisation des incertitudes incluant le désaccordage involontaire, est faite avec une approche probabiliste non paramétrique. Une application à l'optimisation de la conception en vibration d'une roue réelle a finalement été effectuée en deux phases : (1) une optimisation de la répartition des différentes aubes désaccordées intentionnellement sur la roue aubagée et (2) une optimisation du niveau de modification géométrique de ces aubes. Les résultats montrent qu'une conception robuste par désaccordage intentionnel de la roue aubagée a été effectuée

L’analyse des tolérances a pour but de vérifier lors de la phase de conception, l’impact des tolérances individuelles sur l’assemblage et la fonctionnalité d’un système mécanique. Les produits fabriqués possèdent différents types de contacts et sont sujets à des imperfections de fabrication qui sont sources de défaillances d’assemblage et fonctionnelle. Les méthodes généralement proposées pour l’analyse des tolérances ne considèrent pas les défauts de forme. L’objectif des travaux de thèse est de proposer une nouvelle procédure d’analyse des tolérances permettant de prendre en compte les défauts de forme et le comportement géométriques des différents types de contacts. Ainsi, dans un premier temps, une méthode de modélisation des défauts de forme est proposée afin de rendre les simulations plus réalistes. Dans un second temps, ces défauts de forme sont intégrés dans la modélisation du comportement géométrique d’un système mécanique hyperstatique, en considérant les différents types de contacts. En effet, le comportement géométrique des différents types de contacts est différent dès que les défauts de forme sont considérés. La simulation de Monte Carlo associée à une technique d’optimisation est la méthode choisie afin de réaliser l’analyse des tolérances. Cependant, cette méthode est très couteuse en temps de calcul. Pour pallier ce problème, une approche utilisant des modèles probabilistes obtenus grâce à l’estimation par noyaux, est proposée. Cette nouvelle approche permet de réduire les temps de calcul de manière significative
Tolerance analysis aims toward the verification of the impact of individual tolerances on the assembly and functional requirements of a mechanical system. The manufactured products have several types of contacts and their geometry is imperfect, which may lead to non-functioning and non-assembly. Traditional methods for tolerance analysis do not consider the form defects. This thesis aims to propose a new procedure for tolerance analysis which considers the form defects and the different types of contact in its geometrical behavior modeling. A method is firstly proposed to model the form defects to make realistic analysis. Thereafter, form defects are integrated in the geometrical behavior modeling of a mechanical system and by considering also the different types of contacts. Indeed, these different contacts behave differently once the imperfections are considered. The Monte Carlo simulation coupled with an optimization technique is chosen as the method to perform the tolerance analysis. Nonetheless, this method is subject to excessive numerical efforts. To overcome this problem, probabilistic models using the Kernel Density Estimation method are proposed

La programmation par contraintes est une approche régulièrement utilisée pour traiter des problèmes d’ordonnancement variés. Les problèmes d’ordonnancement cumulatifs représentent une classe de problèmes dans laquelle des tâches non morcelable peuvent être effectuées en parallèle. Ces problèmes apparaissent dans de nombreux contextes réels, tels que par exemple l’allocation de machines virtuelles ou l’ordonnancement de processus dans le "cloud", la gestion de personnel ou encore d’un port. De nombreux mécanismes ont été adaptés et proposés en programmation par contraintes pour résoudre les problèmes d’ordonnancement. Les différentes adaptations ont abouti à des raisonnements qui semblent à priori significativement distincts. Dans cette thèse nous avons effectué une analyse détaillée des différents raisonnements, proposant à la fois une notation unifiée purement théorique mais aussi des règles de dominance, permettant une amélioration significative du temps d’exécution d’algorithmes issus de l’état de l’art, pouvant aller jusqu’à un facteur sept. Nous proposons aussi un nouveau cadre de travail pour l’ordonnancement cumulatif robuste, permettant de trouver des solutions supportant qu’à tout moment une ou plusieurs tâches soit retardées, sans remise en cause de l’ordonnancement généré et en gardant une date de fin de projet satisfaisante. Dans ce cadre, nous proposons une adaptation d’un algorithme de l’état de l’art, Dynamic Sweep
Constraint programming is an approach regularly used to treat a variety of scheduling problems. Cumulative scheduling problems represent a class of problems in which non-preemptive tasks can be performed in parallel. These problems appear in many contexts, such as for example the allocation of virtual machines, the ordering process in the "cloud", personnel management or a port. Many mechanisms have been adapted and offered in constraint programming to solve scheduling problems. The various adaptations have resulted in reasoning that appear a priori significantly different. In this thesis we performed a detailed analysis of the various arguments, offering both a theoretical unified caracterization but also dominance rules, allowing a significant improvement in execution time of algorithms from the state of the art, up to a factor of seven. we also propose a new framework for robust cumulative scheduling, to find solutions that support at any time one or more tasks to be delayed while keeping a satisfactory end date of the project and without calling into question the generated scheduling. In this context, we propose an adaptation of an algorithm of the state of the art, Dynamic Sweep

La conception des ouvrages en Génie Civil se fait habituellement de manière semi-probabiliste en employant des valeurs caractéristiques auxquelles sont associées des facteurs partiels de sécurité. Toutefois, de telles approches ne permettent pas de garantir la robustesse de l’ouvrage conçu vis-à-vis des sources d’incertitudes susceptibles d’affecter ses performances au cours de sa réalisation et de son fonctionnement. Nous proposons dans ce mémoire une méthodologie d’aide à la décision pour la conception robuste des ouvrages qui est appliquée à une structure métallique reposant sur des fondations superficielles. La conception de cet ouvrage est conduite en intégrant le phénomène d’interaction sol-structure qui implique que les choix de conception faits sur la fondation influencent ceux faits sur la structure supportée (et réciproquement). La démarche de conception proposée fait appel à des outils d’optimisation multi-objectif et d’aide à la décision afin d’obtenir une solution qui offre le meilleur compromis entre l’ensemble des préférences énoncées par le décideur sur chaque critère de conception. Des analyses de sensibilité sont menées parallèlement dans le but d’identifier et de quantifier les sources d’incertitude les plus influentes sur la variabilité des performances de l’ouvrage. Ces sources d’incertitude représentées sous une forme probabiliste sont intégrées dans la procédure de conception et propagées à l’aide d’une méthode d’échantillonnage par hypercube latin. Une partie du mémoire est consacrée à l’analyse des effets de l’incertitude relative à la modélisation des paramètres géotechniques sur la réponse de l’ouvrage et sur la démarche plus globale d’optimisation
Design in Civil Engineering is usually performed in a semi-probabilistic way using characteristic values which are associated with partial safety factors. However, this approach doesn’t guarantee the structure robustness with regard to uncertainties that could affect its performance during construction and operation. In this thesis, we propose a decision aid methodology for robust design of steel frame on spread foundations. Soil-structure interaction is taken into consideration in the design process implying that the design choices on foundations influence the design choices on steel frame (and vice versa). The proposed design approach uses multi-objective optimization and decision aid methods in order to obtain the best solution with respect to the decision-maker’s preferences on each criterion. Furthermore, sensitivity analyzes are performed in order to identify and quantify the most influencing uncertainty sources on variability of the structure performances. These uncertainties are modeled as random variables and propagated in the design process using latin hypercube sampling. A part of this dissertation is devoted to the effects of uncertainties involved in soil properties on the structure responses and on the design global approach

La présente thèse a pour objet d’explorer les potentialités d’une méthode prometteuse de l’optimisation conique, la programmation semi-définie positive (SDP), pour les problèmes de management d’énergie, à savoir relatifs à la satisfaction des équilibres offre-demande électrique et gazier.Nos travaux se déclinent selon deux axes. Tout d’abord nous nous intéressons à l’utilisation de la SDP pour produire des relaxations de problèmes combinatoires et quadratiques. Si une relaxation SDP dite « standard » peut être élaborée très simplement, il est généralement souhaitable de la renforcer par des coupes, pouvant être déterminées par l'étude de la structure du problème ou à l'aide de méthodes plus systématiques. Nous mettons en œuvre ces deux approches sur différentes modélisations du problème de planification des arrêts nucléaires, réputé pour sa difficulté combinatoire. Nous terminons sur ce sujet par une expérimentation de la hiérarchie de Lasserre, donnant lieu à une suite de SDP dont la valeur optimale tend vers la solution du problème initial.Le second axe de la thèse porte sur l'application de la SDP à la prise en compte de l'incertitude. Nous mettons en œuvre une approche originale dénommée « optimisation distributionnellement robuste », pouvant être vue comme un compromis entre optimisation stochastique et optimisation robuste et menant à des approximations sous forme de SDP. Nous nous appliquons à estimer l'apport de cette approche sur un problème d'équilibre offre-demande avec incertitude. Puis, nous présentons une relaxation SDP pour les problèmes MISOCP. Cette relaxation se révèle être de très bonne qualité, tout en ne nécessitant qu’un temps de calcul raisonnable. La SDP se confirme donc être une méthode d’optimisation prometteuse qui offre de nombreuses opportunités d'innovation en management d’énergie
The present thesis aims at exploring the potentialities of a powerful optimization technique, namely Semidefinite Programming, for addressing some difficult problems of energy management. We pursue two main objectives. The first one consists of using SDP to provide tight relaxations of combinatorial and quadratic problems. A first relaxation, called “standard” can be derived in a generic way but it is generally desirable to reinforce them, by means of tailor-made tools or in a systematic fashion. These two approaches are implemented on different models of the Nuclear Outages Scheduling Problem, a famous combinatorial problem. We conclude this topic by experimenting the Lasserre's hierarchy on this problem, leading to a sequence of semidefinite relaxations whose optimal values tends to the optimal value of the initial problem.The second objective deals with the use of SDP for the treatment of uncertainty. We investigate an original approach called “distributionnally robust optimization”, that can be seen as a compromise between stochastic and robust optimization and admits approximations under the form of a SDP. We compare the benefits of this method w.r.t classical approaches on a demand/supply equilibrium problem. Finally, we propose a scheme for deriving SDP relaxations of MISOCP and we report promising computational results indicating that the semidefinite relaxation improves significantly the continuous relaxation, while requiring a reasonable computational effort.SDP therefore proves to be a promising optimization method that offers great opportunities for innovation in energy management

Cette thèse comporte deux parties majeures : la première partie est dédiée à l'étude du problème sparse CARP déterministe où nous avons développé une transformation du sparse CARP en un sparse CVRP. La seconde est consacrée au problème sparse CARP avec coûts sous incertitude. Nous avons donné une formulation mathématique du problème en min-max. Cette modélisation a permis d'identifier le pire scénario pour le problème robuste. Deux approches algorithmiques ont été proposées pour une résolution approchée
This dissertation consists of two main parts : in the first part, we study the detreministic capacitated arc routing problem over sparse underlying graphs wher we have developed a new transformation techniquevof sparse CARP into sparse CVRP. The second part is consecrated about the sparse CARP with travel costs uncertainty. We have given a mathematical formulation of the probleme in min-max. A worst scenario for the robust problem is then identified, and two algorithmic approaches are proposed to determine a solution of the studied problem

Cette thèse s'intéresse à la résolution de très grands problèmes d'optimisation combinatoire stochastique. Les recherches sont appliquées au problème de planification des arrêts pour rechargement des centrales nucléaires. Compte-tenu de la part prépondérante de celles-ci dans le mix-électrique, ce problème structure fortement la chaîne de management d’énergie d'EDF. Une première partie propose une formulation étendue bi-niveau dans laquelle les décisions de premier niveau fixent les plannings d’arrêt et des profils de production des centrales, et celles de second niveau évaluent le coût de satisfaction de la demande associé. Cette formulation permet la résolution à l'optimum d'instances industrielles déterministes par un solveur en PLNE. Dans le cas stochastique, une telle résolution directe du problème n'est plus possible. Nous proposons une formulation permettant d’en résoudre la relaxation linéaire par génération de colonnes et de coupes, correspondant respectivement aux reformulations de Danzig-Wolfe du premier niveau et de Benders du second. Une phase heuristique permet ensuite de déterminer des solutions entières de bonne qualité pour des instances, jusqu'à une cinquantaine de scénarios représentatifs de l’incertitude sur les données. L’apport de l’approche est estimé en utilisant les outils industriels exploités par EDF pour évaluer les plannings. Une seconde partie porte sur l'intégration de méthodes d'optimisation robuste pour la prise en compte d’aléas sur la disponibilité des centrales. Nous nous plaçons dans un cadre où les recours possibles sur les dates d'arrêts ne sont pas exercés. Nous comparons des méthodes bi-objectif et probabiliste permettant de rendre le planning robuste pour les contraintes opérationnelles dont la relaxation est envisageable. Pour les autres, nous proposons une méthode basée sur un budget d’incertitude. Cette méthode permet de renforcer la stabilité du planning en limitant les besoins de réorganisation futurs. La prise en compte d’une loi de probabilité de l’aléa permet d’affiner le contrôle du prix de cette robustesse
The purpose of this Ph.D. thesis is to study optimization techniques for large-scale stochastic combinatorial problems. We apply those techniques to the problem of scheduling EDF nuclear power plant maintenance outages, which is of significant importance due to the major part of the nuclear energy in the French electricity system. We build on a two-stages extended formulation, the first level of which fixes nuclear outage dates and production profiles for nuclear plants, while the second evaluates the cost to meet the demand. This formulation enables the solving of deterministic industrial instances to optimality, by using a MIP solver. However, the computational time increases significantly with the number of scenarios. Hence, we resort to a procedure combining column generation of a Dantzig-Wolfe decomposition with Benders’ cut generation, to account for the linear relaxation of stochastic instances. We then obtain integer solutions of good quality via a heuristic, up to fifty scenarios. We further assume that outage durations are uncertain and that unexpected shutdowns of plants may occur. We investigate robust optimization methods in this context while ignoring possible recourse on power plants outage dates. We report on several approaches, which use bi-objective or probabilistic methods, to ensure the satisfaction of constraints which might be relaxed in the operating process. For other constraints, we apply a budget uncertainty-based approach to limit future re-organizations of the scheduling. Adding probabilistic information leads to better control of the price of the robustness