Avec la forte croissance du e-commerce et l'augmentation continue de la population des villes impliquant des niveaux de congestion plus élevés, les réseaux de distribution doivent déployer des échelons supplémentaires pour offrir un ajustement dynamique aux besoins des entreprises au cours du temps et faire face aux aléas affectant l’activité de distribution. Dans ce contexte, les praticiens s'intéressent aux réseaux de distribution à deux échelons. Dans cette thèse, nous commençons par présenter une revue complète des problèmes de design des réseaux de distribution et souligner des caractéristiques essentielles de modélisation. Ces aspects impliquent la structure à deux échelons, l’aspect multi-période, l’incertitude et les méthodes de résolution. Notre objectif est donc, d’élaborer un cadre complet pour le design d’un réseau de distribution efficace à deux échelons, sous incertitude et multi-périodicité, dans lequel les produits sont acheminés depuis les plateformes de stockage (WP) vers les plateformes de distribution (DP) avant d'être transportés vers les clients. Ce cadre est caractérisé par une hiérarchie temporelle entre le niveau de design impliquant des décisions relatives à la localisation des plateformes et à la capacité allouée aux DPs sur une échelle de temps annuelle, et le niveau opérationnel concernant des décisions journalières de transport. % sur une base journalière.Dans une première étude, nous introduisons le cadre complet pour le problème de design de réseaux de distribution à deux échelons avec une demande incertaine, une demande et un coût variables dans le temps. Le problème est formulé comme un programme stochastique à plusieurs étapes. Il implique au niveau stratégique des décisions de localisation des DPs ainsi que des décisions d'affectation des capacités aux DPs sur plusieurs périodes de design, et au niveau opérationnel des décisions de transport sous forme d'arcs origine-destination. Ensuite, nous proposons deux modèles alternatifs basés sur la programmation stochastique à deux étapes avec recours, et les résolvons par une approche de décomposition de Benders intégrée à une technique d’approximation moyenne d’échantillon (SAA). Par la suite, nous nous intéressons à la livraison du dernier kilomètre dans un contexte urbain où les décisions de transport dans le deuxième échelon sont caractérisées par des tournées de véhicules. Un problème multi-période stochastique de localisation-routage à deux échelons avec capacité (2E-SM-CLRP) est défini, dans lequel les décisions de localisation concernent les WPs et les DPs. Le modèle est un programme stochastique à deux étapes avec recours en nombre entier. Nous développons un algorithme de décomposition de Benders. Les décisions de localisation et de capacité sont déterminées par la solution du problème maître de Benders. Le sous-problème résultant est un problème multi-dépôt de tournées de véhicule avec des dépôts et véhicules capacitaires qui est résolu par un algorithme de branch-cut-and-price.Enfin, nous étudions le cadre à plusieurs étapes proposé pour le problème stochastique multi-période de design de réseaux de distribution à deux échelons et évaluons sa tractabilité. Pour ceci, nous développons une heuristique à horizon glissant qui permet d’obtenir des bornes de bonne qualité et des solutions de design pour le modèle à plusieurs étapes. / With the high growth of e-commerce and the continuous increase in cities population contrasted with the rising levels of congestion, distribution schemes need to deploy additional echelons to offer more dynamic adjustment to the requirement of the business over time and to cope with all the random factors. In this context, a two-echelon distribution network is nowadays investigated by the practitioners.In this thesis, we first present a global survey on distribution network design problems and point out many critical modeling features, namely the two-echelon structure, the multi-period setting, the uncertainty and solution approaches. The aim, here, is to propose a comprehensive framework for the design of an efficient two-echelon distribution network under multi-period and stochastic settings in which products are directed from warehouse platforms (WPs) to distribution platforms (DPs) before being transported to customers. A temporal hierarchy characterizes the design level dealing with facility-location and capacity decisions over a set of design periods, while the operational level involves transportation decisions on a daily basis.Then, we introduce the comprehensive framework for the two-echelon distribution network design problem under uncertain demand, and time-varying demand and cost, formulated as a multi-stage stochastic program. This work looks at a generic case for the deployment of a retailer's distribution network. Thus, the problem involves, at the strategic level, decisions on the number and location of DPs along the set of design periods as well as decisions on the capacity assignment to calibrate DP throughput capacity. The operational decisions related to transportation are modeled as origin-destination arcs. Subsequently, we propose alternative modeling approaches based on two-stage stochastic programming with recourse, and solve the resulting models using a Benders decomposition approach integrated with a sample average approximation (SAA) technique.Next, we are interested in the last-mile delivery in an urban context where transportation decisions involved in the second echelon are addressed through multi-drop routes. A two-echelon stochastic multi-period capacitated location-routing problem (2E-SM-CLRP) is defined in which facility-location decisions concern both WPs and DPs. We model the problem using a two-stage stochastic program with integer recourse. To solve the 2E-SM-CLRP, we develop a Benders decomposition algorithm. The location and capacity decisions are fixed from the solution of the Benders master problem. The resulting subproblem is a capacitated vehicle-routing problem with capacitated multi-depot (CVRP-CMD) and is solved using a branch-cut-and-price algorithm.Finally, we focus on the multi-stage framework proposed for the stochastic multi-period two-echelon distribution network design problem and evaluate its tractability. A scenario tree is built to handle the set of scenarios representing demand uncertainty. We present a compact formulation and develop a rolling horizon heuristic to produce design solutions for the multi-stage model. It provides good quality bounds in a reasonable computational times.

Hub and Spoke systems, is a important research area in localization theory. This occur, because of these systems are very used in logistics problems, e.g., telecommunication networks and transport of passenger and load.To serve the demand of each pair source destination, basically, the Hub and Spoke system replaces direct connections between the pairs for a hubs network. These hubs group the traffic sharing the transportation medium. To get the best hubs configuration is necessary efficient methods, because this problem, hubs allocation, is a NP-problem. In this work was developed an parallel implementation of the Benders Decomposition method for the uncapacitated multiple allocation hub location problem. In our implementation we use the Skorin- Kapov model. The parallel implementation of Benders Decomposition for hub and spoke problem is not known in literature. The results show that the parallel approach is applicable and more efficient that nonparallel one. The experiments reveals that the parallel algorithm had a time execution 70% minor when compared with the nonparallel one. / Sistemas do tipo eixo raio, tornaram-se uma importante área de pesquisa da teoria de localização nas últimas décadas. Esse destaque deve-se em grande parte ao sucesso de sua utilização em sistemas logísticos, tanto de transporte de passageiros quanto de cargas, e em redes de telecomunicações. Ao invés de servir cada par origem destino de demanda com uma conexão direta, sistemas do tipo eixo raio substituem essas conexões diretas por uma rede de concentradores. Esses concentradores permitem que o tráfego seja agrupado e transportado através de um meio de transporte compartilhado, para ser então entregue aos respectivos destinos. Sendo um problema NP, é necessário o uso de métodos eficientes para sua resolução. Neste trabalho, é desenvolvida uma implementação em paralelo do método de Decomposição de Benders para o problema de localização de concentradores de alocação múltipla não capacitados. A implementação em paralelo do método de Decomposição de Benders para o problema eixo raio não é conhecido na literatura, entretanto os bons resultados obtidos pelo algoritmo paralelo desenvolvido revelam que a abordagem paralela é aplicável e mais eficiente. Nos experimentos realizados, o algoritmo paralelo apresentou um tempo de resposta até 70% menor que o tempo de resposta do algoritmo seqüencial.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2018-11-06T17:02:42Z No. of bitstreams: 1 marcelodesouzaaleixo.pdf: 2786878 bytes, checksum: dfbd57d9b8be2153917fe637209df9f0 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2018-11-23T13:19:16Z (GMT) No. of bitstreams: 1 marcelodesouzaaleixo.pdf: 2786878 bytes, checksum: dfbd57d9b8be2153917fe637209df9f0 (MD5) / Made available in DSpace on 2018-11-23T13:19:16Z (GMT). No. of bitstreams: 1 marcelodesouzaaleixo.pdf: 2786878 bytes, checksum: dfbd57d9b8be2153917fe637209df9f0 (MD5) Previous issue date: 2018-06-29 / Este trabalho apresenta uma metodologia para cálculo da reserva girante do sistema elétrico de potência. A proposta inclui a curva de capabilidade dos geradores bem como cenários de carga e de geração eólica bem como falhas no sistema de geração e transmissão. O fluxo de potência ótimo é utilizado para determinar as condições iniciais do sistema, caso base. A partir daí o problema é resolvido de forma interativa entre dois estágios em umaestruturamestreeescravo: Oproblemamestreutilizaprogramaçãolinearinteirapara determinar o número mínimo de unidades de geração disponíveis (ligadas); O problema escravo verifica se o número de unidades ligadas é suficiente para operação do sistema. Este problema corresponde ao Fluxo de Potência Ótimo com o objetivo de obter o mínimo corte de carga para cada condição operativa. O corte de Benders é produzido para cada cenário, altenativamente, será investigado a utilização da média dos cortes de Benders. O processo termina quando não ocorrer corte de carga. A metodologia é testada utilizando um sistema teste de 4 barras como exemplo tutorial e também aplicada nos sistemas IEEE 14, 39 e 118 barras. / This work presents a methodology for calculating the spinning reserve of the electric power system. The proposal includes the capability curve of the generators as well as errors of prediction of load, wind generation, failures in the system of generation and transmission. The optimal power flow is used to determine the initial conditions of the system, base case. From this point the problem is solved interactively between two stages in a master and slave structure: The first uses integer linear programming to determine the minimum number of available (turn on) generation units; The second corresponds to the Optimum Power Flow with the purpose of obtaining the minimum load shedding for each operative condition. The cut of Benders is produced for each scenario, alternatively, the use of the average of cuts will be investigated. The process ends when there is no load shedding. The methodology is tested using a 4-bar test system as a tutorial example and also applied in IEEE systems 14, 39 and 118 bars.

[pt] No Brasil, as três principais fontes renováveis de energia elétrica são eólica, pequenas centrais hidrelétricas (PCHs) e biomassa. A comercialização da energia proveniente dessas fontes ocorre majoritariamente no ambiente de contratação regulada (ACR), através de leilões, em detrimento do ambiente de contratação livre (ACL). Isso devido ao fato de seus recursos naturais serem sazonais, estabelecendo o risco de preço-quantidade no ACL, em que o excesso ou déficit de energia gerada em relação à quantidade contratada é liquidado ao preço de liquidação de diferenças (PLD), uma variável sistêmica e altamente volátil. Contudo, a complementaridade dessas fontes permite reduzir esses riscos quando a energia é comercializada de forma conjunta, através de um fundo de energia que gera aumento do valor do portfólio com relação à comercialização individual. Esta dissertação utiliza a teoria de jogos cooperativos para analisar formas de repartir o benefício gerado, através da alocação de quotas financeiras. O conjunto de soluções onde o resultado individual das fontes no fundo é maior do que o resultado individual em qualquer subcoalisão define o núcleo do jogo. Assim, a complexidade de encontrar uma solução dentro do núcleo depende do número de subcoalizões, que cresce exponencialmente com o número de jogadores. Nesse contexto, este trabalho se propôs a apresentar: (i) um modelo de portfólio que incentiva a participação de fontes renováveis no ACL; (ii) um modelo de programação linear que busca o núcleo do jogo; (iii) uma metodologia eficiente baseada em decomposição de Benders, capaz de suprimir a questão da explosão combinatória do problema. / [en] In Brazil, the three main sources of renewable energy are wind, small run-of-river hidros (SH) and biomass. The energy sale of such sources occurs mainly in the Regulated Trading Environment (RTE), through auctions, with shy occurrences in the Free Trading Environment (FTE). This is due to the fact that their natural resources are seasonal, establishing the so-called price-quantity risk in the FTE, as the surplus or deficit of energy generated relative to the contracted amount is settled at the market’s spot price, a systemic and highly volatile variable. However, the complementary nature of these sources allows risk reduction if their energy are trade jointly, through an energy hedge pool that increases the value of the portfolio in comparison to individual strategies. This work makes use of cooperative games theory to analyze ways of sharing the generated benefit, through financial quotas allocation. The set of solutions where the individual sources results in the pool are greater than its results at any possible subcoalition defines the core of the game. Thus, the challenge of finding a solution inside the core depends on the number of subcoalitions, which grows exponentially with the number of players. In this context, this work proposes to present: (i) a model of portfolio that encourages the penetration of renewable sources in the FTE; (ii) a linear programming model that pursuits the game’s core; (iii) an efficient methodology based on Benders decomposition that is capable of suppress the problem of combinatorial explosion, typical of cooperative games with many players.

Made available in DSpace on 2016-06-02T19:51:37Z (GMT). No. of bitstreams: 1 2228.pdf: 979050 bytes, checksum: ffa6f96c8eada124b6f1e6ba3ebe02da (MD5) Previous issue date: 2008-12-11 / Financiadora de Estudos e Projetos / Cutting and packing problems are important in the production planning of various industrial segments involving goals such as minimizing the negative efects generated by waste of materials or idle spaces. The loss of material due to an inadequate programming of the cutting or packing patterns, can be substantial, and, in general, parts of these losses can be avoided only with a more eficient production planning, not resulting in additional investments in production processes. This study aimed at evaluating the performance of the Benders decomposition method, applied to the manufacturer and distributor pallet loading models. The manufacturer pallet loading model involves packing equal boxes on a pallet, so as to optimize its use. The distributor pallet loading model involves packing boxes of diferent sizes on a pallet, also a way to optimize its use. The approach based on Benders decomposition, defines a relaxation algorithm that partitions the original problem in two other problems easier to be solved. To check the effectiveness of the approach, computational tests were carried out by comparing the results with those obtained by a computational package composed of a modeling language (GAMS) and a last generation optimization solver (CPLEX ). / Os problemas de corte e empacotamento são importantes no planejamento da produção de vários segmentos industriais envolvendo objetivos como, por exemplo, minimizar os efeitos negativos gerados por desperdício de materiais ou espaços ociosos. As perdas de material, devido a uma programação pouco adequada dos padrões de corte ou empacotamento, podem ser substanciais, sendo que, em geral, parte destas perdas pode ser evitada apenas com uma programação da produção mais eficiente, não implicando em investimentos adicionais nos processos de produção. O objetivo deste estudo é verificar o desempenho do método de decomposição de Benders aplicado a modelos de carregamento de paletes do produtor e do distribuidor. O problema de carregamento de paletes do produtor envolve empacotar caixas iguais sobre um palete, de maneira a otimizar o aproveitamento deste. O problema de carregamento de paletes do distribuidor envolve empacotar caixas de tamanhos diferentes sobre um palete, também de maneira a otimizar o aproveitamento deste. A abordagem baseada na reformulação de Benders define um algoritmo de relaxação que particiona o problema original em dois outros problemas mais simples de serem resolvidos. Para verificar a eficiência da abordagem, realizaram-se testes computacionais, comparando os resultados obtidos com os obtidos pelo pacote computacional composto de uma linguagem de modelagem (GAMS) e um software de otimização de última geração (CPLEX).

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-04-11T14:02:57Z No. of bitstreams: 1 joseantoniochiabaibento.pdf: 931983 bytes, checksum: e18793314d0e558922ed90cb19474dbb (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-04-24T03:37:26Z (GMT) No. of bitstreams: 1 joseantoniochiabaibento.pdf: 931983 bytes, checksum: e18793314d0e558922ed90cb19474dbb (MD5) / Made available in DSpace on 2016-04-24T03:37:26Z (GMT). No. of bitstreams: 1 joseantoniochiabaibento.pdf: 931983 bytes, checksum: e18793314d0e558922ed90cb19474dbb (MD5) Previous issue date: 2013-02-27 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A penetração de parques eólicos nos sistemas elétricos de potência tem apresentado um grande crescimento no Brasil e no mundo devido à disponibilidade da matéria prima, os ventos, e à necessidade de reformulação das matrizes energéticas a fim de reduzir os impactos ambientais decorrentes da geração de energia elétrica. Porém, as usinas eólicas apresentam variações nos despachos de potência devido à variabilidade de velocidade dos ventos. Estas variações causam impactos no sistema, podendo afetar a confiabilidade e a estabilidade de tensão. Além disto, a operação de determinados tipos de aerogeradores requer suporte adicional de potência reativa. Uma opção para aumentar as margens operativas e acomodar as intermitências de regime dos ventos em sistemas elétricos de potência consiste na utilização de compensadores estáticos de reativos (CER) junto às usinas eólicas. Estes equipamentos FACTS (Flexible AC Transmission Systems) provêm suporte de potência reativa variável e de rápido controle, de acordo com os requisitos operacionais dos aerogeradores. Neste sentido, o presente trabalho apresenta uma metodologia para ajuste ótimo dos parâmetros do CER visando dar suporte de potência reativa para a operação de usinas eólicas em sistemas elétricos de potência. Para representar as intermitências no despacho de potência dos aerogeradores, a metodologia proposta considera diferentes cenários de vento. O problema é modelado através de fluxo de potência ótimo (FPO), associado à técnica de decomposição matemática de Benders. Os parâmetros de ajuste do CER são a tensão de referência e o coeficiente de inclinação da curva característica deste equipamento em regime permanente. Destaca-se que o ajuste ótimo deste coeficiente é inédito na literatura especializada. Testes com sistemas do IEEE são realizados para validar a metodologia proposta. / The penetration of wind farms in power systems has shown tremendous growth in Brazil and in the world due to the availability of the raw material, the wind, and the need to redefine the energy mix to reduce the environmental impacts from the electrical energy generation. However, the wind farms have variable outputs due to the variation of wind speeds. These outputs impact the power system and can affect the reliability and the voltage stability. Besides, the operation of some aerogenerators requires additional support of reactive power. An option for handling this feature and increasing the operative margins of power systems is the use of static VAr compensators (SVC) together with the wind farms. These FACTS devices (Flexible AC Transmission Systems) provide a variable reactive power support, with a fast control according to the operational requirements of the aerogenerators. In this sense, this work presents a methodology for the optimal adjustment of the SVC parameters to give reactive power support for wind farms operating in power systems. The proposed methodology considers different wind scenarios to represent the variations of the wind farms outputs. The problem is modeled through an optimal power flow (OPF) and the Benders decomposition technique. The SVC parameters for adjustment are its reference voltage and the coefficient of its characteristic curve in stable state. It can be highlighted that the adjustment of this coefficient is innovative for the literature. Tests with systems of the IEEE are performed to validate the proposed methodology.

Dans plusieurs pays européens, la capacité de l’infrastructure est complètement exploitée aux heures de pointe et aux points critiques : une grande quantité de trains traversent ces points critiques dans un laps de temps très réduit. Dans cette situation le retard d’un train provoqué par un conflit de circulation peut se propager dans tout le réseau. Le problème de la gestion opérationnelle du trafic ferroviaire consiste à trouver les modifications des itinéraires et des ordonnancements des trains qui minimisent la propagation des retards. Dans cette thèse, nous proposons une approche de décomposition de Benders pour la formulation linéaire en nombres entiers à variables mixtes utilisée dans l’algorithme RECIFE-MILP. Après avoir constaté que l’approche de décomposition standard de Benders ne permet pas de trouver rapidement une solution de bonne qualité pour certaines instances du problème, nous étudions trois approches alternatives afin d’améliorer la performance de notre algorithme. Nous proposons d’abord une approche que nous appelons la reformulation réduite de Benders. Ensuite, nous introduisons des inégalités dans la formulation du problème maître de Benders. Finalement, nous scindons le processus de résolution en trois étapes au lieu de deux comme dans la décomposition standard de Benders. L'analyse expérimentale montre que la combinaison de la première et dernière approche surpasse l’algorithme original RECIFE-MILP dans la résolution de grandes instances sous certaines conditions. / In railway systems, during congested traffic situations, the infrastructure capacity is completely exploited for trains circulation. In these situations, when traffic is perturbed some trains must be stopped or slowed down for ensuring safety, and delays occur. The real-time Railway Traffic Management Problem (rtRTMP) is the problem of modifying trains route and schedule to limit delay propagation. In this thesis, we propose a Benders decomposition of a MILP-based algorithm for this problem, named RECIFE-MILP. After observing that the standard Benders decomposition (BD) does not allow the effective solution of rtRTMP instances, we study three possible approaches to improve the performance. Specifically, we first propose a modification of the problem reformulation which is typical of BD, obtaining what we call reduced BD. Then, we introduce some inequalities to the Benders master problem. Finally, we split the solution process in three steps rather than two as in the standard BD. As we show in a thorough experimental analysis, the combination of the first and last approaches outperforms the original RECIFE-MILP algorithm when tackling large instances with some specific features.

Le placement de production (UC pour unit commitment) est une famille de problèmes d'optimisation qui déterminent l’état et la puissance de consigne des groupes de production pour satisfaire la demande électrique à moindre coût. Traditionnellement, une contrainte de sûreté détermine un certain volume de capacité raccordée disponible, appelé la réserve, destinée à gérer l'incertitude. Néanmoins, dans les petits systèmes la contrainte de réserve fixe peut entraîner dans certains cas une violation du critère N-1 bien que le volume de réserve minimale soit respecté. Plus récemment, la part croissante de production variable à partir de sources renouvelables (ENR) peut conduire à des programmes d’appel qui ne garantissent plus la sûreté même dans les grands systèmes.Pour y faire face, différentes techniques d'atténuation des impacts ont été proposées telle que la révision des modèles de placement de la production pour inclure une meilleure représentation de la dynamique du système. Cette sous-famille des problèmes UC est formellement définie dans ces travaux comme le problème FCUC (frequency constrained unit commitment). Elle vise à maintenir la fréquence au-dessus d'un certain seuil, et éviter ainsi le délestage par sous-fréquence (DSF).La première partie de ces travaux identifie les défis dans la formulation du problème FCUC. D’une part, la contrainte de fréquence est fortement non-linéaire par rapport aux variables de décision du problème UC. D’autre part, elle est difficile à approcher par des fonctions analytiques. La simulation séquentielle d'un modèle UC classique et d’un modèle de réponse primaire de la fréquence est alors proposée. L’intérêt d’une formulation plus fidèle de la contrainte de sûreté est donc révélé. La deuxième partie de ces travaux étudie l'impact des ENR sur la réponse primaire de la fréquence. Le besoin de formuler des modèles de FCUC plus précis est mis en avant.La troisième partie des travaux examine le coût, les bénéfices et les limitations des modèles FCUC, basés sur des contraintes indirectes sur certains paramètres dynamiques des unités de production. Il est montré que, bien que l'application de contraintes de sécurité indirectes assure la sûreté dans certains pas horaires, l'effet inverse peut apparaître à un autre instant. Ainsi, l’efficacité des leviers dépend fortement du point de fonctionnement du système. Il en est de même pour le coût de la solution. Cette étude met en évidence la nécessité de nouvelles méthodes pour traiter correctement la contrainte sur le creux de fréquence afin d'assurer l'optimalité et efficacité de la solution.Finalement, la quatrième partie des travaux offre une nouvelle formulation du problème FCUC suivant une approche de décomposition de Bender. La décomposition de Bender sépare un problème d'optimisation avec une certaine structure en deux parties : le problème maître et le problème esclave. Dans le cas du FCUC, le problème maître propose des plans de production candidats (états des groupes) et le problème esclave assure le respect des contraintes de fréquence par le biais d'un modèle de plans sécants. Les résultats de simulation montrent que la représentation plus précise du creux de fréquence au niveau du problème esclave réduit le risque de DSF et le coût de la sécurité par rapport à d'autres modèles de FCUC. / The Unit Commitment problem (UC) is a family of optimisation models for determining the optimal short-term generation schedule to supply electric power demand with a defined risk level. The UC objective function is given by the operational costs over the optimisation horizon. The constraints include, among others, technical, operational and security limits. Traditionally, the security constraints are given by the requirement of a certain volume of on-line spare capacity, which is called the reserve and is meant to handle uncertainty, while preventing the interruption of power supply. It is commonly specified following a static reliability criterion, such as the N-1 rule.Nevertheless, in small systems the fixed, and a priori defined, reserve constraint could entail a violation of the N-1 criterion, although the reserve constraint was met. More recently, the increasing share of variable generation from renewable sources (V-RES), such as wind and solar, may lead to UC solutions that no longer ensure system security. Therefore, different impact mitigation techniques have been proposed in literature, which include the revision of UC models to provide a better representation of the system dynamics. This subfamily of UC models is formally defined in this work as the frequency constrained UC problem (FCUC), and aims to keep the frequency above a certain threshold, following pre-defined contingencies, by adding enhanced security constraints. In this work this topic is addressed in four parts.The first part identifies the main challenge of formulating the FCUC problem. Indeed, the frequency minimum, also called the frequency nadir, constraint is strongly non-linear on the decision variables of the UC model. Moreover, the behaviour of the frequency nadir regarding the binary decision variables is hard to approximate by analytical functions. Thus, a sequential simulation approach is proposed, based on a classic UC model and a reduced order model of the primary frequency response. The potential benefits of a smarter allocation of the primary reserve is revealed.The second part of this work investigates the impact of V-RES sources on the primary frequency response. The underlying processes that lead to the increase of the Under-Frequency Load Shedding (UFLS) risk are thoroughly discussed. The need of formulating more accurate FCUC models is highlighted.The third part of this work examines the cost/benefit and limitation of FCUC models based on indirect constraints over certain dynamic parameters of the generating units. A methodology is proposed that assesses the effectiveness and optimality of some existing V-RES impact mitigation techniques, such as the increase of the primary reserve requirement, the prescription of an inertia requirement, the authorisation of V-RES dispatch-down or the consideration of fast non-synchronous providers of frequency regulation services. This study showed the need for new methods to properly handle the frequency nadir constraint in order to ensure optimality, without compromising the optimisation problem’s tractability.The fourth part of this work offers a new formulation of the FCUC problem following a Bender’s decomposition approach. This method is based on the decomposition of an optimisation problem into two stages: the master and the slave problems. Here, the master problem deals with the generating unit states and the slave problem handles the frequency nadir constraints through a cutting plane model. Simulation results showed that the more accurate representation of the frequency nadir in the slave problem reduces the risk of UFLS and the security cost, with respect to other FCUC models, such as those based on inertia constraints. In addition, the optimality of the global solution is guaranteed; although the convergence of the master problem is slow, due to the well-known tailing off effect of cutting plane methods.

We consider the problem of minimizing costs in the generation unit commitment problem, a cornerstone in electric power system operations, while enforcing an -- reliability criterion. This reliability criterion is a generalization of the well-known - criterion and dictates that at least fraction of the total system demand (for ) must be met following the failure of or fewer system components. We refer to this problem as the contingency-constrained unit commitment problem, or CCUC. We present a mixed-integer programming formulation of the CCUC that accounts for both transmission and generation element failures. We propose novel cutting plane algorithms that avoid the need to explicitly consider an exponential number of contingencies. Computational studies are performed on several IEEE test systems and a simplified model of the Western US interconnection network. These studies demonstrate the effectiveness of our proposed methods relative to current state-of-the-art.

Network planning is an essential phase in successfully operating state-of-the-art telecommunication systems. It helps carriers increase revenues by deploying the right technologies in a cost effective manner. More importantly, through the network planning phase, carriers determine the capital needed to build the network as well as the competitive pricing for the offered services. Through this phase, radio tower locations are selected from a pool of candidate locations so as to maximize the net revenue acquired from servicing a number of subscribers. In the Universal Mobile Telecommunication System (UMTS) which is based on the Wideband Code Division Multiple Access scheme (W-CDMA), the coverage area of each tower, called a cell, is not only affected by the signal's attenuation but is also affected by the assignment of the users to the towers. As the number of users in the system increases, interference levels increase and cell sizes decrease. This complicates the network planning problem since the capacity and coverage problems cannot be solved separately. To identify the optimal base station locations, traffic intensity and potential locations are determined in advance, then locations of base stations are chosen so as to satisfy minimum geographical coverage and minimum quality of service levels imposed by licensing agencies. This is implemented through two types of power control mechanisms. The power based power control mechanism, which is often discussed in literature, controls the power of the transmitted signal so that the power at the receiver exceeds a given threshold. On the other hand, the signal-to-interference ratio (SIR) based power control mechanism controls the power of the transmitted signal so that the ratio of the power of the received signal over the power of the interfering signals exceeds a given threshold. Solving the SIR based UMTS/W-CDMA network planning problem helps network providers in designing efficient and cost effective network infrastructure. In contrast to the power based UMTS/W-CDMA network planning problem, the solution of the SIR based model results in higher profits. In SIR based models, the power of the transmitted signals is decreased which lowers the interference and therefore increases the capacity of the overall network. Even though the SIR based power control mechanism is more efficient than the power based power control mechanism, it has a more complex implementation which has gained less attention in the network planning literature. In this thesis, a non-linear mixed integer problem that models the SIR based power control system is presented. The non-linear constraints are reformulated using linear expressions and the problem is exactly solved using a Benders decomposition approach. To overcome the computational difficulties faced by Benders decomposition, two novel extensions are presented. The first extension uses the analytic center cutting plane method for the Benders master problem, in an attempt to reduce the number of times the integer Benders master problem is solved. Additionally, we describe a heuristic that uses the analytic center properties to find feasible solutions for mixed integer problems. The second extension introduces a combinatorial Benders decomposition algorithm. This algorithm may be used for solving mixed integer problems with binary variables. In contrast to the classical Benders decomposition algorithm where the master problem is a mixed integer problem and the subproblem is a linear problem, this algorithm decomposes the problem into a mixed integer master problem and a mixed integer subproblem. The subproblem is then decomposed using classical Benders decomposition, leading to a nested Benders algorithm. Valid cuts are generated at the classical Benders subproblem and are added to the combinatorial Benders master problem to enhance the performance of the algorithm. It was found that valid cuts generated using the analytic center cutting plane method reduce the number of times the integer Benders master problem is solved and therefore reduce the computational time. It was also found that the combinatorial Benders reduces the complexity of the integer master problem by reducing the number of integer variables in it. The valid cuts generated within the nested Benders algorithm proved to be beneficial in reducing the number of times the combinatorial Benders master problem is solved and in reducing the computational time that the overall algorithm takes. Over 110 instances of the UMTS/W-CDMA network planning problem ranging from 20 demand points and 10 base stations to 140 demand points and 30 base stations are solved to optimality.