Directly to content
  1. Publishing |
  2. Search |
  3. Browse |
  4. Recent items rss |
  5. Open Access |
  6. Jur. Issues |
  7. DeutschClear Cookie - decide language by browser settings

Relaxations and Approximations for Mixed-Integer Optimal Control

Jung, Michael

German Title: Relaxierungen und Approximationen für gemischt-ganzzahlige Optimalsteuerung

[img]
Preview
PDF, English - main document
Download (3MB) | Terms of use

Citation of documents: Please do not cite the URL that is displayed in your browser location input, instead use the persistent URL or the URN below, as we can guarantee their long-time accessibility.

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.

Translation of abstract (German)

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.

Item Type: Dissertation
Supervisor: Sager, Prof. Dr. Sebastian
Date of thesis defense: 20 December 2013
Date Deposited: 13 Jan 2014 09:06
Date: 2014
Faculties / Institutes: Service facilities > Interdisciplinary Center for Scientific Computing
Subjects: 500 Natural sciences and mathematics
510 Mathematics
Controlled Keywords: Optimal control, Mixed-integer programming, Approximation methods and heuristics
About | FAQ | Contact | Imprint |
OA-LogoDINI certificate 2013Logo der Open-Archives-Initiative