The energy transition taking place in various parts of the world will have many effects on the current energy systems as an increasing amount of intermittent power supply gets installed every year. In Sweden, just as many other countries, this will cause both challenges and opportunities for today´s energy producers. Challenges that may arise along with an increasingly fluctuating electricity production include both power deficits at certain times and regions but also hours of over-production which can cause electricity prices to drop significantly. Such challenges will have to be met by both dispatchable power generation and dynamic consumption. Conversely, actors prepared to adapt to the new climate by implementing new technologies or innovative business models could benefit from the transition towards a fully renewable energy system.  This thesis evaluates the techno-economic potential of green hydrogen production at a combined heat and power plant with the objective to provide decision support to a district heat and electricity producer in Sweden. It was in the company’s interest to investigate how hydrogen production could help reduce the production cost of district heat as well as contribute to the reduction of greenhouse gases.  In the project, two separate business models: Power-to-gas and Power-to-power were evaluated on the basis of technical and economic performance and environmental impact. To do this, a mathematical model of the CHP plant and the hydrogen systems was developed in Python which optimizes the operation based on costs. The business models were then simulated for two different years with each year representing a distinctly different electricity market situation.  The main conclusions of the study show that Power-to-gas could already be profitable at a hydrogen retail price of 40 SEK per kg, which is the projected retail price for the transportation sector. The demand today is however limited but is expected to grow fast in the near future, especially within heavy transportation. Another limiting factor for hydrogen production showed to be the availability of storage space, as hydrogen gas even at pressures up to 200 bar require large volumes.  Power-to-power for frequency regulation was found to not be economically justifiable as the revenue for providing grid services could not outweigh the high investment costs for any of the simulated years. This resulted in a high levelized cost of energy at over 3000 SEK per MWh which was mostly due to the low capacity factor of the power-to-power system.  Finally, green hydrogen has the potential of replacing fossil fuels in sectors that is difficult to reach with electricity, for example long-haul road transport or the shipping industry. Therefore, green hydrogen production in large scale could help decarbonize many of society’s fossil-heavy segments. By also serving as a grid-balancer, hydrogen production in a power-to-gas process has the potential of becoming an important part of a renewable energy system. / Energiomställningen som äger rum i olika delar av världen kommer att ha många effekter på de nuvarande energisystemen eftersom en ökande mängd väderberoende kraftproduktion installeras varje år. I Sverige, precis som många andra länder, kommer detta att medföra både utmaningar och möjligheter för dagens energiproducenter. Utmaningar som kan uppstå tillsammans med en alltmer fluktuerande elproduktion inkluderar både kraftunderskott vid vissa tider och regioner men också timmar av överproduktion som kan få elpriserna att sjunka avsevärt. Sådana utmaningar måste mötas av både planerbar kraftproduktion och dynamisk konsumtion. Omvänt kan aktörer som är beredda att anpassa sig till det nya klimatet genom att implementera ny teknik eller innovativa affärsmodeller dra nytta av övergången till ett helt förnybart energisystem.  Denna rapport utvärderar den tekno-ekonomiska potentialen för produktion av grön vätgas vid ett kraftvärmeverk med målet att ge beslutsstöd till en fjärrvärme- och elproducent i Sverige. Det var i företagets intresse att undersöka hur vätgasproduktion kan bidra till att sänka produktionskostnaden för fjärrvärme samt bidra till att minska växthusgaser.  I projektet utvärderades två separata affärsmodeller: Power-to-gas och Power-to-power baserat på teknisk och ekonomisk prestanda samt miljöpåverkan. För att kunna göra detta utvecklades en matematisk modell i Python av kraftvärmeverket och vätgassystemen som optimerar driften baserat på kostnader. Affärsmodellerna simulerades sedan för två olika års elpriser för att undersöka modellens prestanda i olika typer av elmarknader.  De viktigaste slutsatserna i studien visar att Power-to-gas redan kan vara lönsamt till ett vätgaspris på 40 SEK per kg, vilket är det förväntade marknadspriset på grön vätgas for transportsektorn. Efterfrågan är idag begränsad men förväntas växa snabbt inom en snar framtid, särskilt inom tung transport. En annan begränsande faktor för vätgasproduktion visade sig vara tillgången på lagringsutrymme, eftersom vätgas även vid tryck upp till 200 bar kräver stora volymer.  Power-to-power för frekvensreglering visade sig inte vara ekonomiskt försvarbart, eftersom intäkterna för att tillhandahålla nättjänster inte kunde uppväga de höga investeringskostnaderna under några av de simulerade åren. Detta resulterade i en hög LCOE på över 3000 SEK per MWh, vilket främst berodde på Power-to-power-systemets låga utnyttjandegrad.  Slutligen kan det sägas att grön vätgas har stor potential att ersätta fossila bränslen i sektorer som är svåra att elektrifiera, exempelvis tunga vägtransporter eller sjöfart. Därför kan storskalig grön vätgasproduktion hjälpa till att dekarbonisera många av samhällets fossiltunga segment. Genom att dessutom fungera som balansering har väteproduktion i en Power-to-gas-process potential att bli en viktig del av ett system med stor andel förnybar energi.

Due to the increase in electrical demand and renewable penetration, electrical utilities need to improve and optimize the grid infrastructure. Fundamental components in this grid infrastructure are transformers, which are designed conservatively on the base of a static rated power. However, load and weather change continuously and hence, transformers are not used in the most efficient way. For this reason a new technology has been developed: Dynamic transformer rating (DTR). By applying DTR, it is possible to load transformers above the nameplate rating without affecting their life time expectancy. This project goes one step further and uses DTR for the short term and long term wind farm planning. The optimal wind farm is designed by applying DTR to the power transformer of the farm. The optimization is carried out using a Mixed-Integer Linear Programming (MILP) model. In respect of the transformer thermal analysis, the linearized top oil model of IEEE Clause 7 is selected. The model is executed for 4 different types of power transformers: 63 MVA, 100 MVA, 200 MVA and 400 MVA. As result, it is obtained that the net present value for the investment and the capacity of the wind farm increase linearly with respect to the size of the transformer. Then, a sensitivity analysis is carried out by modifying the wind speed, the electricity price, the lifetime of the transformer and the selected weather data. From this sensitivity analysis, it is possible to conclude that wind resources and electricity price are key parameters for the feasibility of the wind farm. / På grund av ökningen av efterfrågan av elektricitet och förnybara energin, elförsörgingsföretag måste förbättras och elnätets infrastruktur måste optimeras. Grundläggande komponenter i elnätet är transformatorer, som är designade konservativt efter en statisk märkeffekt. Laster och vädret ändras dock kontinuerligt, detta betyder att transformatorer inte används på de mest effektiva sätten. Av denna anledning har en ny teknik utvecklats: Dynamisk lastbarhet hos transformatorer (DTR). Genom att applicera DTR, gör det möjligt att belasta en transformator högre än märkdata utan att påverka den förväntade livslängden. Detta projekt går ett steg längre och använder DTR för kort och lång sikts vindkraftparkplaneringar. Den optimala vindkraftparken är designad genom att använda DLT på krafttransformatorn för vindkraftsparken. Optimeringen utförst med hjälp av Mixed-Integer Linear programming (MILP) modell. Gällande transformatorns termiska analys, så valdes den linjäriserade toppoljemodellen av IEEE Clause 7. Modellen var utförd för fyra olika krafttransformatorer: 63 MVA, 100 MVA, 200 MVA och 400 MVA. Resultatet blev att nettonuvärdet för investeringen och kapaciteten av vindkraftsparken ökade linjärt med avseende på storleken på transformatorn. En känslighetsanalys var utförd genom att ändra vindhastigheten, elpriset, livstiden av transformatorn och de valda väderdata. Från känslighetsanalysen så var det möjligt att dra slutsatsen att vindresurser och elpriset är nyckelparametrar för vindkraftsparkens genomförbarhet.

This thesis examines the optimal scheduling of a hydroelectric power plant with cascaded reservoirs each with multiple generating units under uncertainty after testing three linearization methods. These linearization methods are Successive Linear Programming, Piecewise Linear Approximations, and a Hybrid of the two together. There are two goals of this work. The first goal of this work aims to replace the nonconvex mixed-integer nonlinear program (MINLP) with a computationally efficient linearized mixed-integer linear program (MILP) that will be capable of finding a high quality solution, preferably the global optimum. The second goal is to implement a stochastic approach on the linearized method in a pseudo-rolling horizon method which keeps the ending time step fixed. Overall, the Hybrid method proved to be a viable replacement and performs well in the pseudo-rolling horizon tests. / Thesis / Master of Applied Science (MASc)

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.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programs (IPs) are mathematical models that can provide an optimal solution to a variety of different problems. They have been used to reduce costs and optimize organizations. Additionally, IPs are NP-complete resulting in many IPs that cannot be solved. Cutting planes or valid inequalities have been used to decrease the time required to solve IPs. Lifting is a technique that strengthens existing valid inequalities. Lifting inequalities can result in facet defining inequalities, which are the theoretically strongest valid inequalities. Because of these properties, lifting procedures are used in software to reduce the time required to solve an IP. The thesis introduces a new algorithm for exact synchronized simultaneous uplifting over an arbitrary initial inequality for knapsack problems. Synchronized Simultaneous Lifting (SSL) is a pseudopolynomial time algorithm requiring O(nb+n[superscript]3) effort to solve. It exactly uplifts two sets simultaneously into an initial arbitrary valid inequality and creates multiple inequalities of a particular form. This previously undiscovered class of inequalities generated by SSL can be facet defining. A small computational study shows that SSL is quick to execute, requiring on average less than a quarter of a second. Additionally, applying SSL inequalities to a knapsack problem enabled commercial software to solve problems that it could not solve without them.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programs (IP) are used in companies and organizations across the world to reach financial and time-related goals most often through optimal resource allocation and scheduling. Unfortunately, integer programs are computationally difficult to solve and in some cases the optimal solutions are unknown even with today’s advanced computing machines. Lifting is a technique that is often used to decrease the time required to solve an IP to optimality. Lifting begins with a valid inequality and strengthens it by changing the coefficients of variables in the inequality. Often times, this technique can result in facet defining inequalities, which are the theoretically strongest inequalities. This thesis introduces a new type of lifting called synchronized simultaneous lifting (SSL). SSL allows for multiple sets of simultaneously lifted variables to be simultaneously lifted which generates a new class of inequalities that previously would have required an oracle to be found. Additionally, this thesis describes an algorithm to perform synchronized simultaneous lifting for a binary knapsack inequality called the Synchronized Simultaneous Lifting Algorithm (SSLA). SSLA is a quadratic time algorithm that will exactly simultaneously lift two sets of simultaneously lifted variables. Short computational studies show SSLA can sometimes solve IPs to optimality that CPLEX, an advanced integer programming solver, alone cannot solve. Specifically, the SSL cuts allowed a 76 percent improvement over CPLEX alone.

The primary aim of this thesis is to develop effective solution techniques for large-scale maritime inventory routing problems that possess a core substructure common in many real-world applications. We use the term “large-scale” to refer to problems whose standard mixed-integer linear programming (MIP) formulations involve tens of thousands of binary decision variables and tens of thousands of constraints and require days to solve on a personal computer. Although a large body of literature already exists for problems combining vehicle routing and inventory control for road-based applications, relatively little work has been published in the realm of maritime logistics. A major contribution of this research is in the advancement of novel methods for tackling problems orders of magnitude larger than most of those considered in the literature. Coordinating the movement of massive vessels all around the globe to deliver large quantities of high value products is a challenging and important problem within the maritime transportation industry. After introducing a core maritime inventory routing model to aid decision-makers with their coordination efforts, we make three main contributions. First, we present a two-stage algorithm that exploits aggregation and decomposition to produce provably good solutions to complex instances with a 60-period (two-month) planning horizon. Not only is our solution approach different from previous methods discussed in the maritime transportation literature, but computational experience shows that our approach is promising. Second, building on the recent successes of approximate dynamic programming (ADP) for road-based applications, we present an ADP procedure to quickly generate good solutions to maritime inventory routing problems with a long planning horizon of up to 365 periods. For instances with many ports (customers) and many vessels, leading MIP solvers often require hours to produce good solutions even when the planning horizon is limited to 90 periods. Our approach requires minutes. Our algorithm operates by solving many small subproblems and, in so doing, collecting and learning information about how to produce better solutions. Our final research contribution is a polyhedral study of an optimization problem that was motivated by maritime inventory routing, but is applicable to a more general class of problems. Numerous planning models within the chemical, petroleum, and process industries involve coordinating the movement of raw materials in a distribution network so that they can be blended into final products. The uncapacitated fixed-charge transportation problem with blending (FCTPwB) that we study captures a core structure encountered in many of these environments. We model the FCTPwB as a mixed-integer linear program and derive two classes of facets, both exponential in size, for the convex hull of solutions for the problem with a single consumer and show that they can be separated in polynomial time. Finally, a computational study demonstrates that these classes of facets are effective in reducing the integrality gap and solution time for more general instances of the FCTPwB.

Lattices are an easy and clean class of periodic arrangements that are not only discrete but associated with algebraic structures. We will specifically discuss applying lattices theory to computing the area of polygons in the plane and some optimization problems. This thesis will details information about Pick's Theorem and the higher-dimensional cases of Ehrhart Theory. Closely related to Pick's Theorem and Ehrhart Theory is the Frobenius Problem and Integer Knapsack Problem. Both of these problems have higher-dimension applications, where the difficulties are similar to those of Pick's Theorem and Ehrhart Theory. We will directly relate these problems to optimization problems and operations research.

Thesis (PhD)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: The (classical) domination number of a graph is the cardinality of a smallest subset of its vertex set with the property that each vertex of the graph is in the subset or adjacent to a vertex in the subset. Since its introduction to the literature during the early 1960s, this graph parameter has been researched extensively and nds application in the generic facility location problem where a smallest number of facilities must be located on the vertices of the graph, at most one facility per vertex, so that there is at least one facility in the closed neighbourhood of each vertex of the graph. The placement constraint in the above application may be relaxed in the sense that multiple facilities may possibly be located at a vertex of the graph and the adjacency criterion may be strengthened in the sense that a graph vertex may possibly be required to be adjacent to multiple facilities. More speci cally, the number of facilities that can possibly be located at the i-th vertex of the graph may be restricted to at most ri 0 and it may be required that there should be at least si 0 facilities in the closed neighbourhood of this vertex. If the graph has n vertices, then these restriction and su ciency speci cations give rise to a pair of vectors r = [r1,....., rn] and s = [s1,....., sn]. The smallest number of facilities that can be located on the vertices of a graph satisfying these generalised placement conditions is called the hr; si-domination number of the graph. The classical domination number of a graph is therefore its hr; si-domination number in the special case where r = [1,....., 1] and s = [1,....., 1]. The exact values of the hr; si-domination number, or at least upper bounds on the hr; si- domination number, are established analytically in this dissertation for arbitrary graphs and various special graph classes in the general case, in the case where the vector s is a step function and in the balanced case where r = [r,....., r] and s = [s,....., s]. A linear algorithm is put forward for computing the hr; si-domination number of a tree, and two exponential-time (but polynomial-space) algorithms are designed for computing the hr; si- domination number of an arbitrary graph. The e ciencies of these algorithms are compared to one another and to that of an integer programming approach toward computing the hr; si- domination number of a graph. / AFRIKAANSE OPSOMMING: Die (klassieke) dominasiegetal van 'n gra ek is die grootte van 'n kleinste deelversameling van die gra ek se puntversameling met die eienskap dat elke punt van die gra ek in die deelversameling is of naasliggend is aan 'n punt in die deelversameling. Sedert die verskyning van hierdie gra ekparameter in the literatuur gedurende die vroeë 1960s, is dit deeglik nagevors en vind dit neerslag in die generiese plasingstoepassing waar 'n kleinste getal fasiliteite op die punte van die gra ek geplaas moet word, hoogstens een fasiliteit per punt, sodat daar minstens een fasiliteit in die geslote buurpuntversameling van elke punt van die gra ek is. Die plasingsbeperking in die bogenoemde toepassing mag egter verslap word in die sin dat meer as een fasiliteit potensieel op 'n punt van die gra ek geplaas kan word en verder mag die naasliggendheidsvereiste verhoog word in die sin dat 'n punt van die gra ek moontlik aan veelvuldige fasiliteite naasliggend moet wees. Gestel dat die getal fasiliteite wat op die i-de punt van die gra ek geplaas mag word, beperk word tot hoogstens ri 0 en dat hierdie punt minstens si 0 fasiliteite in die geslote buurpuntversameling daarvan moet hê. Indien die gra ek n punte bevat, gee hierdie plasingsbeperkings en -vereistes aanleiding tot die paar vektore r = [r1, .... , rn] en s = [s1,...., sn]. Die kleinste getal fasiliteite wat op die punte van 'n gra ek geplaas kan word om aan hierdie veralgemeende voorwaardes te voldoen, word die hr; si-dominasiegetal van die gra ek genoem. Die klassieke dominasiegetal van 'n gra ek is dus die hr; si-dominasiegetal daarvan in die spesiale geval waar r = [1,......, 1] en s = [1,....., 1]. In hierdie verhandeling word die eksakte waardes van, of minstens grense op, die hr; si-dominasiegetal van arbitrêre gra eke of spesiale klasse gra eke analities bepaal vir die algemene geval, vir die geval waar s 'n trapfunksie is, en vir die gebalanseerde geval waar r = [r,....., r] en s = [s,....., s]. 'n Lineêre algoritme word ook daargestel vir die berekening van die hr; si-dominasiegetal van 'n boom, en twee eksponensiële-tyd (maar polinoom-ruimte) algoritmes word ontwerp vir die berekening van die hr; si-dominasiegetal van 'n arbitrêre gra ek. Die doeltre endhede van hierdie algoritmes word met mekaar vergelyk en ook met dié van 'n heeltallige programmeringsbenadering tot die bepaling van die hr; si-dominasiegetal van 'n gra ek.

Approved for public release, distribution is unlimited / Tomahawk cruise missiles (TCM) cost over one million dollars and are in short supply. U.S. Navy ships require TCM and other conventional ammunition be loaded in appropriate amounts prior to deploying to sea. A typical deployment lasts for six months and, when completed, any remaining ammunition must be unloaded and made ready for other deploying ships. For ships under Commander, Naval Surface Force U.S. Pacific Fleet (SURFPAC), about 3,500 tons of ammunition must be loaded and unloaded annually; this currently costs 14 million dollars for just pilots, tugboats and fuel. This thesis formulates and solves an integer linear program, Surface Navy Scheduler (SNSKED), to prescribe an ammunition load and unload schedule for San Diego homeported ships. SNSKED seeks a schedule with minimized costs subject to constraints on ships availability, port capabilities and support assets. We test SNSKED on a realistic quarterly scenario consisting of 19 combatant ships, three weapons stations, two ammunition ships, five mission types, two ammunition types, and three ways of loading ammunition. SNSKED provides optimal schedules that reduce costs by over 16 percent. We also use SNSKED to evaluate different operational policies, ammunition port utilization, and ammunition loading times. / Lieutenant Commander, United States Navy