Robust mixed integer linear programming; Application to the design of an hybrid system for electricity production

Dans cette thèse, nous nous intéressons à l’optimisation robuste. Plus précisément,nous nous intéresserons aux problèmes linéaires mixtes bi-niveaux, c’est à dire aux problèmes dans lesquels le processus de décision est divisé en deux parties : dans un premier temps, les valeurs optimales des variables dites "de décisions" seront calculées ; puis, une fois que l’incertitude sur les données est levée, nous calculerons les valeurs des variables dites "de recours". Dans cette thèse, nousnous limiterons au cas où les variables de deuxième étape, dites "de recours", sontcontinues.Dans la première partie de cette thèse, nous nous concentrerons sur l’étudethéorique de tels problèmes. Nous commencerons par résoudre un problème linéairesimplifié dans lequel l’incertitude porte seulement sur le membre droit descontraintes, et est modélisée par un polytope bien particulier. Nous supposerons enoutre que le problème vérifie une propriété dite "de recours complet", qui assureque, quelles que soient les valeurs prises par les variables de dcisions, si ces dernières sont admissibles, alors le problème admet toujours une solution réalisable, et ce, quelles que soient les valeurs prises par les paramètres incertains. Nous verrons alors une méthode permettant, à partir d’un programme robuste quelconque, de se ramener à un programme robuste équivalent dont le problème déterministe associévérifie la propriété de recours complet. Avant de traiter le cas général, nous nouslimiterons d’abord au cas o les variables de décisions sont entières. Nous testeronsalors notre approche sur un problème de production. Ensuite, après avoir remarquéque l’approche développée dans les chapitres précédents ne se généralisait pasnaturellement aux polytopes qui n’ont pas des points extrmes 0-1, nous montreronscomment, en utilisant des propriétés de convexité du problème, résoudre le problème robuste dans le cas général. Nous en déduirons alors des résultats de complexité sur le problème de deuxième étape, et sur le problème robuste. Dans la suite de cette partie nous tenterons d’utiliser au mieux les informations probabilistes que l’on a sur les données aléatoires pour estimer la pertinence de notre ensemble d’incertitude.Dans la deuxième partie de cette thèse, nous étudierons un problème de conceptionde parc hybride de production d’électricité. Plus précisément, nous chercheronsà optimiser un parc de production électrique constitué d’éoliennes, de panneauxsolaires, de batteries et d’un générateur à diesel, destiné à répondre à unedemande locale d’énergie électrique. Il s’agit de déterminer le nombre d’éoliennes,de panneaux solaires et de batteries à installer afin de répondre à la demande pourun cot minimum. Cependant, les données du problème sont très aléatoires. En effet,l’énergie produite par une éolienne dépend de la force et de la direction du vent ; celle produite par un panneau solaire, de l’ensoleillement et la demande en électricité peut tre liée à la température ou à d’autres paramètres extérieurs. Pour résoudre ce problème, nous commencerons par modéliser le problème déterministeen un programme linéaire mixte. Puis nous appliquerons directement l’approche de la première partie pour résoudre le problème robuste associé. Nous montrerons ensuite que le problème de deuxième étape associé, peut se résoudre en temps polynomial en utilisant un algorithme de programmation dynamique. Enfin, nous donnerons quelques généralisations et améliorations pour notre problème.Robust optimization is a recent approach to study problems with uncertain datathat does not rely on a prerequisite precise probability model but on mild assumptionson the uncertainties involved in the problem.We studied a linear two-stage robustproblem with mixed-integer first-stage variables and continuous second stagevariables. We considered column wise uncertainty and focused on the case whenthe problem doesn’t satisfy a "full recourse property" which cannot be always satisfied for real problems. We also studied the complexity of the robust problemwhich is NP-hard and proved that it is actually polynomial solvable when a parameterof the problem is fixed.We then applied this approach to study a stand-alonehybrid system composed of wind turbines, solar photovoltaic panels and batteries.The aim was to determine the optimal number of photovoltaic panels, wind turbinesand batteries in order to serve a given demand while minimizing the total cost of investment and use. We also studied some properties of the second stage problem, in particular that the second stage problem can be solvable in polynomial time using dynamic programming