Combinatorial integral decompositions for mixed-integer optimal control

Abstract

Many optimization problems in science, engineering, and medicine can be modeled by differential equations that can be steered via discrete control functions and are therefore called mixed-integer optimal control problems. The challenge of solving these problems lies in combining an infinite-dimensional optimization problem with discrete-valued optimization functions. After discretization, these problems become mixed-integer nonlinear programs for which the combinatorial integral approximation decomposition was proposed. The decomposition solves one nonlinear problem and one rounding problem formulated as a mixed-integer linear program. This thesis generalizes and extends the combinatorial integral approximation decomposition algorithm. We define a framework that, through a sequence of several nonlinear optimization and rounding problemswith increasing numbers of fixed integer variables, is designed to transfer feasibility from the obtained relaxed solution to the rounded solution. We derive several rounding problem versions based on different norms, the structure of the dynamical system, and the temporal ordering of the control approximation constraints. Based on the constructed integer control functions, we propose recombination strategies for generating promising candidate solutions with respect to the objective. For the combinatorial integral approximation decomposition in the unconstrained case, convergence to the optimal solution can be achieved by grid refinement. However, when refinement is not applicable or desirable, recombination methods are useful. We provide an overview of a range of time-coupled combinatorial constraints that are commonin practical applications. Specifically,we investigate decomposition algorithms for mixedinteger optimal control problems under minimumdwell time and bounded discrete total variation constraints. Typically, state constraints also arise in application-driven problems. We therefore propose methods for incorporating information from the nonlinear problem step into the rounding problemconstraints to generate state constraint feasible integer control solutions. Independent of the additional constraints, we derive different, partly approximate algorithms to solve the mixed-integer linear rounding problem and perform a theoretical analysis by proving tight bounds in terms of the integral deviation gap. Efficient software is indispensable for problemsolving in practice. In this context, we present the package pycombina, which provides solution algorithms for the mixed-integer linear problem. Computational results from benchmark problems and real-world case studies of a hybrid electric vehicle and a heart assist device systemhighlight the relevance and applicability of the proposed algorithms.

Viele Optimierungsprobleme aus den Natur- und Ingenieurwissenschaften sowie der Medizin können mit Differentialgleichungen modelliert werden, die über diskrete Steuerungsfunktionen geregelt werden können und daher als gemischt-ganzzahlige Optimalsteuerungsprobleme bezeichnet werden. Die Herausforderung bei der Lösung dieser Probleme liegt in der Kombination eines unendlich-dimensionalen Optimierungsproblems auf der einen Seite und diskretwertigen Optimierungsfunktionen auf der anderen Seite. Diese Probleme werden nach der Diskretisierung zu gemischt-ganzzahligen nichtlinearen Problemen. Für deren Lösung wurde wiederumdie combinatorial integral approximation Dekomposition vorgeschlagen, welche aus dem Lösen eines nichtlinearen Optimierungsproblems und eines Rundungsproblems, das als ein gemischt-ganzzahliges lineares Problem formuliert werden kann, besteht. Diese Arbeit verallgemeinert und erweitert den Dekompositions-Algorithmus in vielerlei Hinsicht. Wir definieren einen algorithmischen Rahmen, der durch eine Folge von mehreren nichtlinearen Optimierungs- und Rundungsproblemen mit zunehmender Anzahl von fixierten ganzzahligen Variablen die Zulässigkeit der konstruierten relaxierten zur gerundeten Lösung übertragen soll. Wir leiten mehrere Rundungsproblemversionen ab, die auf verschiedenen Normen, der Struktur des dynamischen Systems und der zeitlichen Anordnung der Nebenbedingungen der Steuerungs-Approximiation beruhen. Auf der Grundlage der konstruierten ganzzahligen Steuerungsfunktionen schlagen wir Rekombinationsstrategien vor, um vielversprechende Kandidatenlösungen im Hinblick auf die Zielfunktion zu generieren. Während im unbeschränkten Fall für den Dekompositionsalgorithmus eine Konvergenz zur optimalen Lösung durchGitterverfeinerung bewiesenwerden kann, sind Rekombinationsstrategien nützlich, wenn eine Verfeinerung nicht anwendbar oder erwünscht ist. Wir geben einen Überblick über eine Reihe von zeitgekoppelten kombinatorischen Nebenbedingungen, die in vielen praktischen Anwendungen üblich sind. Insbesondere untersuchen wir Dekompositionsalgorithmen für gemischt-ganzzahlige optimale Steuerungsprobleme unter minimaler Verweilzeit und einer beschränkten Anzahl erlaubterWechsel der aktiven diskreten Steuerungsfunktion. Typischerweise treten auch Beschränkungen der differentiellen Zustände bei anwendungsgetriebenen Problemen auf. Für die Konstruktion zulässiger ganzzahliger Steuerungslösungen schlagen wirMethoden vor, umInformationen aus dem nichtlinearen Problemschritt in das Rundungsproblem einzubeziehen. Unabhängig von den zusätzlichen Nebenbedingungen leiten wir verschiedene, teilweise approximative Algorithmen zur Lösung des gemischt-ganzzahligen linearen Rundungsproblems her und führen eine theoretische Analyse durch, indem wir scharfe Schranken in Bezug auf den Rundungsfehler beweisen. Effiziente Software ist für die Problemlösung in der Praxis unumgänglich. In diesem Kontext stellen wir das Paket pycombina vor, das Lösungsalgorithmen für das gemischt-ganzzahlige lineare Problem bereitstellt und im Rahmen eines Gemeinschaftsprojekts mit anderen Forschern entwickelt wurde. Numerische Ergebnisse aus Benchmark-Problemen und realen Fallstudien aus einem Hybrid-Elektrofahrzeug und einem Herzunterstützungssystem heben die Relevanz und Anwendbarkeit der diskutierten Algorithmen hervor.