Le problème généralisé des moments (PGM) est un problème d'optimisation linéaire sur des espaces de mesures. Il permet de modéliser simplement un grand nombre d'applications. En toute généralité il est impossible à résoudre mais si ses données sont des polynômes et des ensembles semi-algébriques alors on peut définir une hiérarchie de relaxations semidéfinies (SDP) - la hiérarchie moments-sommes-de-carrés (moments-SOS) - qui permet en principe d'approcher la valeur optimale avec une précision arbitraire. Le travail contenu dans cette thèse adresse deux facettes concernants le PGM et la hiérarchie moments-SOS: Une première facette concerne l'évolution des relaxations SDP pour le PGM. Le degré des poids SOS dans la hiérarchie moments-SOS augmente avec l'ordre de relaxation. Lorsque le nombre de variables n'est pas modeste, on obtient rapidement des programmes SDP de taille trop grande pour les logiciels de programmation SDP actuels, sauf si l'on peut utiliser des symétries ou une parcimonie structurée souvent présente dans beaucoup d'applications de grande taille. On présente donc un nouveau certificat de positivité sur un compact semi-algébrique qui (i) exploite la parcimonie présente dans sa description, et (ii) dont les polynômes SOS ont un degré borné à l'avance. Grâce à ce nouveau certificat on peut définir une nouvelle hiérarchie de relaxations SDP pour le PGM qui exploite la parcimonie et évite l'explosion de la taille des matrices semidéfinies positives liée au degré des poids SOS dans la hiérarchie standard. Une deuxième facette concerne (i) la modélisation de nouvelles applications comme une instance particulière du PGM, et (ii) l'application de la méthodologie moments-SOS pour leur résolution. En particulier on propose des approximations déterministes de contraintes probabilistes, un problème difficile car le domaine des solutions admissibles associées est souvent non-convexe et même parfois non connecté. Dans notre approche moments-SOS le domaine admissible est remplacé par un ensemble plus petit qui est le sous-niveau d'un polynôme dont le vecteur des coefficients est une solution optimale d'un certain SDP. La qualité de l'approximation (interne) croît avec le degré du polynôme et la taille du SDP. On illustre cette approche dans le problème du calcul du flux de puissance optimal dans les réseaux d'énergie, une application stratégique où la prise en compte des contraintes probabilistes devient de plus en plus cruciale (e.g., pour modéliser l'incertitude liée á l'énergie éolienne et solaire). En outre on propose une extension des cette procedure qui est robuste à l'incertitude sur la distribution sous-jacente. Des garanties de convergence sont fournies. Une deuxième contribution concerne l'application de la méthodologie moments-SOS pour l'approximation de solutions généralisés en commande optimale. Elle permet de capturer le comportement limite d'une suite minimisante de commandes et de la suite de trajectoires associée. On peut traiter ainsi le cas de phénomènes simultanés de concentrations de la commande et de discontinuités de la trajectoire. Une troisième contribution concerne le calcul de solutions mesures pour les lois de conservation hyperboliques scalaires dont l'exemple typique est l'équation de Burgers. Cette classe d'EDP non linéaire peut avoir des solutions discontinues difficiles à approximer numériquement avec précision. Sous certaines hypothèses, la solution mesurepeut être identifiée avec la solution classique (faible) à la loi de conservation. Notre approche moment-SOS fournit alors une méthode alternative pour approcher des solutions qui contrairement aux méthodes existantes évite une discrétisation du domaine. / The generalized moment problem (GMP) is a linear optimization problem over spaces of measures. It allows to model many challenging mathematical problems. While in general it is impossible to solve the GMP, in the case where all data are polynomial and semialgebraic sets, one can define a hierarchy of semidefinite relaxations - the moment-sums-of-squares (moment-SOS) hierachy - which in principle allows to approximate the optimal value of the GMP to arbitrary precision. The work presented in this thesis addresses two facets concerning the GMP and the moment-SOS hierarchy: One facet is concerned with the scalability of relaxations for the GMP. The degree of the SOS weights in the moment-SOS hierarchy grows when augmenting the relaxation order. When the number of variables is not small, this leads quickly to semidefinite programs (SDPs) that are out of range for state of the art SDP solvers, unless one can use symmetries or some structured sparsity which is typically present in large scale applications. We provide a new certificate of positivity which (i) is able to exploit the structured sparsity and (ii) only involves SOS polynomials of fixed degree. From this, one can define a new hierarchy of SDP relaxations for the GMP which can take into account sparsity and at the same time prevents from explosion of the size of SDP variables related to the increasing degree of the SOS weights in the standard hierarchy. The second facet focusses on (i) modelling challenging problems as a particular instance of the GMP and (ii) solving these problems by applying the moment-SOS hierarchy. In particular we propose deterministic approximations of chance constraints a difficult problem as the associated set of feasible solutions is typically non-convex and sometimes not even connected. In our approach we replace this set by a (smaller) sub-level-set of a polynomial whose vector of coefficients is a by-product of the moment-SOS hierarchy when modeling the problem as an instance of the GMP. The quality of this inner approximation improves when increasing the degree of the SDP relaxation and asymptotic convergence is guaranteed. The procedure is illustrated by approximating the feasible set of an instance of the chance-constrained AC Optimal Power Flow problem (a nonlinear problem in the management of energy networks) which nowadays becomes more and more important as we rely increasingly on uncertain energy sources such as wind and solar power. Furthermore, we propose an extension of this framework to the case where the underlying distribution itself is uncertain and provide guarantees of convergence. Another application of the moment-SOS methodology discussed in this thesis consider measure valued solutions to optimal control problems. We show how this procedure can capture the limit behavior of an optimizing sequence of control and its corresponding sequence of trajectories. In particular we address the case of concentrations of control and discontinuities of the trajectory may occur simultaneously. In a final contribution, we compute measure valued solutions to scalar hyperbolic conservation laws, such as Burgers equation. It is known that this class of nonlinear partial differential equations has potentially discontinuous solutions which are difficult to approximate numerically with accuracy. Under some conditions the measure valued solution can be identified with the classical (weak) solution to the conservation law. In this case our moment-SOS approach provides an alternative numerical scheme to compute solutions which in contrast to existing methods, does not rely on discretization of the domain.

No description available.

The submitted thesis studies penalty function methods for stochastic programming problems. The main objective of the paper is to examine penalty function methods for deterministic nonlinear programming, in particular exact penalty function methods, in order to enhance penalty function methods for stochastic programming. For this purpose, the equivalence of the original de- terministic nonlinear and the corresponding penalty function problem using arbi- trary vector norm as the penalty function is shown for convex and invex functions occurring in the problems, respectively. The obtained theorems are consequently applied to multiple chance constrained problems under finite discrete probability distribution to show the asymptotic equivalence of the probabilistic and the cor- responding penalty function problems. The practical use of the newly obtained methods is demonstrated on a numerical study, in which a comparison with other approaches is provided as well. 1

Notre société étant plus dépendante que jamais au vecteur électrique, la moindre perturbation du transport ou de l’acheminement de l’électricité a un impact social et économique important. La fiabilité et la sécurité des réseaux électriques sont donc cruciales pour les gestionnaires de réseaux, en plus des aspects économiques. De plus, les réseaux de transport sont interconnectés pour réduire les coûts des opérations et pour améliorer la sécurité. Un des plus grand défis des gestionnaires des réseaux de transport est ainsi de se coordonner avec les réseaux voisins, ce qui soulève des problèmes liés à la taille du problème, à l’interopérabilité et à la confidentialité des données.Cette thèse se focalise principalement sur la sécurité des opérations sur les réseaux électriques, c’est pourquoi l’évolution des principales caractéristiques des blackouts, qui sont des échecs de la sécurité des réseaux, sont étudiés sur la période 2005-2016. L’approche de cette étude consiste à déterminer quelles sont les principales caractéristiques des incidents de ces 10 dernières années, afin d’identifier ce qui devrait être intégré pour réduire le risque que ces incidents se reproduisent. L’évolution a été étudiée et comparé avec les caractéristiques des blackouts qui se sont produit avant 2005. L’étude se focalise sur les préconditions qui ont mené à ces blackouts et sur les cascades, et particulièrement sur le rôle de la vitesse des cascades. Les caractéristiques importante sont extraites et intégrées dans la suite de notre travail.Un algorithme résolvant un problème préventif d’Optimal Power Flow avec contraintes de sécurité (SCOPF) de manière distribuée est ainsi développé. Ce problème consiste en l’ajout de contraintes qui assure qu’après la perte de n’importe quel appareil d’importance, le nouveau point d’équilibre, atteint suite au réglage primaire en fréquence, respecte les contraintes du système. L’algorithme développé utilise une décomposition fine du problème et est implémenté sous le paradigme multi-agent, basé sur deux catégories d’agents : les appareils et les bus. Les agents sont coordonnés grâce à l’ « Alternating Direction Method of Multipliers (ADMM)» et grâce à un problème de consensus. Cette décomposition procure l’autonomie et la confidentialité nécessaire aux différents acteurs du système, mais aussi, un bon passage à l’échelle par rapport à la taille du problème. Cet algorithme a aussi pour avantage d’être robuste à n’importe quelle perturbation, incluant la séparation du système en plusieurs régions.Puis, pour prendre en compte l’incertitude sur la production créée par les erreurs de prédiction des fermes éoliennes, une approche distribuée à deux étapes est développée pour résoudre un problème d’Optimal Power Flow avec contraintes probabilistes (CCOPF), d’une manière complétement distribuée. Les erreurs de prédiction des fermes éoliennes sont modélisées par des lois normales indépendantes et les écarts par rapport aux plannings de production sont considérés compensés par le réglage primaire en fréquence. La première étape de l’algorithme a pour but de déterminer des paramètres de sensibilités nécessaires pour formuler le problème. Les résultats de cette étape sont ensuite des paramètres d’entrée de la seconde étape qui, elle, résout le problème de CCOPF. Une extension de cette formulation permet d’ajouter de la flexibilité au problème en permettant la réduction de la production éolienne. Cet algorithme est basé sur la même décomposition fine que précédemment où les agents sont également coordonnés par l’ADMM et grâce à un problème de consensus. En conclusion, cet algorithme en deux étapes garantit la confidentialité et l’autonomie des différents acteurs, et est parallèle et adaptée aux plateformes hautes performances. / Our societies are more dependent on electricity than ever, thus any disturbance in the power transmission and delivery has major economic and social impact. The reliability and security of power systems are then crucial to keep, for power system operators, in addition to minimizing the system operating cost. Moreover, transmission systems are interconnected to decrease the cost of operation and improve the system security. One of the main challenges for transmission system operators is therefore to coordinate with interconnected power systems, which raises scalability, interoperability and privacy issues. Hence, this thesis is concerned with how TSOs can operate their networks in a decentralized way but coordinating their operation with other neighboring TSOs to find a cost-effective scheduling that is globally secure.The main focus of this thesis is the security of power systems, this is why the evolution of the main characteristics of the blackouts that are failures in power system security, of the period 2005-2016 is studied. The approach consists in determining what the major characteristics of the incidents of the past 10 years are, to identify what should be taken into account to mitigate the risk of incidents. The evolution have been studied and compared with the characteristics of the blackouts before 2005. The study focuses on the pre-conditions that led to those blackouts and on the cascades, and especially the role of the cascade speed. Some important features are extracted and later integrated in our work.An algorithm that solve the preventive Security Constrained Optimal Power Flow (SCOPF) problem in a fully distributed manner, is thus developed. The preventive SCOPF problem consists in adding constraints that ensure that, after the loss of any major device of the system, the new steady-state reached, as a result of the primary frequency control, does not violate any constraint. The developed algorithm uses a fine-grained decomposition and is implemented under the multi-agent system paradigm based on two categories of agents: devices and buses. The agents are coordinated with the Alternating Direction method of multipliers in conjunction with a consensus problem. This decomposition provides the autonomy and privacy to the different actors of the system and the fine-grained decomposition allows to take the most of the decomposition and provides a good scalability regarding the size of the problem. This algorithm also have the advantage of being robust to any disturbance of the system, including the separation of the system into regions.Then, to account for the uncertainty of production brought by wind farms forecast error, a two-step distributed approach is developed to solve the Chance-Constrained Optimal Power Flow problem, in a fully distributed manner. The wind farms forecast errors are modeled by independent Gaussian distributions and the mismatches with the initials are assumed to be compensated by the primary frequency response of generators. The first step of this algorithm aims at determining the sensitivity factors of the system, needed to formulate the problem. The results of this first step are inputs of the second step that is the CCOPF. An extension of this formulation provides more flexibility to the problem and consists in including the possibility to curtail the wind farms. This algorithm relies on the same fine-grained decomposition where the agents are again coordinated by the ADMM and a consensus problem. In conclusion, this two-step algorithm ensures the privacy and autonomy of the different system actors and it is de facto parallel and adapted to high performance platforms.

L'incertitude est une propriété naturelle des systèmes complexes. Les paramètres de certains modèles peuvent être imprécis; la présence de perturbations aléatoires est une source majeure d'incertitude pouvant avoir un impact important sur les performances du système. Dans cette thèse, nous étudierons les problèmes d’optimisation avec contraintes en probabilités dans les cas suivants : Tout d’abord, nous passons en revue les principaux résultats relatifs aux contraintes en probabilités selon trois perspectives: les problèmes liés à la convexité, les reformulations et les approximations de ces contraintes, et le cas de l’optimisation distributionnellement robuste. Pour les problèmes d’optimisation géométriques, nous étudions les programmes avec contraintes en probabilités jointes. A l’aide d’hypothèses d’indépendance des variables aléatoires elliptiquement distribuées, nous déduisons une reformulation des programmes avec contraintes géométriques rectangulaires jointes. Comme la reformulation n’est pas convexe, nous proposons de nouvelles approximations convexes basées sur la transformation des variables ainsi que des méthodes d’approximation linéaire par morceaux. Nos résultats numériques montrent que nos approximations sont asymptotiquement serrées. Lorsque les distributions de probabilité ne sont pas connues à l’avance, le calcul des bornes peut être très utile. Par conséquent, nous développons quatre bornes supérieures pour les contraintes probabilistes individuelles, et jointes dont les vecteur-lignes de la matrice des contraintes sont indépendantes. Sur la base des inégalités de Chebyshev, Chernoff, Bernstein et de Hoeffding, nous proposons des approximations déterministes. Des conditions suffisantes de convexité. Pour réduire la complexité des calculs, nous reformulons les approximations sous forme de problèmes d'optimisation convexes solvables basés sur des approximations linéaires et tangentielles par morceaux. Enfin, des expériences numériques sont menées afin de montrer la qualité des approximations étudiées sur des données aléatoires. Dans certains systèmes complexes, la distribution des paramètres aléatoires n’est que partiellement connue. Pour traiter les incertitudes dans ces cas, nous proposons un ensemble d'incertitude basé sur des données obtenues à partir de distributions mixtes. L'ensemble d'incertitude est construit dans la perspective d'estimer simultanément des moments d'ordre supérieur. Ensuite, nous proposons une reformulation du problème robuste avec contraintes en probabilités en utilisant des données issues d’échantillonnage. Comme la reformulation n’est pas convexe, nous proposons des approximations convexes serrées basées sur la méthode d’approximation linéaire par morceaux sous certaines conditions. Pour le cas général, nous proposons une approximation DC pour dériver une borne supérieure et une approximation convexe relaxée pour dériver une borne inférieure pour la valeur de la solution optimale du problème initial. Enfin, des expériences numériques sont effectuées pour montrer que les approximations proposées sont efficaces. Nous considérons enfin un jeu stochastique à n joueurs non-coopératif. Lorsque l'ensemble de stratégies de chaque joueur contient un ensemble de contraintes linéaires stochastiques, nous modélisons ces contraintes sous la forme de contraintes en probabilité jointes. Pour chaque joueur, nous formulons les contraintes en probabilité dont les variables aléatoires sont soit normalement distribuées, soit elliptiquement distribuées, soit encore définies dans le cadre de l’optimisation distributionnellement robuste. Sous certaines conditions, nous montrons l’existence d’un équilibre de Nash pour ces jeux stochastiques. / Chance constrained optimization is a natural and widely used approaches to provide profitable and reliable decisions under uncertainty. And the topics around the theory and applications of chance constrained problems are interesting and attractive. However, there are still some important issues requiring non-trivial efforts to solve. In view of this, we will systematically investigate chance constrained problems from the following perspectives. As the basis for chance constrained problems, we first review some main research results about chance constraints in three perspectives: convexity of chance constraints, reformulations and approximations for chance constraints and distributionally robust chance constraints. For stochastic geometric programs, we formulate consider a joint rectangular geometric chance constrained program. With elliptically distributed and pairwise independent assumptions for stochastic parameters, we derive a reformulation of the joint rectangular geometric chance constrained programs. As the reformulation is not convex, we propose new convex approximations based on the variable transformation together with piecewise linear approximation methods. Our numerical results show that our approximations are asymptotically tight. When the probability distributions are not known in advance or the reformulation for chance constraints is hard to obtain, bounds on chance constraints can be very useful. Therefore, we develop four upper bounds for individual and joint chance constraints with independent matrix vector rows. Based on the one-side Chebyshev inequality, Chernoff inequality, Bernstein inequality and Hoeffding inequality, we propose deterministic approximations for chance constraints. In addition, various sufficient conditions under which the aforementioned approximations are convex and tractable are derived. To reduce further computational complexity, we reformulate the approximations as tractable convex optimization problems based on piecewise linear and tangent approximations. Finally, based on randomly generated data, numerical experiments are discussed in order to identify the tight deterministic approximations. In some complex systems, the distribution of the random parameters is only known partially. To deal with the complex uncertainties in terms of the distribution and sample data, we propose a data-driven mixture distribution based uncertainty set. The data-driven mixture distribution based uncertainty set is constructed from the perspective of simultaneously estimating higher order moments. Then, with the mixture distribution based uncertainty set, we derive a reformulation of the data-driven robust chance constrained problem. As the reformulation is not a convex program, we propose new and tight convex approximations based on the piecewise linear approximation method under certain conditions. For the general case, we propose a DC approximation to derive an upper bound and a relaxed convex approximation to derive a lower bound for the optimal value of the original problem, respectively. We also establish the theoretical foundation for these approximations. Finally, simulation experiments are carried out to show that the proposed approximations are practical and efficient. We consider a stochastic n-player non-cooperative game. When the strategy set of each player contains a set of stochastic linear constraints, we model the stochastic linear constraints of each player as a joint chance constraint. For each player, we assume that the row vectors of the matrix defining the stochastic constraints are pairwise independent. Then, we formulate the chance constraints with the viewpoints of normal distribution, elliptical distribution and distributionally robustness, respectively. Under certain conditions, we show the existence of a Nash equilibrium for the stochastic game.

L'hydraulique est la principale énergie renouvelable produite en France. Elle apporte une réserve d'énergie et une flexibilité intéressantes dans un contexte d'augmentation de la part des énergies intermittentes dans la production. Sa gestion soulève des problèmes difficiles dus au nombre des barrages, aux incertitudes sur les apports d'eau et sur les prix, ainsi qu'aux usages multiples de l'eau. Cette thèse CIFRE, effectuée en partenariat avec Electricité de France, aborde deux questions de gestion hydraulique formulées comme des problèmes d'optimisation dynamique stochastique. Elles sont traitées dans deux grandes parties.Dans la première partie, nous considérons la gestion de la production hydroélectrique d'un barrage soumise à une contrainte dite de cote touristique. Cette contrainte vise à assurer une hauteur de remplissage du réservoir suffisamment élevée durant l'été avec un niveau de probabilité donné. Nous proposons différentes modélisations originales de ce problème et nous développons les algorithmes de résolution correspondants. Nous présentons des résultats numériques qui éclairent différentes facettes du problème utiles pour les gestionnaires du barrage.Dans la seconde partie, nous nous penchons sur la gestion d'une cascade de barrages. Nous présentons une méthode de résolution approchée par décomposition-coordination, l'algorithme Dual Approximate Dynamic Programming (DADP). Nousmontrons comment décomposer, barrage par barrage, le problème de la cascade en sous-problèmes obtenus en dualisant la contrainte de couplage spatial ``déversé supérieur = apport inférieur''. Sur un cas à trois barrages, nous sommes en mesure de comparer les résultats de DADP à la solution exacte (obtenue par programmation dynamique), obtenant desgains à quelques pourcents de l'optimum avec des temps de calcul intéressants. Les conclusions auxquelles nous sommes parvenu offrent des perspectives encourageantes pour l'optimisation stochastique de systèmes de grande taille / Hydropower is the main renewable energy produced in France. It brings both an energy reserve and a flexibility, of great interest in a contextof penetration of intermittent sources in the production of electricity. Its management raises difficulties stemming from the number of dams, from uncertainties in water inflows and prices and from multiple uses of water. This Phd thesis has been realized in partnership with Electricité de France and addresses two hydropower management issues, modeled as stochastic dynamic optimization problems. The manuscript is divided in two parts. In the first part, we consider the management of a hydroelectric dam subject to a so-called tourist constraint. This constraint assures the respect of a given minimum dam stock level in Summer months with a prescribed probability level. We propose different original modelings and we provide corresponding numerical algorithms. We present numerical results that highlight the problem under various angles useful for dam managers. In the second part, we focus on the management of a cascade of dams. We present the approximate decomposition-coordination algorithm called Dual Approximate Dynamic Programming (DADP). We show how to decompose an original (large scale) problem into smaller subproblems by dualizing the spatial coupling constraints. On a three dams instance, we are able to compare the results of DADP with the exact solution (obtained by dynamic programming); we obtain approximate gains that are only at a few percents of the optimum, with interesting running times. The conclusions we arrived at offer encouraging perspectives for the stochastic optimization of large scale problems

[pt] O planejamento hidrotérmico estocástico multi-etapa se destaca como um dos problemas mais importantes do setor elétrico, principalmente devido à sua grande relevância na operação do sistema. Este problema refere-se a determinar o despacho ótimo das usinas que minimizam o custo de operação sob as restrições físicas do sistema. Uma das principais dificuldades do problema reside nas representações de incerteza, pois a decisão de despacho deve considerar os diferentes cenários possíveis de afluência de água, geração renovável e demanda. Mais recentemente, o grande aumento de fontes renováveis variáveis trouxe a atenção dos pesquisadores para como melhorar a granularidade do modelo sem aumentar muito o tempo computacional. Neste trabalho é proposto uma nova formulação para um despacho econômico estocástico multi-etapa com unit-commitment. O modelo usa regras de decisão afins para ser computacionalmente tratável. A relação entre regras de decisão e o scenario approach é explorada e, ao construir o conjunto de incertezas, tanto a viabilidade da política da regra de decisão quanto a restrição probabilística do balanço de carga são automaticamente respeitadas. / [en] Multi-stage stochastic hydrothermal planning stands as one of the most critical problems in the power systems industry, mostly due to its vast implication in the system operation. The multi-stage stochastic hydrothermal scheduling refers to determining the economic dispatch of the power plants that minimize the global operation cost under the system s physical constraints. One of the main difficulties of the problem lies in the representations of uncertainty, as the dispatch decision must consider the different possible scenarios of water inflow, renewable generation, and the demand. More recently, we have seen a worldwide speed up in the integration of variable renewable sources. Nonetheless, these sources have a greater uncertainty in the short-term than the world has ever experienced. Therefore, to support the dispatch scheduling, the models must accurately represent the uncertainties without increasing computational time. In this work it is proposed a novel formulation for a multistage stochastic week-ahead economic dispatch with unit-commitment. The model uses affine decision rules to be computationally tractable. The relationship between the decision rules and the scenario approach is explored, and by building the uncertainty set with the scenario approach, both the feasibility of the decision rule policy and the chance-constraint on the load balance are respected.

Orientador: John Fredy Franco Baquero / Resumo: A crescente penetração dos Veículos Elétricos (VEs) no setor de transportes representa um novo e grande desafio para o planejamento da expansão e da operação dos Sistemas de Distribuição de Energia Elétrica (SDEEs) devido ao correspondente aumento da demanda associada ao carregamento das baterias. Portanto, devem ser desenvolvidos métodos que ajudem os SDEEs a lidar com esses desafios, considerando as incertezas associadas às demandas convencionais e aos VEs. Nesta tese é proposto um método robusto baseado em um modelo de Programação Linear Inteira-Mista (PLIM) para auxiliar a integração de VEs no SDEE. O método proposto permite resolver o problema de planejamento multi-estágio da expansão do SDEE considerando a alocação e o dimensionamento de Estações de Carregamento de VEs (ECVEs). Restrições probabilísticas são usadas na formulação proposta para lidar com as incertezas associadas à demanda, garantindo o cumprimento da capacidade de potência das subestações com um nível de confiança especificado. O modelo proposto para o planejamento da expansão avalia a construção e/ou reforço de subestações, ECVEs e circuitos, assim como também a alocação de unidades de geração distribuída e bancos de capacitores ao longo do horizonte de planejamento. O modelo de PLIM proposto é resolvido através de técnicas de otimização clássica visando garantir a solução ótima do problema. A eficiência e robustez do modelo são verificadas usando sistemas teste de 18 e 54 nós, junto com simulações de Mo... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The increasing penetration of electric vehicles (EVs) in the transportation sector represents a new challenge for the expansion planning of electrical distribution systems (EDS) due to the corresponding increase of the energy demand. Therefore, methods to support the EDS considering the uncertainties associated with conventional and EV demands should be developed. This thesis presents a methodology to consider the EV integration into the EDS. A mixed-integer linear programming (MILP) model is proposed to solve the multi-stage expansion planning of EDS considering the allocation and sizing of EV charging stations (EVCSs). Chance constraints are used in the formulation to deal with the uncertainties associated with the demands, guaranteeing the fulfilment of the substation capacities within a given confidence level. The proposed model for the expansion planning considers the construction/reinforce of substations, EVCSs and circuits as well as the allocation of distributed generation units and capacitor banks along the planning horizon. The proposed MILP model guarantees optimality using classical optimization techniques. The efficiency and robustness of the model is verified using two test systems with 18-nodes and 54-nodes. Monte Carlo simulations were carried out to verify the compliance of the proposed chance constraint. / Doutor

Les centres d’appels sont des éléments clés de presque n’importe quelle grande organisation. Le problème de gestion du travail a reçu beaucoup d’attention dans la littérature. Une formulation typique se base sur des mesures de performance sur un horizon infini, et le problème d’affectation d’agents est habituellement résolu en combinant des méthodes d’optimisation et de simulation. Dans cette thèse, nous considérons un problème d’affection d’agents pour des centres d’appels soumis a des contraintes en probabilité. Nous introduisons une formulation qui exige que les contraintes de qualité de service (QoS) soient satisfaites avec une forte probabilité, et définissons une approximation de ce problème par moyenne échantillonnale dans un cadre de compétences multiples. Nous établissons la convergence de la solution du problème approximatif vers celle du problème initial quand la taille de l’échantillon croit. Pour le cas particulier où tous les agents ont toutes les compétences (un seul groupe d’agents), nous concevons trois méthodes d’optimisation basées sur la simulation pour le problème de moyenne échantillonnale. Étant donné un niveau initial de personnel, nous augmentons le nombre d’agents pour les périodes où les contraintes sont violées, et nous diminuons le nombre d’agents pour les périodes telles que les contraintes soient toujours satisfaites après cette réduction. Des expériences numériques sont menées sur plusieurs modèles de centre d’appels à faible occupation, au cours desquelles les algorithmes donnent de bonnes solutions, i.e. la plupart des contraintes en probabilité sont satisfaites, et nous ne pouvons pas réduire le personnel dans une période donnée sont introduire de violation de contraintes. Un avantage de ces algorithmes, par rapport à d’autres méthodes, est la facilité d’implémentation. / Call centers are key components of almost any large organization. The problem of labor management has received a great deal of attention in the literature. A typical formulation of the staffing problem is in terms of infinite-horizon performance measures. The method of combining simulation and optimization is used to solve this staffing problem. In this thesis, we consider a problem of staffing call centers with respect to chance constraints. We introduce chance-constrained formulations of the scheduling problem which requires that the quality of service (QoS) constraints are met with high probability. We define a sample average approximation of this problem in a multiskill setting. We prove the convergence of the optimal solution of the sample-average problem to that of the original problem when the sample size increases. For the special case where we consider the staffing problem and all agents have all skills (a single group of agents), we design three simulation-based optimization methods for the sample problem. Given a starting solution, we increase the staffings in periods where the constraints are violated, and decrease the number of agents in several periods where decrease is acceptable, as much as possible, provided that the constraints are still satisfied. For the call center models in our numerical experiment, these algorithms give good solutions, i.e., most constraints are satisfied, and we cannot decrease any agent in any period to obtain better results. One advantage of these algorithms, compared with other methods, that they are very easy to implement.

Le problème de dimensionnement et planification d'agents en centre d'appels consiste à déterminer sur une période le nombre d'interlocuteurs requis afin d'atteindre la qualité de service exigée et minimiser les coûts induits. Ce sujet fait l'objet d'un intérêt croissant pour son intérêt théorique mais aussi pour l'impact applicatif qu'il peut avoir. Le but de cette thèse est d'établir des approches en contraintes en probabilités en considérant l'incertitude de la demande.Tout d'abord, la thèse présente un modèle en problème d'optimisation stochastique avec contrainte en probabilité jointe traitant la problématique complète en une étape afin d'obtenir un programme facile à résoudre. Une approche basée sur l'idée de continuité est proposée grâce à des lois de probabilité continues, une nouvelle relation entre les taux d'arrivées et les besoins théoriques et la linéarisation de contraintes. La répartition du risque global est faite pendant le processus d'optimisation, permettant une solution au coût réduit. Ces solutions résultantes respectent le niveau de risque tout en diminuant le coût par rapport à d'autres approches.De plus, le modèle en une étape est étendu pour améliorer sa représentation de la réalité. D'une part, le modèle de file d'attente est amélioré et inclus la patience limitée des clients. D'autre part, une nouvelle expression de l'incertitude est proposée pour prendre la dépendance des périodes en compte.Enfin, une nouvelle représentation de l'incertitude est considérée. L'approche distributionally robust permet de modéliser le problème sous l'hypothèse que la loi de probabilité adéquate est inconnue et fait partie d'un ensemble de lois, défini par une moyenne et une variance données. Le problème est modélisé par une contrainte en probabilité jointe. Le risque à chaque période est définie par une variable à optimiser.Un problème déterministe équivalent est proposé et des approximations linéaires permettent d'obtenir une formulation d'optimisation linéaire. / The staffing and shift-scheduling problems in call centers consist in deciding how many agents handling the calls should be assigned to work during a given period in order to reach the required Quality of Service and minimize the costs. These problems are subject to a growing interest, both for their interesting theoritical formulation and their possible applicative effects. This thesis aims at proposing chance-constrained approaches considering uncertainty on demand forecasts.First, this thesis proposes a model solving the problems in one step through a joint chance-constrained stochastic program, providing a cost-reducing solution. A continuous-based approach leading to an easily-tractable optimization program is formulated with random variables following continuous distributions, a new continuous relation between arrival rates and theoritical real agent numbers and constraint linearizations. The global risk level is dynamically shared among the periods during the optimization process, providing reduced-cost solution. The resulting solutions respect the targeted risk level while reducing the cost compared to other approaches.Moreover, this model is extended so that it provides a better representation of real situations. First, the queuing system model is improved and consider the limited patience of customers. Second, another formulation of uncertainty is proposed so that the period correlation is considered.Finally, another uncertainty representation is proposed. The distributionally robust approach provides a formulation while assuming that the correct probability distribution is unknown and belongs to a set of possible distributions defined by given mean and variance. The problem is formulated with a joint chance constraint. The risk at each period is a decision variable to be optimized. A deterministic equivalent problem is proposed. An easily-tractable mixed-integer linear formulation is obtained through piecewise linearizations.