User: Guest  Login
If you experience problems opening the document, please try this link.
Original title:
A Polyhedral Analysis of Start-up Process Models in Unit Commitment Problems
Translated title:
Die Polyedrische Struktur von Startprozess-Modellen in der Kraftwerkseinsatzplanung
Author:
Silbernagl, Matthias
Year:
2016
Document type:
Dissertation
Faculty/School:
Fakultät für Mathematik
Advisor:
Gritzmann, Peter (Prof. Dr.)
Referee:
Gritzmann, Peter (Prof. Dr.); Martin, Alexander (Prof. Dr.); Hamacher, Thomas (Prof. Dr.)
Language:
en
Subject group:
MAT Mathematik
Keywords:
Unit Commitment, Mixed Integer Programming, Integrality Gap, Valid Inequalities, Extended Formulation, Start-up Costs, Start-up Cost Epigraph, Start-up Process, Start-up Types, Power Plant Temperatures, Residual Temperature Inequalities, Binary Tree Inequalities, Integration of Renewables
Translated keywords:
Einsatzplanung, Kraftwerkseinsatzplanung, Gemischt-Ganzzahlige Programmierung, Ganzzahligkeitslücke, Nebenbedingungen, Erweiterte Formulierungen, Startkosten, Startkostenepigraph, Startprozess, Starttypen, Kraftwerkstemperaturen, Integration Erneuerbarer Energien
TUM classification:
MAT 500d; MAT 910d
Abstract:
This work investigates mixed-integer start-up models in Unit Commitment problems with a focus on the underlying polyhedral structure and on practical applicability. Despite more than a century of research, this problem family is far from being solved. Moreover, the structure of the problem has recently been shifted by the introduction of renewable energy sources in significant quantities. The production of the prevalent renewable energy sources, wind and solar energy, is inherently volatile, aggravating the task of keeping electricity production and demand in balance. As a consequence, conventional units need to change production level and start up more often, resulting in a higher share of start-up costs among the total costs. Hence, accurate models of start-ups, and in particular of start-up costs, become a priority. After a polyhedral analysis of the start-up cost function, we present two families of models based on different approaches: The first type of formulations explicitly captures the temperature of a power plant and models the typical inversely exponential start-up costs. The second type of formulations classifies each start-up by binary variables, allowing arbitrary costs and power trajectories. The practical relevance of both models is experimentally demonstrated using data of the German power system. We start by analyzing the start-up cost epigraphs, which leads to a linear, irredundant H-representation of the epigraph of the start-up cost function in a single period with a linear separation algorithm (joint work with René Brandenberg and Matthias Huber), an exponential H-representation of the epigraph of the start-up cost function summed over all periods, which is irredundant in the general case and possesses a linear separation algorithm (joint work with René Brandenberg and Matthias Huber), and an exponential class of facets of the epigraph of the start-up cost function combined for all periods. By explicitly modeling the temperature of a unit, we provide the extended formulation of the epigraph of the summed start-up costs with O(T) variables and O(T2) inequalities (joint work with René Brandenberg and Matthias Huber). Only O(T) of these inequalities are necessary to model the start-up costs in the binary case, while the remaining O(T2) inequalities tighten the linear relaxation and can be separated in O(T). This temperature formulation can be extended to incorporate the start-up process. State-of-the-art start-up process models classify each start-up as one of S types. By interpreting these types as flows in a particular network, we significantly tighten and generalize these models such that the resulting polyhedron with O(ST) variables and O(T2) inequalities is an extended formulation of the epigraph of the start-up costs in all periods. In the binary case, the start-up costs are modeled correctly by O(ST) of these inequalities, and the remaining inequalities tighten the linear relaxation and can be separated in O(T2). The start-up process models from the literature still apply to these start-up types. We compare our models experimentally to the state-of-the-art using a model of the German Power system. At the hands of scenarios of the years 2011 and of 2025, we substantiate our theoretical results: The extended formulations presented in this thesis outperform the existing formulations both in terms of solution time and integrality gap.
Translated abstract:
Diese Arbeit untersucht die gemischt-ganzzahlige Modellierung von Startvorgängen in der Kraftwerkseinsatzplanung mit Fokus auf den zugrundeliegenden polyedrischen Strukturen und auf der praktischen Anwendbarkeit. Trotz über einem Jahrhundert an Forschung ist diese Problemfamilie weit von einer Lösung entfernt. Außerdem hat sich die Struktur des Problems in den letzten Jahren durch die gesteigerte Nutzung von erneuerbaren Energien deutlich verändert. Die Produktion der am stärksten eingesetzten erneuerbaren Energien, der Wind- und Sonnenenergie, ist von Natur aus unstetig und erschwert damit die Koordination von Stromproduktion und -nachfrage. Als Konsequenz müssen konventionelle Kraftwerke ihren Produktionslevel häufiger anpassen und öfter hoch- und runterfahren, was den Anteil von Startkosten an den Gesamtkosten deutlich erhöht. Deshalb kommt der sorgfältigen Modellierung des Startvorgangs, und insbesondere der Startkosten, eine hohe Bedeutung zu. Nach einer polyedrischen Analyse der Startkostenfunktion stellen wir zwei Familien von Modellen basierend auf unterschiedlichen Ansätzen vor: Die erste Art von Formulierungen modelliert den Temperaturverlauf eines Kraftwerks explizit und bildet damit die typischen invers exponentiellen Startkosten ab. Die zweite Art von Formulierungen typisiert Startvorgänge durch Binärvariablen und erlaubt dadurch beliebige Kosten und Produktionsverläufe. Die praktische Relevanz beider Modelle wird durch Experimente anhand von Daten des deutschen Kraftwerkparks nachgewiesen. Wir beginnen im ersten Schritt mit der Analyse der Epigraphen der Startkostenfunktionen und erhalten eine lineare, irredundante H-Darstellung des Epigraphen der Startkosten in einem einzelnen Zeitschritt mit linearem Separationsalgorithmus (in Zusammenarbeit mit René Brandenberg und Matthias Huber), eine exponentielle H-Darstellung des Epigraphen der Startkosten summiert über alle Zeitschritte, welche im Allgemeinen irredundant ist und einen linearem Separationsalgorithmus besitzt (in Zusammenarbeit mit René Brandenberg und Matthias Huber), und eine exponentielle Familie von Facetten des Epigraphen der Startkosten kombiniert über alle Zeitschritte. Durch die explizite Modellierung der Temperatur eines Kraftwerks erhalten wir eine erweiterte Formulierung des Epigraphen der summierten Startkostenfunktion mit O(T) Variablen und O(T2) Nebenbedingungen (in Zusammenarbeit mit René Brandenberg und Matthias Huber). Lediglich O(T) dieser Nebenbedingungen sind notwendig, um die Startkosten im ganzzahligen Fall zu modellieren, die restlichen O(T2) Nebenbedingungen stärken die lineare Relaxation und können in O(T) separiert werden. Diese Temperaturformulierung kann um die Modellierung des gesamten Startprozesses erweitert werden. Die zur Zeit führenden Modelle ordnen jedem Start einen von S Typen zu. Indem wir diese Starttypen als Flüsse in einem speziellen Netzwerk betrachen, stärken und verallgemeinern wir diese Modelle, sodass das resultierende Polyeder mit O(ST) Variablen und O(T2) Nebenbedingungen eine erweiterte Formulierung des Epigraphen der über alle Zeitschritte kombinierten Startkosten darstellt. Im ganzzahligen Fall werden die Startkosten bereits durch O(ST) dieser Nebenbedingungen korrekt modelliert, die übrigen Nebenbedingungen stärken die lineare Relaxation und können in O(T2) separiert werden. Die auf Starttypen basierenden Modelle aus der Literatur bleiben auch mit unserer Verbesserung anwendbar. Abschließend führen wir mit unseren und den aus der Literatur bekannten Modellen Experimente auf Basis des deutschen Kraftwerksparks durch. Anhand der Szenarien für das Jahr 2011 und 2025 belegen wir unsere theoretischen Resultate: Die in dieser Arbeit vorgestellten erweiterten Formulierungen übertreffen die bestehenden Formulierung sowohl bezüglich der Rechenzeit als auch bezüglich der Ganzzahligkeitslücke.
WWW:
https://mediatum.ub.tum.de/?id=1311607
Date of submission:
11.07.2016
Oral examination:
07.12.2016
File size:
1546050 bytes
Pages:
191
Urn (citeable URL):
https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20161207-1311607-1-5
Last change:
10.02.2017
 BibTeX