eprintid: 16036 rev_number: 18 eprint_status: archive userid: 987 dir: disk0/00/01/60/36 datestamp: 2014-01-13 09:06:10 lastmod: 2014-02-20 11:30:50 status_changed: 2014-01-13 09:19:37 type: doctoralThesis metadata_visibility: show creators_name: Jung, Michael title: Relaxations and Approximations for Mixed-Integer Optimal Control title_de: Relaxierungen und Approximationen für gemischt-ganzzahlige Optimalsteuerung subjects: ddc-500 subjects: ddc-510 divisions: i-708000 adv_faculty: af-11 cterms_swd: Optimal control cterms_swd: Mixed-integer programming cterms_swd: Approximation methods and heuristics abstract: This thesis treats different aspects of the class of Mixed-Integer Optimal Control Problems (MIOCPs). These are optimization problems that combine the difficulties of underlying dynamic processes with combinatorial decisions. Typically, these combinatorial decisions are realized as switching decisions between the system’s different operations modes. During the last decades, direct methods emerged as the state-of-the-art solvers for MIOCPs. The formulation of a valid, tight and dependable integral relaxation, i.e., the formulation of a model for fractional values, plays an important role for these direct solution methods. We give detailed insight into several relaxation approaches for MIOCPs and compare them with regard to their respective structures. In particular, these are the typical solution’s structures and properties as convexity, problem size and numerical behavior. From these structural properties, we deduce some required specifications of a solver. Additionally, the modeling and subsequent limitation of the switching process directly tackle the class-specific typical issue of chattering solutions. One of the relaxation methods for MIOCPs is the outer convexification, where the binary variables only enter affinely. For the approximation of this relaxation’s solution, we took up on the control approximation problem in integral sense derived by Sager as part of a decomposition approach for MIOCPs with affine binary controls. This problem describes the optimal approximation of fractional controls with binary controls such that the corresponding dynamic process is changed as little as possible. For the multi-dimensional problem, we developed a new heuristic, which for the first time gives a bound that only depends on the control grid and not anymore on the number of the system’s controls. For the generalization of the control approximation problem with additional constraints, we derived a tailored branch-and-bound algorithm, which is based on the properties of the Lagrangian relaxation of the one-dimensional problem. This algorithm beats state-of-the-art commercial solvers for Mixed-Integer Linear Programs (MILPs) for this special approximation problem by several orders of magnitude. Overall, we present several, partially new modeling approaches for MIOCPs together with the accompanying structural properties. On this basis, we develop new theories for the approximation of certain relaxed solutions. We discuss the efficient implementation of the resulting structure exploiting algorithms. This leads to a deeper and better understanding of MIOCPs. We show the practicability of the theoretical observations with the help of four prototypical problems. The presented methods and algorithms allow on their basis the direct development of decision support and analysis tools in practice. abstract_translated_text: Diese Arbeit behandelt verschiedene Aspekte der Klasse gemischt-ganzzahliger nichtlinearer Optimalsteuerungsprobleme (MIOCPs). Dies sind Optimierungsprobleme, die die Problematik zugrundeliegender dynamischer Prozesse mit kombinatorischen Entscheidungen verbinden. Typischerweise sind diese Entscheidungen Schaltentscheidungen zwischen den verschiedenen Operationsmodi des dynamischen Systems. In den letzten Jahrzehnten haben sich direkte Methoden als die Löser von MIOCPs durchgesetzt. Die Formulierung einer gültigen, engen und verlässlichen Relaxierung der Ganzzahligkeit, also die Formulierung eines Modells für gebrochene Werte, spielt eine wichtige Rolle bei diesen direkten Lösungsmethoden. Wir geben ausführlichen Einblick in verschiedene Vorgehen zur Relaxierung von MIOCPs und vergleichen sie im Hinblick auf ihre zugehörigen Strukturen. Insbesondere sind diese die Lösungsstrukturen und Eigenschaften wie Konvexität, Problemgröße und numerisches Verhalten. Aus diesen strukturellen Eigenschaften folgen direkt einige nötige Spezifikationen eines Lösers. Zusätzlich wird das für diese Klasse typische Problem von häufigem Springen zwischen verschiedenen Systemmodi durch die Modellierung und anschließende Beschränkung des Umschaltprozesses direkt angegangen. Eine der Relaxierungen für MIOCPs ist die äußere Konvexifizierung bei der die Binärvariablen nur affin eingehen. Für diese Relaxierung greifen wir das von Sager als Teil eines Zerlegungsansatzes für MIOCPs mit affinen ganzzahligen Steuerungen entwickelte Steuerungsapproximationsproblem im integralen Sinne auf. Es beschreibt die optimale Approximation von fraktionellen Steuerungen durch ganzzahlige Steuerungen, so dass der zugehörige dynamische Prozess möglichst wenig verändert wird. Wir entwickeln eine neue Heuristik für das mehrdimensionale Problem, die zum ersten mal eine Schranke liefert, die nur von dem Steuerungsgitter und nicht mehr von der Anzahl der Steuerungen abhängt. Für eine Verallgemeinerung des Steuerungsapproximationsproblems durch zusätzliche Beschränkungen leiten wir einen maßgeschneiderten Branch-and-Bound-Algorithmus her, dem die Eigenschaften der Lagrange-Relaxierung des eindimensionalen Problems zugrunde liegen. Dieser Algorithmus schlägt moderne, kommerzielle Löser für gemischt-ganzzahlige lineare Programme (MILPs) für dieses spezielle Approximationsproblem um mehrere Größenordnungen. Insgesamt stellen wir diverse, teilweise neue Modellierungsansätze für MIOCPs mit den sich ergebenden strukturellen Eigenschaften vor. Darauf aufbauend entwickeln wir neue Theorien zur Approximation von bestimmten relaxierten Lösungen. Wir gehen auch auf die effiziente Implementierung der sich daraus ergebenden strukturausnutzenden Algorithmen ein. Dadurch wird ein tieferes und besseres Verständnis von MIOCPs entwickelt. Die Praktikabilität der theoretischen Beobachtungen zeigen wir anhand von vier prototypischen Anwendungen. Die vorgestellten Modellierungen und Algorithmen ermöglichen auf ihrer Basis die direkte Entwicklung von Decision Support und Analyse Tools für die Praxis. abstract_translated_lang: ger date: 2014 id_scheme: DOI id_number: 10.11588/heidok.00016036 ppn_swb: 779594800 own_urn: urn:nbn:de:bsz:16-heidok-160366 date_accepted: 2013-12-20 advisor: HASH(0x55fc34e9f038) language: eng bibsort: JUNGMICHAERELAXATION2014 full_text_status: public citation: Jung, Michael (2014) Relaxations and Approximations for Mixed-Integer Optimal Control. [Dissertation] document_url: https://archiv.ub.uni-heidelberg.de/volltextserver/16036/1/DissertationJung.pdf