Operations Research

Marco Lübbecke hat als Mathematiker den Lehrstuhl für Operations
Research an der RWTH Aachen inne. Sein Lehrstuhl ist sowohl der
Fakultät für Wirtschaftswissenschaften als auch der Fachgruppe
für Mathematik zugeordnet. Zum Gespräch mit Sebastian Ritterbusch
in Karlsruhe kam es anlässlich des Treffens der DFG
Forschergruppe 2083: Integrierte Planung im öffentlichen Verkehr
auf Einladung von Peter Vortisch, der auch schon zur
Verkehrsmodellierung in Folge 93 in diesem Podcast zu hören war.
Auf Twitter sind Marco Lübbecke unter @mluebbecke und sein
Lehrstuhl unter @RWTH_OR zu finden und er schreibt das Blog Café
Opt.


Operations Research befasst sich zusammenfassend mit
mathematischen Modellen und Methoden zur
Entscheidungsunterstützung. Dabei steht oft die Frage einer
möglichst guten oder optimierten Entscheidung im Vordergrund und
daher ist das Gebiet von mathematischer Seite im Bereich der
mathematischen Optimierung angesiedelt. Die Optimierung behandelt
grundsätzlich die Bestimmung eines optimalen Werts einer
Zielfunktion (und einer dazugehörenden Lösung) unter
Berücksichtigung von einschränkenden Nebenbedingungen, den
Restriktionen. Daneben steht aber auch die Frage der geeigneten
Abbildung und Modellierung der Wirklichkeit und den Fehlerquellen
der Beschreibung wie auch die grundsätzliche Herangehensweise an
das Problem.


Das optimierte Zusammenspiel von Menschen, Algorithmen und
Technologie wird seit 2011 auch oft mit dem Begriff Industrie 4.0
für eine erhoffte vierte industrielle Revolution beschrieben. Die
einheitliche Definition des Begriffs lassen aber selbst
renommierte Industrievertreter offen. Als eine Schnittmenge der
Beschreibungen kann man die lokale Intelligenz von
Fertigungskomponenten ausmachen, die über Vernetzung und Sensorik
zu einem besseren Gesamtprozess führen kann. Im Kleinen werden so
Entscheidungsprozesse durchgeführt und dies führt grundlegend auf
die gerade eingeführte mathematische Optimierungstheorie mit
allen ihren Facetten. So gesehen ist die Industrie 4.0 als
Optimierungsproblem eigentlich ohne Mathematik undenkbar.


Ein in der Universität sehr naheliegendes Feld der Optimierung
ist die Vorlesungsplanung, und hier ist aus der Forschung
zusammen mit Gerald Lach in Kooperation zwischen der TU Berlin
und der RWTH Aachen die Lösung Mathplan entstanden, die
inzwischen an vielen Universitäten erfolgreich zur Vorlesungs-,
Tutorien- und Klausurplanung eingesetzt wird. Mit genügend Zeit
und genügend Personal kann man zwar einen einigermaßen
akzeptablen Plan mit viel Erfahrung auch ohne besondere
mathematische Optimierung aufstellen, das ändert sich aber
schlagartig, wenn kurzfristige Änderungen berücksichtigt und
Konflikte aufgelöst werden müssen. Mathematisch geht es hier um
ganzzahlige lineare Programme, für die zwar Lösungsverfahren
bekannt waren, diese für die Größenordnung der Probleme nicht
geeignet waren. Eine Modellreduktion ohne Verlust der Optimalität
führte hier zur Lösung.


Auch in der Erstellung von Zugfahrplänen besteht ein großes
Optimierungspotential. Da die Realität nicht perfekt planbar ist,
geht es hier besonders um eine robuste Planung, die auch bei
entstehenden Störungen noch das anvisierte Ziel erreichen kann.
In der Forschung unter anderem auch mit Anita Schöbel der Uni
Göttingen geht es um die Analyse der Fortpflanzungen von
Verzögerungen, damit besonders kritische Fälle besonders
behandelt werden können. Ein weiterer Gesichtspunkt ist aber auch
die Möglichkeit Probleme möglichst gut durch kleine Eingriffe
wieder korrigieren zu können.


Ein zunächst überraschendes Forschungsthema ist die
Bundestagswahl, wo sich Sebastian Goderbauer mit der optimierten
Wahlkreiseinteilung befasst. Die 299 Bundestagswahlkreise werden
weitaus häufiger neu zugeschnitten als man denkt: Da nach
Bundestagswahlgesetz jeder Wahlkreis gerade 1/299-tel der
Wahlberechtigten mit einer Toleranz von maximal 25 Prozent
vertreten muss, erfordert die Wählerwanderung und Veränderung der
Bevölkerungsstruktur die regelmäßigen Veränderungen. Das
sogenannte Gerrymandering ist besonders bei Wahlen mit
Mehrheitswahlrecht ein sehr problematisches Vorgehen bei
Wahlkreisveränderungen, das offensichtlich undemokratische
Auswirkungen hat. In Deutschland ist dies weniger ein Problem,
wohl aber die deutlich ungleiche Größenverteilung der Wahlkreise.
Die mathematische Definition und Betrachtung als
Optimierungsproblem trägt die Hoffnung in sich, dass das
Zuschnitt-Verfahren transparenter und nachvollziehbarer als
bisher abläuft, und das sich dadurch balanciertere
Wahlkreisgrößen ergeben können.


Ein zentrales Forschungsgebiet ist für Marco Lübbecke der Bereich
der ganzzahligen Programme. Die vielen auftretenden Variablen
können beispielsweise Entscheidungen repräsentieren, die diskrete
Werte wie ja oder nein repräsentieren. Dazu kommen verschiedene
Resktriktionen und Nebenbedingungen, die Einschränkungen aus der
Umgebungssituationen wie beispielsweise begrenzte Resourcen
darstellen. Der Begriff "Programm" für die Bezeichnung von
Optimierungsproblemen ist historisch aus dem englischen Begriff
"programming" entstanden, der früher intensiv für "Planung"
verwendet wurde. Heutzutage ist dieser Zusammenhang nicht mehr so
naheliegend und entsprechend hat sich die Mathematical
Programming Society (MPS) in Mathematical Optimization Society
(MOS) umbenannt.


Sind die Variablen eines Optimierungsproblems im , so kann man
sich Schnitte mit linearen Ungleichungen wie das halbseitige
Abschneiden des Lösungsraumes mit Ebenen vorstellen. Man nennt
das Resultat ein Polyeder oder Vielflächner. Ist nun zusätzlich
auch die Zielfunktion linear, so spricht man von einem linearen
Optimierungsproblem oder linearen Programm.


Wird nun der Lösungsbereich mit einem Gitter geschnitten, d.h.
die Variablen können nur diskrete wie z.B. nur ganzzahlige Werte
annehmen, so wird das Optimierungsproblem deutlich schwieriger.
Dies ist erstaunlich, da der Lösungsbereich deutlich
eingeschränkt wird. Jedoch verliert der Lösungsbereich seine
konvexe Struktur und führt im linearen Fall von einem in
polynomialer Zeit lösbaren Problem zu einem NP-schweren Problem.


Wenn die Lösungsmenge eine beschränkte Anzahl von Elementen
besitzt, so ist die Existenz von Maximum und Minimum durch
Ausprobieren leicht zu beweisen. Das Problem ist jedoch, dass bei
großen Datenmengen das vollständige Durchsuchen viel zu lange
dauern würde. Eine Strategie zur Reduktion des Problems ist hier
die Aggregation oder das Clustering, wo verschiedene Aspekte
durch einzelne Repräsentanten dargestellt und gruppiert werden
und so Rechenzeit eingespart wird. Zwar werden so nur
approximierte Probleme gelöst, jedoch deutlich schneller und wenn
möglich mit Fehlerschranken, die den maximalen Abstand zur
tatsächlichen Lösung spezifizieren.


Ein Beispiel für dieses Prinzip sind die Contraction Hierarchies,
die das Routingproblem bzw. einen kürzesten Pfad auf einem
Graphen zu finden durch eine zuvor berechnete Reduktion des
betrachteten Netzes beschleunigen, exakte Fehlerschranken
liefern, und gleichzeitig die Berechnung einer optimalen Lösung
durch Berechnung lokaler Routen ermöglicht. Das Verfahren kommt
aber an Grenzen, wenn einige Aspekte nur mit Wahrscheinlichkeiten
beschrieben werden können.


Ein klassisches Optimierungsproblem ist das Problem des
Handlungsreisenden, an dem sich die verschiedenen Verfahren und
Analysen der diskreten Optimierung illustrieren lassen. Dabei hat
das Problem die Forschungsrelevanz nicht verloren: Viele neue
Verfahren und Forschungsansätze gehen auf das Problem des
Handlungsreisenden zurück. Gleichzeitig steht das Problem
stellvertretend für viele Optimierungsprobleme zu Reihenfolgen in
der Anwendung und findet so immer neuen Einsatz.


Grundsätzlich basieren Optimierungsprobleme auf der Suche nach
Extremwerten, diese kann man beispielsweise mit Abstiegs- oder
Aufstiegsverfahren versuchen zu finden. Will man nun
Einschränkungen berücksichtigen, so kann man die Zielfunktion mit
Lagrange-Multiplikatoren für die Restriktionen erweitern. Diese
Multiplikatoren kann man als Strafterme verstehen, die das Finden
des Optimums unter Einhaltung der Restriktionen erzwingen. Die
Verwendung der Lagrange-Multiplikatoren erzeugt automatisch über
die Lagrange-Dualität ein duales Problem und führt auch auf
Sattelpunkte. Die neue Sichtweise ist aus mehreren Gründen sehr
hilfreich: Zum einen vereinfacht diese Dualität mathematische
Beweise, sie ermöglicht Abschätzungen für die Qualität von
Lösungen und liefert gleich zwei alternative Verfahren, um ein
Optimierungsproblem zu lösen.


Ein Standardverfahren zum Lösen von linearen
Optimierungsproblemen ist das Simplex-Verfahren. Hier wird
ausgenutzt, dass lineare Restriktionen ein Polyeder bilden und
eine lineare Optimierungsfunktion ihr Maximum auf einer
(Hyper-)Fläche, einer Kante (bzw. entsprechenden
höherdimensionalen Strukturen) oder einer Ecke annehmen muss.
Diese Kanten und Ecken werden mit dem Verfahren systematisch
durchsucht. Beim schriftlichen Rechnen hat das Simplex-Verfahren
große Ähnlichkeit mit dem Gaußschen Eliminationsverfahren, das
zum Lösen von linearen Gleichungssystemen eingesetzt wird. In der
Praxis ist das Simplex-Verfahren sehr schnell, jedoch finden sich
konstruierte Gegenbeispiele, auf denen das Simplex-Verfahren eine
schrecklich langsame exponentielle Laufzeit an den Tag legt.
Daher haben hier traditionelle innere Punkte-Verfahren und
Barrier-Verfahren ein aufwandstheoretisch deutlich besseres
Laufzeitverhalten, in der Praxis sind die Ergebnisse aber sehr
gemischt.


Hat man nun ein diskretes bzw. ganzzahliges Problem, so liefert
das Simplex-Verfahren ohne Berücksichtigung der Diskretisierung
typischerweise keine ganzzahlige Lösung, liefert aber
Abschätzungen für das Optimum, da der Wert einer optimalen
ganzzahligen Lösung nicht besser sein kann als der einer
optimalen kontinuierlichen Lösung. Für die nicht-ganzzahligen
Lösungen für einzelne Variablen wie kann man nun zwei ganzzahlige
Restriktionen definieren wie oder , und jetzt zwei Teilprobleme
bzw. "Branches" mit je einer der beiden Restriktionen zusätzlich
lösen. So erhält man entweder ein unzulässiges Teilproblem, oder
bereits ein ganzzahlige Lösung (nicht notwendigerweise eine
beste) oder eben wieder eine nicht-ganzzahlige. Durch
fortwährendes Verzeigen auf den nicht-ganzzahligen Variablen
entsteht eine Baumstruktur der Teilprobleme. Mit Hilfe der aus
den jeweiligen kontinuierlichen Relaxationen gewonnenen Schranken
lassen sich ganze Äste des Baums abschneiden ("Bound"), in denen
keine bessere Lösung mehr zu finden ist als die beste die man
bisher gefunden hat. Dieses Verfahren führen wir für alle
weiteren verbleibenden Probleme oder Branches durch bis eine
optimale lineare und diskrete Lösung übrig bleibt. Damit liefert
das Branch-and-Bound-Verfahren bzw. weiter verfeinert das
Branch-and-Cut-Verfahren auf Basis der Lösung von vielen
kontinuierlichen linearen Optimierungsproblemen die Lösung des
diskreten Problems. Eine Erweiterung des Verfahrens auf besonders
große Probleme ist das Branch-and-Price-Verfahren, das mit Basis
von Column Generation die Variablen sucht, die für die Lösung des
Gesamtproblems relevant sind, und das Problem eingeschränkt auf
diese Variablen löst, ohne dabei Optimalität aufzugeben.


Ein interessantes Beispiel ist hier das Bin Packing bzw.
Behälterproblem, wo es darum geht, eine Anzahl von verschiedenen
Objekten auf eine Anzahl von Behältern zu verteilen. Das
Entscheidungsproblem, ob eine gegebene Anzahl von Behältern
reicht, ist sowohl für Versandhäuser äußerst relevant, ist aber
gleichzeitig auch NP-Vollständig, also aufwandstheoretisch
nachgewiesen schwer. Hier kann man durch vorheriges Sammeln von
möglichen Füllmustern ein riesengroßes Modell erstellen, dieses
aber mit der column generation in der Praxis um so effizienter
lösen.


In der Industrie werden beispielsweise die Pakete Cplex, Gurobi
oder Xpress zur Lösung von Optimierungsproblemen eingesetzt, die
die besprochenen Verfahren umsetzen. Hier können auch
Modellierungssprachen zum Einsatz kommen, die die Probleme
abstrakt und menschenlesbar definieren. Vorteile sind hier die
Trennung von Daten und Modell und auch die Trennung von Problem
und Löser. Ein Beispiel für eine Modellierungssprache für
Optimierungsproblemen ist GAMS, sie stehen aber heutzutage in
starker Konkurrenz zu modernen Programmiersprachen wie Python.


Im Sinne des Leitsatzes "Tue Gutes und rede darüber" ist die
Kommunikation von Wissenschaft für Forschende in Öffentlichkeit,
Social Media und Internet eine große Gelegenheit mit vielen
Vorteilen: Neben dem Austausch von wichtigen Erfahrungen zum
Beispiel zum Schreiben wissenschaftlicher Paper, hilft es der
wissenschaftlichen Vernetzung, der gesellschaftlichen Diskussion
zur Relevanz des Forschungsgebiet über den Tellerand hinaus, und
interessiert auch die Öffentlichkeit und auch junge Menschen
näher in die spannenden Themen einzusteigen.
Literatur und weiterführende Informationen

G. Lach, M. Lübbecke: Optimal university course timetables
and the partial transversal polytope, International Workshop on
Experimental and Efficient Algorithms. Springer Berlin
Heidelberg, 2008.

C. Liebchen, M. Lübbecke, R. Möhring, S. Stiller: The concept
of recoverable robustness, linear programming recovery, and
railway applications, in Robust and online large-scale
optimization (pp. 1-27). Springer Berlin Heidelberg, 2009.

S. Goderbauer: Mathematische Optimierung der
Wahlkreiseinteilung für die Deutsche Bundestagswahl, Springer
Spektrum, Springer BestMasters, 2016.

S. Goderbauer, B. Bahl, P. Voll, M. Lübbecke, A. Bardow, A.
Koster: An adaptive discretization MINLP algorithm for optimal
synthesis of decentralized energy supply systems, Computers &
Chemical Engineering, 95, 38-48, 2016.

R. Geisberger: Contraction Hierarchies: Faster and Simpler
Hierarchical Routing in Road Networks, Diplomarbeit am Institut
für Theoretische Informatik Universität Karlsruhe, 2008.

M. Lübbecke, J. Desrosiers: Selected topics in column
generation, Operations Research, 53(6), 1007-1023, 2005.

M. Lübbecke: How to write a paper, blog post, 2014.

M. Lübbecke: Are we too complicated? Communication of the
Travelling Salesperson Problem in public, blog post, 2015.

Podcasts

S. Müller: Schulwegoptimierung, Gespräch mit G. Thäter im
Modellansatz Podcast, Folge 101, Fakultät für Mathematik,
Karlsruher Institut für Technologie (KIT), 2016.
http://modellansatz.de/schulwegoptimierung

P. Vortisch: Verkehrsmodellierung I, Gespräch mit G. Thäter
im Modellansatz Podcast, Folge 93, Fakultät für Mathematik,
Karlsruher Institut für Technologie (KIT), 2016.
http://modellansatz.de/verkehrsmodellierung-i

K. Nökel: ÖPNV, Gespräch mit G. Thäter im Modellansatz
Podcast, Folge 91, Fakultät für Mathematik, Karlsruher Institut
für Technologie (KIT), 2016. http://modellansatz.de/oepnv

U. Leyn: Verkehrswesen, Gespräch mit G. Thäter im
Modellansatz Podcast, Folge 88, Fakultät für Mathematik,
Karlsruher Institut für Technologie (KIT), 2016.
http://modellansatz.de/verkehrswesen

J. Eilinghoff: Analysis, Gespräch mit S. Ritterbusch im
Modellansatz Podcast, Folge 36, Fakultät für Mathematik,
Karlsruher Institut für Technologie (KIT), 2014.
http://modellansatz.de/analysis

J. Dickmann: Pumpspeicherkraftwerke, Gespräch mit S.
Ritterbusch im Modellansatz Podcast, Folge 5, Fakultät für
Mathematik, Karlsruher Institut für Technologie (KIT), 2014.
http://modellansatz.de/pumpspeicher

J. Wolf: Puerto Patida, das Rätselhörspiel zum Mitmachen,
http://OhneQ.de, 2015-2016.