Combinatorial algorithms and complexity of rounding problems arising in Mixed-Integer Optimal Control
The combinatorial decomposition approach, consisting of first solving a (nonlinear) relaxed problem and then computing appropriate roundings recuperating the discrete controls, has become an established method for solving mixed-integer optimal control problems. This thesis analyzes the rounding step in detail, provides a time complexity investigation, and develops three new fast non-heuristical approaches for the rounding step, enhancing the modeling capabilities of the decomposition approach. In particular, the proposed algorithms can be used to solve rounding problems in the presence of combinatorial constraints or switching costs up to optimality with respect to a wide range of objective functions, e.g., the integral control deviation or the switching costs. The first approach is concerned with rounding problems on equidistant grids and vanishing constraints. We establish a connection between assigning discrete controls to grid points in the discretization and computing a matching on a simple bipartite graph. Using the graph-based view, we provide the tight bound for the integral control deviation and develop a fast rounding algorithm for this setting, which solves the rounding problem optimally in polynomial time. For the second approach, we reformulate the rounding problem into a system of linear algebraic equations modulo 2. Application of this formulation allows several combinatorial constraints such as dwell times to be added to the rounding step. We generalize the dwell-time setting and provide additional combinatorial constraint formulations enhancing the modeling capabilities of the decomposition approach. Finally, we show that the rounding problem becomes NP-complete when switching costs are added that directly depend on the rounding decision made for the previous grid point. For this setting, we develop a rounding framework based on computing a shortest path in a directed acyclic graph. This framework is capable of quickly computing the discrete control with minimal switching costs within a maximally allowed integral deviation. The framework also provides the additional flexibility to solve all of the previously discussed Numerical experiments on several benchmark problems illustrate and support the theoretical findings.
combinatorially constrained rounding problems and can be applied to optimal control problems in the multidimensional setting.
Die combinatorial integral approximation Zerlegung hat sich in den letzten Jahren als ein Verfahren zur Lösung beziehungsweise Approximation von gemischt-ganzzahligen Optimalsteuerungsproblemen etabliert. Bei diesem Verfahren wird zunächst ein relaxiertes (nichtlineares) Problem gelöst. Durch Anwendung eines geeigneten Rundungsalgorithmus wird aus der relaxierten Lösung eine ganzzahlige Steuerung für das ursprüngliche gemischt-ganzzahlige Problem generiert. Diese Arbeit erweitert sowohl die theoretischen als auch die praktischen Anwendungsmöglichkeiten des Verfahrens, indem sie den Rundungsschritt im Detail analysiert und drei schnelle neue nicht-heuristische Algorithmen entwickelt. Insbesondere ermöglichen diese Algorithmen, Rundungsprobleme mit kombinatorischen Nebenbedingungen oder Schaltkosten optimal im Bezug auf die gewählte Kostenfunktion, wie beispielsweise der maximal zulässigen Abweichung zur relaxierten Lösung (integral control deviation) oder den Schaltkosten, zu lösen. Der erste Ansatz erlaubt es, Rundungsprobleme auf äquidistanten Gittern und mit vanishing constraints in Polynomialzeit zu lösen. Wir ermöglichen dies, indem wir das Rundungsproblem als ein Zuweisungsproblem (assignment problem) auffassen. Die mathematische Sichtweise entspricht in diesem Fall dem matching problem auf einem einfachen bipartiten Graphen, welcher durch Kontrollaktivierungen und Gitterpunkte modelliert ist. Dieser graphenbasierte Ansatz gewährt zudem die Möglichkeit, die bestmögliche Schranke der integral control deviation für vanishing constraint behaftete Rundungsprobleme herzuleiten. In einem zweiten Ansatz reformulieren wir das Rundungsproblem in ein linear-algebraisches Gleichungssystem modulo 2. Diese Betrachtungsweise gestattet es, verschiedene kombinatorische Nebenbedingungen wie unter anderem Verweilzeiten (dwell-times) in den Rundungsschritt mitaufzunehmen. Zudem verallgemeinern wir die Formulierung der Verweilzeitnebenbedingungen und legen dar, wie zusätzliche kombinatorische Nebenbedingungen in den Rundungsschritt aufgenommen werden können. Dies erweitert die Modellierungsmöglichkeiten des gesamten Zerlegungsanssatzes. Ein dritter Ansatz wird für Rundungsprobleme mit Schaltkosten benötigt. Wir zeigen, dass dieses Problem bereits für Schaltkosten, deren Höhe unmittelbar von der Rundungsentscheidung auf dem vorherigen Gitterpunkt abhängt, NP-vollständig ist. Um diese insbesondere für die Praxis wichtige Problemklasse von Rundungsproblemen dennoch handhaben zu können, wird ein Ansatz basierend auf einer kürzesten Wege Formulierung in azyklischen gerichteten Graphen entwickelt. Dieser Ansatz ermöglicht es, zuverlässig und schnell diskrete Steuerungen mit minimalen Schaltkosten innerhalb einer vorgegebenen integral control deviation zu berechnen. Des Weiteren ist der kürzeste Wege Ansatz im Vergleich zu den anderen in dieser Arbeit entwickelten Algorithmen der flexibelste hinsichtlich zusätzlicher kombinatorischer Nebenbedingungen, da er nicht nur jegliche der zuvor diskutieren Rundungsprobleme lösen kann, sondern auch bei mehrdimensionalen Optimalsteuerungsproblemen einsetzbar ist. Abschließend werden die theoretischen Ergebnisse durch numerische Berechnungen bestätigt und veranschaulicht.
Preview
Cite
Access Statistic
Rights
Use and reproduction:
All rights reserved