Mathematische Optimierung

In den letzten 50 Jahren haben mathematische Optimierungsmodelle und –algorithmen ihre universelle Einsetzbarkeit in vielen Bereichen der Entscheidungs- und Planungsunterstützung bewiesen. Gerade in den letzten beiden Jahrzehnten hat die mathematische Forschung zur Entwicklung moderner Optimierungsalgorithmen beigetragen, mit denen sich heutzutage Problemgrößen behandeln lassen, die vor 10 Jahren noch undenkbar schienen. So lassen sich lineare Programme mit Milliarden von Variablen und Nebenbedingungen effizient lösen, bei ganzzahligen Programmen ist man immerhin bereits im Millionenbereich. Einen Überblick über die zurückliegenden Effizienzsteigerungen in der Löserentwicklung gibt die folgende Grafik am Beispiel zweier führender kommerzieller Löser für diese Sorte von Problemen.

Wie sich entnehmen lässt, hat allein die Entwicklung besserer mathematischer Verfahren einen Geschwindigkeitsschub von Faktor 4,7 Millionen gebracht. Im Vergleich dazu liegt der Speed-Up-Faktor durch bessere Hardware gerade bei 1600. Insgesamt lassen sich damit heute Optimierungsprobleme innerhalb von 1 Sekunde lösen, die vor 25 Jahren noch unlösbar schienen.

Die Partner im ADA Lovelace Center entwickeln bereits seit vielen Jahren effiziente mathematische Verfahren für Planungsprobleme aller Art. Dies umfasst z. B. die Felder Verkehr und Logistik, Energieerzeugung und Übertragung, Supply-Chain-Management, Gebäudeinfrastrukturen, Automobile, Finanzen sowie Anwendungen aus dem Ingenieurswesen. Gleichzeitig werden optimierungstheoretische Probleme untersucht, deren Ergebnisse zum Beispiel in die Beschleunigung allgemeiner Lösercodes eingehen.

Mit der Integration von Verfahren des maschinellen Lernens mit Optimierungsverfahren wurde in jüngster Zeit ein ganz neues Feld aufgetan, was den Weg von Offline-Optimierungsproblemen (mit bekannten, statischen Parametern) hin zu Online-Optimierungsproblemen in Echtzeitanwendungen (unter dynamischen, zeitlich veränderlichen Parametern) betrifft. Für die oftmals hochdynamischen Randbedingungen heutiger Anwendungen, z. B. der Planung von Logistikketten, wird die Verfügbarkeit solcher Verfahren von besonderer Wichtigkeit sein. So haben wir beispielweise gezeigt, dass es möglich ist, Prioritäten und Kostenfunktionen in Planungsproblemen aus beobachteten Entscheidungen der Vergangenheit abzuleiten. Die Fähigkeit, aus vergangenen Entscheidungen explizite Planungsregeln herzuleiten, sorgt daher für eine höhere Automatisierbarkeit und Objektivierbarkeit der zu treffenden Planungsentscheidungen. Die Weiterentwicklung solcher Ansätze im Rahmen lernender Verfahren nimmt im ADA Lovelace Center einen besonderen Stellenwert ein. Es wird durch unsere Arbeit erstmals möglich, aus den bislang nur in der Theorie gegebenen Gütegarantien dieser Verfahren praktisch nutzbare Algorithmen zu machen, welche für den Anwender einen entscheidenden Wettbewerbsvorteil ausmachen.
 

Datenanalyse und Optimierung waren bislang in der Entwicklung von Systemen der Entscheidungsunterstützung zwei getrennte, aufeinanderfolgende Arbeitsschritte. Dieser Ansatz stößt aber gleich aus mehreren Gründen zunehmend an seine Grenzen: Im Zeitalter zunehmend größer werdender Datenmengen ist allein die Auswahl der für ein Optimierungsproblem relevanten Parameter eine große Herausforderung. Auch ist unklar, welche Merkmale eines Systems für das Treffen guter Planungsentscheidung relevant sind, oder welche Effekte Einfluss auf die Performanz des gewählten Plans haben. Hier gewinnt die Integration der Ansätze aus Datenanalyse und Optimierung an Wichtigkeit. Sehr vielversprechend erscheint für die Zukunft der Weg, mit generischen Basismodellen zur Beschreibung einer Anwendung zu starten und sowohl die Bewertungsfunktion als auch die speziellen Randbedingungen aus den verfügbaren Daten zu lernen. Diese Form der automatischen Modellbildung wird den heutzutage ständig wechselnden Planungsbedingungen deutlich gerechter, denn hier hat man es oft mit einem konstanten Zustrom neuer Daten zu tun, die sofort in die nächste Regelungsaktion für das System einfließen müssen, um es im Optimalzustand zu halten.

Im ADA Lovelace Center werden insbesondere Techniken entwickelt, die in der Lage sind, sich auf die Dynamik eines gegebenen Systems einzustellen und für dieses optimale Entscheidungen zu treffen. Die so »gelernten« Entscheidungen werden dadurch im Laufe der Zeit, und mit mehr Trainingsdaten, immer besser die realen, zeitlich variablen Rahmenbedingungen reflektieren. Die Nutzbarmachung dieser Technik zur Herleitung von Optimierungsmodellen ebnet den Weg hin zu mitlernenden mathematischen Entscheidungsmodellen, welche einen großen Fortschritt im Bereich der automatischen Planung und Steuerung darstellen. Bisher für diese Fragestellung verfügbare Verfahren, wie die mehrstufige stochastische Optimierung, scheitern hier oftmals wegen ihres exorbitanten Rechenaufwandes. Online-Learning bietet eine intrinsisch leichtgewichtige Alternative, denn zu seiner Philosophie gehört es, jeden Datenpunkt nur einmal zu betrachten, was zu einer bedeutenden Entkopplung entlang der zeitlichen Achse und somit zu deutlich geringerer Rechenkomplexität führt. Auch wird so sichergestellt, dass nicht mehr aktuelles Wissen vergessen werden kann, denn weiter zurückliegende Beobachtungen erhalten ein deutlich kleineres Gewicht als kürzlich aufgenommene Daten.

Lernende Optimierungsverfahren sind auch ein wesentlicher Beitrag zum besseren Verständnis eines gegebenen Systems. In vielen Bereichen der praktischen Planung eines Unternehmens beruhen die getroffenen Entscheidungen auf impliziten, nicht formalisierten Regeln (mitunter »Bauchentscheidungen«). Diese sind nicht an sich schlecht, sind aber oft schwer nachvollziehbar und damit schwer automatisierbar. Auch geht diese Form des Expertenwissens oft verloren, wenn die zuständigen Mitarbeiter die Firma wechseln oder in den Ruhestand gehen. Lernende Optimierungsmodelle versetze eine Firma in die Lage, das bei ihr implizit vorhandene Planungswissen in eine mathematische Form zu gießen, die es erlaubt, dieses Wissen verstehbar und für die automatisierte Entscheidungsfindung nutzbar zu machen. Auf einem Feld, das in der Lage ist, die Wettbewerbsfähigkeit der deutschen Industrie ganz entscheidend zu steigern, gehört das ADA Lovelace Center zu den Pionieren dieses Forschungszweiges und liefert maßgebliche Impulse.

Eine weitere Herausforderung moderner Optimierungsverfahren liegt in der Reduktion der Modellkomplexität. Diese ist von immenser Wichtigkeit insbesondere angesichts der immer weiter wachsenden Datenmengen, die in die Entscheidungsfindung einbezogen werden müssen. Für das Dilemma, dass exakte Verfahren der ganzzahligen Optimierung in der Regel eine mit der Eingabegröße exponentiell wachsende Laufzeit aufweisen, versprechen moderne mathematische Methoden Abhilfe. Das Trennen relevanter von irrelevanten Parametern durch die Integration von Datenanalyseverfahren und Optimierungsalgorithmen erlaubt es auch bei sehr großen Datenmengen, Signal und Rauschen voneinander zu unterscheiden. Durch diese repräsentative Auswahl der Effekte in der Zielsetzung und den Nebenbedingungen des gewählten Optimierungsmodells kann so die Rechenzeit deutlich gesenkt werden. Ein Beispiel dafür ist die jüngste Entwicklung von Lernalgorithmen zur Auswahl repräsentativer Szenarien in der Optimierung unter Datenunsicherheiten. Letztere stellt eine Technik dar, um Entscheidungen zu treffen, die auch unter unsicheren (z. B. auf Messungen oder Prognosen basierenden) Eingabedaten qualitativ hochwertig und umsetzbar bleiben. Solche algorithmischen Methoden, die die Auswahl repräsentativer Szenarien unter einer großen Vielzahl denkbarer Szenarien ermöglichen, sind ein wichtiger Beitrag für die Anwendbarkeit dieser Verfahren in der Praxis. Auch hier setzt das ADA Lovelace Center mit seiner Forschung international sichtbare Akzente.

Das richtige Mischverhältnis finden mit Mathematischer Optimierung

Mathematische Optimierungsmethoden sind für die Beschreibung und effiziente Planung komplexer Systeme unverzichtbar. Diese treten u.a. dort auf, wo bereits die schiere Anzahl der darin interagierenden Komponenten für eine Explosion in der Kombinatorik der zulässigen Lösungen sorgt. Gerade im Rahmen logistischer Entscheidungsprozesse spielt die Optimierung komplexer Systeme eine wesentliche Rolle. Man denke hierbei zum Beispiel an die Produktion in der Lebensmittelindustrie. Dort sind die Rohstoffe in gewissen, festgelegten Verhältnissen zu mischen, um die fertigen Produkte herzustellen. Die Anforderungen an die Inhaltstoffe sowie die gesetzlichen Vorgaben sind mittlerweile so komplex geworden, dass allein die Aufstellung einer zulässigen Zuordnung der Rohstoffchargen zu den Mischaufträgen bereits ein sehr schweres Problem darstellt; gar nicht zu reden vom Finden möglichst kostensparender Pläne. In der Applikation »selbstoptimierende adaptive logistische Netzwerke« entwickeln wir mathematische Modelle und Algorithmen zur Lösung solcher Problemstellungen.

Fahrplanoptimierung zur Energieeinsparung im Schienenverkehr

Im deutschen Schienennetz sind jeden Tag etwa 30.000 Züge unterwegs, die bei der Erstellung von Fahrplänen berücksichtigt werden müssen. In den letzten Jahren hat zusätzlich zu den üblichen Anforderungen an die Fahrplangestaltung, wie Pünktlichkeit und Betriebssicherheit, der Aspekt des Energieverbrauchs immer stärker an Bedeutung gewonnen. Will man im Rahmen der Fahrplanoptimierung auch den Energieverbrauch der Züge optimieren, inkl. ihrer Bewegungsdynamik, so entsteht ein Optimierungsproblem mit physikalischen Nebenbedingungen in Verbindung mit Schaltvorgängen. Die Mischung aus kontinuierlichem und diskretem Problemanteil führt dazu, dass man zur Lösung auf Verfahren der jeweils anderen Disziplin zurückgreifen kann. So sind oftmals Differenzialgleichungen zu linearisieren bevor diskrete Optimierungstechniken wieder zum Einsatz kommen können. Dies kann beispielsweise auf Basis von sog. stückweisen Linearisierungen erfolgen. Diese Technik erlaubt es, nichtlineare Funktionen in einem Optimierungsmodell durch Setzen von Stützstellen linear anzunähern. Solche und weitere Techniken werden im ADA Lovelace Center in der Applikation »Fahrerassistenzsysteme im Schienenverkehr« entwickelt und eingesetzt. In einem gemeinsamen Projekt mit der Verkehrs-Aktiengesellschaft VAG werden diese Techniken verwendet, um die Energieeffizienz des Nürnberger U-Bahn-Verkehrs zu erhöhen.

Optimale Netzauslegung in Gleichstromnetzen

Leistungselektronische Bausteine bilden den Kern unzähliger Anwendungen und Anlagen in Industrie, Energietechnik, Haustechnik und Mobilität. Verbaute Leistungswandler messen kontinuierlich Kenngrößen wie Strom, Spannung, und deren Änderung über die Zeit und ermitteln darüber indirekt den Zustand des verbundenen Gesamtsystems (beispielsweise des Energienetzes, einer Fertigungsanlage, eines Speichers oder Elektromotors). In der Applikation »Intelligente Leistungselektronik« entwickeln wir mathematische Modelle, um mit Hilfe dieser Daten die Stabilität von Gleichstromnetzen zu optimieren. Das Ziel ist dabei die Auswahl geeigneter Bauteile und die Justierung der Softwaresteuerung, um das Netz auf eine gewisse Bandbreite an Lastszenarien hin optimal auszurichten. Da die Simulation des Lastflusses in Gleichstromnetzen zu aufwändig ist, um sie direkt in ein Optimierungsmodell zu integrieren, trainieren wir Klassifikationsmodelle wie z. B. Entscheidungsbäume um die komplexen Einflüsse von Bauteilen und Software auf die Netzstabilität zu repräsentieren. Diese Randbedingungen werden gemischt-ganzzahlig reformuliert und stellen so die gelernten Zusammenhänge in deutlich einfacherer Form approximativ im Optimierungsmodell dar. Speziell darauf angepasste Dekompositionsalgorithmen sorgen für eine schnellere Berechnung der Lösung. Dadurch erhalten wir effiziente Verfahren zur Berechnung optimaler Netzauslegungen.