The thesis presents models for short term planning (24 hours) of a hyro dominated hydrothermal power system. The purpose of the models is to minimizae the system operation costs to provide a forecasted load and keep enough spinning reserve. / This thesis presents models for short term planning (24 hours) of a hydro dominated hydrothermal power system. The purpose of the models is to minimize the system operation cost to provide a forecasted load and keep enough spinning reserve.   The thesis focuses on two issues in hydro power modelling. The first issue is the relationship between water discharged and power generated. This relationship is a non-linear and non-convex function. If the plant has several units, the efficiency of the plant will have local maximums, so called local best-efficiency points. The second issue is to take into account the cost of start-ups of hydro units in the planning.   The hydro model is mixed-integer. Discharg􀁐s are allowed at zero flow, the local best-efficiency points and on the continuous part between the local best-efficiency point with the highest flow and the point with maximum flow. This last continuous part is modelled as a linear function. In order to get data for the start-up cost a survey among the largest power producers in Sweden has been made, where three questions about start-ups of hydro power units has been asked: What causes the costs in the start-up?, How much does a start-up cost? and How do start-ups effect the short-term scheduling strategies of power producers in Sweden? The results show that a fair estimate of the start-up cost is about $3/MW nominal output. For the thermal plants a standard model with polynomial operation cost, start-up costs and ramp-rate constraints has been used. The model also includes the possibilities of purchasing and selling power to forecasted prices.   The planning problem is formulated as a mathematical programming problem. The solution technique uses Lagrange relaxation to decompose the problem into subproblems. There will be one subproblem for each hydro and thermal plant. In order to find good feasible solutions a heuristic technique to change the integer variables in the hydro system has been developed. The Lagrange multipliers are updated with the subgradient method.   The models are tested in three different load situations; a winter day (heavy load), an autumn day (medium load) and a summer day (light load). The result shows that the method gives near optimal schedules in reasonable computation time in cases with a normal part of the thermal units committed. The assumed start-up cost results in that hydro units almost never are started or stopped for one hour only. / <p>QC 20161206</p>

The focus of this thesis is the development and solution of problems that simultaneously involve the planning of the location of facilities and transportation decisions from such facilities to consumers. This has been termed integrated distribution planning problems with practical application in logistics and manufacturing. In this integration, different planning horizons of short, medium and long terms are involved with the possibility of reaching sub-optimal decisions being likely when the planning horizons are considered separately. Two categories of problems were considered under the integrated distribution models. The first is referred to as the Step-Fixed Charge Location and Transportation Problem (SFCLTP). The second is termed the Fixed Charge Solid Location and Transportation Problem (FCSLTP). In these models, the facility location problem is considered to be a strategic or long term decision. The short to medium-term decisions considered are the Step-Fixed Charge Transportation Problem (SFCTP) and the Fixed Charge Solid Transportation Problem (FCSTP). Both SFCTP and FCSTP are different extensions to the classical transportation problem, requiring a trade-off between fixed and variable costs along the transportation routes to minimize total transportation costs. Linearization and subsequent local improvement search techniques were developed to solve the SFCLTP. The first search technique involved the development of a hands-on solution including a numerical example. In this solution technique, linearization was employed as the primal solution, following which structured perturbation logic was developed to improve on the initial solution. The second search technique proposed also utilized the linearization principle as a base solution in addition to some heuristics to construct transportation problems. The resulting transportation problems were solved to arrive at a competitive solution as regards effectiveness (solution value) compared to those obtainable from standard solvers such as CPLEX. The FCSLTP is formulated and solved using the CPLEX commercial optimization suite. A Lagrange Relaxation Heuristic (LRH) and a Hybrid Genetic Algorithm (GA) solution of the FCSLTP are presented as alternative solutions. Comparative studies between the FCSTP and the FCSLTP formulation are also presented. The LRH is demonstrated with a numerical example and also extended to hopefully generate improved upper bounds. The CPLEX solution generated better lower bounds and upper bound when compared with the extended LRH. However, it was observed that as problem size increased, the solution time of CPLEX increased exponentially. The FCSTP was recommended as a possible starting solution for solving the FCSLTP. This is due to a lower solution time and its feasible solution generation illustrated through experimentation. The Hybrid Genetic Algorithm (HGA) developed integrates cost relaxation, greedy heuristic and a modified stepping stone method into the GA framework to further explore the solution search space. Comparative studies were also conducted to test the performance of the HGA solution with the classical Lagrange heuristics developed and CPLEX. Results obtained suggests that the performance of HGA is competitive with that obtainable from a commercial solver such as CPLEX. / Thesis (PhD)--University of Pretoria, 2019. / Industrial and Systems Engineering / PhD / Unrestricted

Lagrangian relaxation is a successful solution approach for many combinatorial optimisation problems, one of them being the train timetabling problem (TTP). We model this problem using time expanded networks for the single train schedules and coupling constraints to enforce restrictions like station capacities and headway times. Lagrangian relaxation of these coupling constraints leads to shortest path subproblems in the time expanded networks and is solved using a proximal bundle method. However, large instances of our practical partner Deutsche Bahn lead to computationally intractable models. In this thesis we develop two new algorithmic techniques to improve the solution process for this kind of optimisation problems. The first new technique, Dynamic Graph Generation (DGG), aims at improving the computation of the shortest path subproblems in large time expanded networks. Without sacrificing any accuracy, DGG allows to store only small parts of the networks and to dynamically extend them whenever the stored part proves to be too small. This is possible by exploiting the properties of the objective function in many scheduling applications to prefer early paths or due times, respectively. We prove that DGG can be implemented very efficiently and its running time and the size of nodes that have to be stored additionally does not depend on the size of the time expanded network but only on the length of the train routes. The second technique is an asynchronous and parallel bundle method (APBM). Traditional bundle methods require one solution of each subproblem in each iteration. However, many practical applications, e.g. the TTP, consist of rather loosely coupled subproblems. The APBM chooses only small subspaces corresponding to the Lagrange multipliers of strongly violated coupling constraints and optimises only these variables while keeping all other variables fixed. Several subspaces of disjoint variables may be chosen simultaneously and are optimised in parallel. The solutions of the subspace problem are incorporated into the global data as soon as it is available without any synchronisation mechanism. However, in order to guarantee convergence, the algorithm detects automatically dependencies between different subspaces and respects these dependencies in future subspace selections. We prove the convergence of the APBM under reasonable assumptions for both, the dual and associated primal aggregate data. The APBM is then further extended to problems with unknown dependencies between subproblems and constraints in the Lagrangian relaxation problem. The algorithm automatically detects these dependencies and respects them in future iterations. Again we prove the convergence of this algorithm under reasonable assumptions. Finally we test our solution approach for the TTP on some real world instances of Deutsche Bahn. Using an iterative rounding heuristic based on the approximate fractional solutions obtained by the Lagrangian relaxation we are able to compute feasible schedules for all trains in a subnetwork of about 10% of the whole German network in about 12 hours. In these timetables 99% of all passenger trains could be scheduled with no significant delay and the travel time of the freight trains could be reduced by about one hour on average.

The Constrained Shortest Path Problem (CSPP) consists of finding the shortest path in a graph or network that satisfies one or more resource constraints. Without these constraints, the shortest path problem can be solved in polynomial time; with them, the CSPP is NP-hard and thus far no polynomial-time algorithms exist for solving it optimally. The problem arises in a number of practical situations. In the case of vehicle path planning, the vehicle may be an aircraft flying through a region with obstacles such as mountains or radar detectors, with an upper bound on the fuel consumption, the travel time or the risk of attack. The vehicle may be a submarine travelling through a region with sonar detectors, with a time or risk budget. These problems all involve a network which is a discrete model of the physical domain. Another example would be the routing of voice and data information in a communications network such as a mobile phone network, where the constraints may include maximum call delays or relay node capacities. This is a problem of current economic importance, and one for which time-sensitive solutions are not always available, especially if the networks are large. We consider the simplest form of the problem, large grid networks with a single side constraint, which have been studied in the literature. This thesis explores the application of Constraint Programming combined with Lagrange Relaxation to achieve optimal or near-optimal solutions of the CSPP. The following is a brief outline of the contribution of this thesis. Lagrange Relaxation may or may not achieve optimal or near-optimal results on its own. Often, large duality gaps are present. We make a simple modification to Dijkstra’s algorithm that does not involve any additional computational work in order to generate an estimate of path time at every node. / We then use this information to constrain the network along a bisecting meridian. The combination of Lagrange Relaxation (LR) and a heuristic for filtering along the meridian provide an aggressive method for finding near-optimal solutions in a short time. Two network problems are studied in this work. The first is a Submarine Transit Path problem in which the transit field contains four sonar detectors at known locations, each with the same detection profile. The side constraint is the total transit time, with the submarine capable of 2 speeds. For the single-speed case, the initial LR duality gap may be as high as 30%. The first hybrid method uses a single centre meridian to constrain the network based on the unused time resource, and is able to produce solutions that are generally within 1% of optimal and always below 3%. Using the computation time for the initial Lagrange Relaxation as a baseline, the average computation time for the first hybrid method is about 30% to 50% higher, and the worst case CPU times are 2 to 4 times higher. The second problem is a random valued network from the literature. Edge costs, times, and lengths are uniform, randomly generated integers in a given range. Since the values given in the literature problems do not yield problems with a high duality gap, the values are varied and from a population of approximately 100,000 problems only the worst 200 from each set are chosen for study. These problems have an initial LR duality gap as high as 40%. A second hybrid method is developed, using values for the unused time resource and the lower bound values computed by Dijkstra’s algorithm as part of the LR method. The computed values are then used to position multiple constraining meridians in order to allow LR to find better solutions. / This second hybrid method is able to produce solutions that are generally within 0.1% of optimal, with computation times that are on average 2 times the initial Lagrange Relaxation time, and in the worst case only about 5 times higher. The best method for solving the Constrained Shortest Path Problem reported in the literature thus far is the LRE-A method of Carlyle et al. (2007), which uses Lagrange Relaxation for preprocessing followed by a bounded search using aggregate constraints. We replace Lagrange Relaxation with the second hybrid method and show that optimal solutions are produced for both network problems with computation times that are between one and two orders of magnitude faster than LRE-A. In addition, these hybrid methods combined with the bounded search are up to 2 orders of magnitude faster than the commercial CPlex package using a straightforward MILP formulation of the problem. Finally, the second hybrid method is used as a preprocessing step on both network problems, prior to running CPlex. This preprocessing reduces the network size sufficiently to allow CPlex to solve all cases to optimality up to 3 orders of magnitude faster than without this preprocessing, and up to an order of magnitude faster than using Lagrange Relaxation for preprocessing. Chapter 1 provides a review of the thesis and some terminology used. Chapter 2 reviews previous approaches to the CSPP, in particular the two current best methods. Chapter 3 applies Lagrange Relaxation to the Submarine Transit Path problem with 2 speeds, to provide a baseline for comparison. The problem is reduced to a single speed, which demonstrates the large duality gap problem possible with Lagrange Relaxation, and the first hybrid method is introduced. / Chapter 4 examines a grid network problem using randomly generated edge costs and weights, and introduces the second hybrid method. Chapter 5 then applies the second hybrid method to both network problems as a preprocessing step, using both CPlex and a bounded search method from the literature to solve to optimality. The conclusion of this thesis and directions for future work are discussed in Chapter 6.

Wir betrachten ein Kraftwerkssystem mit thermischen Blöcken und Pumpspeicherwerken und entwickeln dafür ein Modell für den kostenoptimalen Wochenbetrieb. Auf Grund der Ungewißheit des Bedarfs an elektrischer Energie ist das mathematische Modell ein mehrstufiges stochastisches Problem. Dieses Modell beinhaltet viele gemischt-ganzzahlige stochastische Entscheidungsvariablen. Die Variablen einzelner Einheiten sind aber nur durch wenige Nebenbedingungen miteinander verbunden, welches die Zerlegung in stochastische Teilprobleme erleichtert. Diese stochastischen Teilprobleme besitzen deterministische Analoga, deren Lösungsverfahren entsprechend erweitert werden können. In dieser Arbeit werden ein Abstiegsverfahren für stochastische Speicherprobleme und eine Erweiterung der dynamischen Programmierung auf stochastische Probleme betrachtet. Die Lösung des dualen Problems führt zu Schattenpreisen, die bestimmte Einsatzentscheidungen bevorteilen. Die Heuristik zur Suche von primalen zulässigen Punkten wertet eine Folge von zugeordneten Economic-Dispatch-Problemen aus. Die Kombination der Einschränkung auf dual bevorzugte Fahrweisen (Lagrangian reduction) mit der Auswertung einer Folge von Economic-Dispatch-Problemen (Facettensuche) führt zu einem effizienten Verfahren. Die numerischen Ergebnisse an Hand realistischer Daten eines deutschen Versorgungsunternehmens rechtfertigen diesen Zugang. / We consider a power generation system comprising thermal units and pumped hydro storage plants, and introduce a model for its weekly cost-optimal operation. Due to the uncertainty of the load, the mathematical model represents a dynamic (multi-stage) stochastic program. The model involves a large number of mixed-integer (stochastic) decisions but its constraints are loosely coupled across operating power units. The coupling structure is used to design a stochastic Lagrangian relaxation method, which leads to a decomposition into stochastic single unit subproblems. The stochastic subproblems have deterministic counterparts, which makes it easy to develop algorithms for the stochastic problems. In this paper, a descent method for stochastic storage problems and an extension of dynamic programming towards stochastic programs are developed. The solution of the dual problem provides multipliers leading to preferred schedules (binary primal variables). The crossover heuristics evaluates the economic dispatch problems corresponding to a sequence of such preferred schedules. The combination of the restriction on dual preferred schedules (Lagrangian reduction) with the evaluation of a sequence (facet search) leads to an efficient method. The numerical results on realistic data of a German utility justify this approach.

No description available.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Made available in DSpace on 2016-08-17T14:52:49Z (GMT). No. of bitstreams: 1 Aniceto_de_Deus_Pereira_Neto.pdf: 1168768 bytes, checksum: adc4488efe00f3201345ff8a783ac6bb (MD5) Previous issue date: 2008-07-25 / The restructuring and deregulation of electricity markets has caused signi¯cant changes in electrical power systems in several countries. This process has result in a market-based competition by creating an open market environment. In this new environment each generation company runs the Unit Commitment to maximize their pro¯ts, and have no obligation to meet the energy and spinning reserve demands, as happened in the past. With this new structure, the Unit Commitment problem has received special attention, since generation companies in actual model always seek the maximum pro¯t without concern to serve all demands. On the other hand, there is the system operator, which always seeks to optimize overall system at the lowest cost. So, there are two di®erent situations into this competitive market environment: generators seeking the maximum bene¯t without concern to the system security operating, and independent system operator seeking always operate the system safely and at less cost. This work presents the mathematical models and the solution Unit Commitment problem, which was implemented considering two view points: the generation companies and the system independent operator views. Moreover, an auction model is extended to PRD in a horizon of 24 hours. This auction model simulates the interaction between generators and system operator to meet demands and security of the system. The idea is to stimulate the players to o®er products to energy (primary) and reserve (Ancilar Service) markets using only prices o®ered by market operator for each product. This iterative process is ¯nalized when generators supply su±cient to meet demand, and not cause any violation on °ow limits in transmission lines. The solution method proposed for Unit Commitment is based on evolution strategies and Lagrange Relaxation, resulting in a robust hybrid algorithm. The method have been validated in a test system composed of 6 buses, 7 transmission lines and 10 generating units. The results showed the e±ciency of the hybrid model proposed, which was able to solve the unit commitment problem in its various models considered here. / A reestruturação dos mercados de energia elétrica provocou mudanças significativas nos sistemas elétricos de potência de diversos países. Neste novo ambiente, cada empresa de geração executa individualmente o Pré-Despacho para maximizar seus benefícios financeiros, e não têm a obrigação em atender suas demandas de potência e reserva girante, como acontecia no modelo tradicional. Por outro lado existe o operador do sistema, o qual sempre busca a otimização global do sistema ao menor custo. Assim, têm-se duas situações distintas neste ambiente competitivo: os geradores buscando o máximo benefício sem preocupação com a segurança operativa do sistema, e o operador independente buscando sempre operar o sistema de forma segura e ao menor custo. Este trabalho apresenta as modelagens matemáticas e a solução do Pré- Despacho executado sob os dois pontos de vista: dos agentes de geração e do operador independente do sistema. Além do mais, um modelo de leilão é estendido para o PRD num horizonte de 24 horas. Este modelo simula a interação entre os agentes de geração e o operador do sistema na busca por uma solução única que concilie o interesse de ambos. A idéia é estimular os agentes geradores a ofertarem os produtos para os mercados de energia (primário) e de reserva (Serviço Ancilar) mediante oferta de preços pelo operador do mercado para os respectivos produtos. Esse procedimento iterativo é finalizado quando a oferta dos geradores for suficiente para atender completamente a demanda e, não provocar violações em nenhum limite de fuxos na malha de transmissão. O método de solução proposto para o Pré-Despacho é baseado em estratégias evolutivas e Relaxação de Lagrange, resultando em um modelo híbrido robusto. Os modelos e técnicas foram validados em um sistema teste composto por 6 barras, 7 linhas de transmissão e 10 unidades geradoras. Os resultados obtidos demonstraram a eficiência do método de solução, o qual se mostrou capaz de resolver o problema de Pré-Despacho nas suas diversas modelagens utilizadas.

Lagrangian relaxation is a successful solution approach for many combinatorial optimisation problems, one of them being the train timetabling problem (TTP). We model this problem using time expanded networks for the single train schedules and coupling constraints to enforce restrictions like station capacities and headway times. Lagrangian relaxation of these coupling constraints leads to shortest path subproblems in the time expanded networks and is solved using a proximal bundle method. However, large instances of our practical partner Deutsche Bahn lead to computationally intractable models. In this thesis we develop two new algorithmic techniques to improve the solution process for this kind of optimisation problems. The first new technique, Dynamic Graph Generation (DGG), aims at improving the computation of the shortest path subproblems in large time expanded networks. Without sacrificing any accuracy, DGG allows to store only small parts of the networks and to dynamically extend them whenever the stored part proves to be too small. This is possible by exploiting the properties of the objective function in many scheduling applications to prefer early paths or due times, respectively. We prove that DGG can be implemented very efficiently and its running time and the size of nodes that have to be stored additionally does not depend on the size of the time expanded network but only on the length of the train routes. The second technique is an asynchronous and parallel bundle method (APBM). Traditional bundle methods require one solution of each subproblem in each iteration. However, many practical applications, e.g. the TTP, consist of rather loosely coupled subproblems. The APBM chooses only small subspaces corresponding to the Lagrange multipliers of strongly violated coupling constraints and optimises only these variables while keeping all other variables fixed. Several subspaces of disjoint variables may be chosen simultaneously and are optimised in parallel. The solutions of the subspace problem are incorporated into the global data as soon as it is available without any synchronisation mechanism. However, in order to guarantee convergence, the algorithm detects automatically dependencies between different subspaces and respects these dependencies in future subspace selections. We prove the convergence of the APBM under reasonable assumptions for both, the dual and associated primal aggregate data. The APBM is then further extended to problems with unknown dependencies between subproblems and constraints in the Lagrangian relaxation problem. The algorithm automatically detects these dependencies and respects them in future iterations. Again we prove the convergence of this algorithm under reasonable assumptions. Finally we test our solution approach for the TTP on some real world instances of Deutsche Bahn. Using an iterative rounding heuristic based on the approximate fractional solutions obtained by the Lagrangian relaxation we are able to compute feasible schedules for all trains in a subnetwork of about 10% of the whole German network in about 12 hours. In these timetables 99% of all passenger trains could be scheduled with no significant delay and the travel time of the freight trains could be reduced by about one hour on average.