DE
von Tim Varelmann
Gemischt-ganzzahlige Optimierungsprobleme sind so genannte 'kombinatorische Optimierungsprobleme'. Bei kombinatorischen Optimierungsproblemen suchen wir nach einer optimalen Kombination von diskreten Entscheidungen. Wer schon mal ein Sandwich bei Subway gegessen hat, ist mit diskreten Entscheidungen vertraut: In einem Subway-Restaurant hat man die Wahl zwischen sechs Brotsorten, manchmal auch mehr. Man kann aber nicht 30 % eines Brotes und 70 % eines anderen Brotes für ein Sandwich wählen, also ist die Wahl des Brots eine diskrete Entscheidung. Bei kombinatorischen Optimierungsproblemen ist es normalerweise nicht möglich, alle Entscheidungen aufzuzählen und sie zu testen.
In dem Subway-Beispiel mit sechs Brotsorten, zwei Größen, dreizehn Fleischsorten, vier Käsesorten, sieben Gemüsesorten (die jeweils eine Ja/Nein-Entscheidung erfordern), neun Soßen, Salz und Pfeffer (wieder Ja/Nein) gibt es bereits über 1,4 Millionen verschiedene Subs. Viele Subway-Restaurants bieten sogar noch mehr Gemüse, Soßen usw. an, und wer freundlich fragt, bekommt vielleicht sogar zwei Soßen. Tatsache ist, dass kein Mensch sein Lieblingssub durch Ausprobieren aller dieser Varianten herausfinden könnte. In einem Subway-Restaurant sind die Entscheidungen aber unabhängig voneinander. Da du deine Vorlieben für Brot kennst, musst du nicht alle Brotsorten testen - schon gar nicht mit und ohne Oliven und so weiter.
In der mathematischen Optimierung werden Entscheidungen modelliert unter Berücksichtigung technischer, wirtschaftlicher und logistischer Aspekte, welche eng miteinander zusammenhängen. Daher kann man keine qualitativ hochwertigen Entscheidungen treffen, indem man einzelne Entscheidungen isoliert. Anstatt jede einzelne Option aufzuzählen und zu testen, verwenden wir Algorithmen, die viele suboptimale Entscheidungen schnell ausschließen, um in einem viel kleineren Suchraum zu optimieren. Im schlechtesten Fall gelingt es solchen Algorithmen allerdings nicht, suboptimale Entscheidungen auszuschließen, und sie benötigen immer noch unverhältnismäßig viel Laufzeit. In der Praxis läuft es aber in der Regel deutlich besser als im schlechtesten Fall. Bob Bixby, der erste Entwickler von CPLEX und einer der Gründer von Gurobi, hat es treffend formuliert: "Gemischt-ganzzahlige Optimierung ist eine Kiste voller Tricks". Normalerweise kann man nicht beweisen, dass solche Tricks den schlechtesten Fall verhindern. Wir werden sehen, dass viele dieser Tricks trotzdem praktisch nützlich sind, um optimale Lösungen schneller als im schlechtesten Fall zu finden.
In diesem Artikel möchte ich auf zugängliche Weise einige Tricks vorstellen, die in mathematischen Optimierungslösungen implementiert sind, indem ich Ähnlichkeiten mit einer Aufgabe aus dem täglichen Leben herausarbeite: Socken nach dem Waschen zuzuordnen. Dies kann eine ziemlich lästige Aufgabe sein. Wenn die Socken sauber sind, sollte man alle Socken in passende Sockenpaare sortieren. Um alle Socken in ein passendes Paar zu sortieren, maximierst du die Anzahl der passenden Paare. Das heißt, du hast ein Optimierungsproblem. Und wenn du nicht "Pippi Langstrumpf" oder "Dobby der Hauself" heißt, muss du eine gewisse Sorgfalt an den Tag legen.
Im schlechtesten Fall dauert das Sortieren der Socken sehr lange. Stell dir vor, du würdest eine Socke aus dem Haufen nehmen und sie mit allen anderen Socken im Haufen vergleichen, bis du im letzten Vergleich endlich die passende Partnersocke findest. Am hypothetischen schlechtesten aller Tage muss du die nächste Socke wieder mit allen anderen vergleichen, und du hast bei jedem Sockenpaar in deinem Haufen das gleiche Pech. Wenn du deine Socken in einer Ladung von 25 Paaren wäschst, muss du die erste Socke mit 49 anderen Socken vergleichen. Nachdem du das erste Paar aus dem Haufen genommen hast, muss du die nächste Socke mit 47 verbleibenden Socken vergleichen. Für das dritte Paar Socken wären 45 Vergleiche erforderlich und für das vorletzte Paar 3 Vergleiche. Dann bleibt nur noch das letzte Paar im Haufen, aber da du den ganzen Tag Pech hattest, würdest du auch diese Socken miteinander vergleichen, nur um sicherzugehen, dass die Waschmaschine keine Socken gefressen hat. Am Ende musstest du also
49 +47 +45 + ... + 3 + 1 = 625
Vergleiche anstellen.
Ich hoffe, dass du dieses Szenario beim Sortieren deiner Socken nie erlebt hast und erleben wirst. Die Chancen dafür sind ganz gut, denn die menschliche Wahrnehmung hat - wie ein gemischt-ganzzahliger Optimierungsalgorithmus - eine ganze Reihe von Tricks auf Lager, um passende Sockenpaare zu finden. Das geschickte Sortieren von Socken ist also ähnlich wie mathematische Optimierungsalgorithmen. Beide nutzen Tricks, um Strukturen der realen Welt auszunutzen, um schnell zum Ziel zu kommen. Wir werden nun vier solcher Tricks in beiden Anwendungsfällen untersuchen, angefangen bei der anfänglichen Problemreduzierung bis hin zur speziellen Behandlung großer Aufgaben.
Manchmal haben wir ein Paar wirklich bunter Socken, die im Sockenhaufen geradezu leuchten. Solche Socken sind leicht zu erkennen und bilden natürlich die ersten zusammengehörigen Sockenpaare. Die menschliche Wahrnehmung hebt helle Farben effektiv hervor, so dass wir selten den ganzen Haufen durchsuchen müssen, um das Gegenstück zu einer sehr bunten Socke zu finden.
Auch aus kombinatorischer Sicht ist es sinnvoll, dies zuerst zu tun. Wie wir gesehen haben, braucht man im schlechtesten Fall mehr Vergleiche, um das erste Paar zu finden, als für jedes spätere Paar. Da wir übereinstimmende Paare aus dem Haufen entfernen, werden später sortierte Socken mit einem kleineren Haufen verbleibender Socken verglichen. Dazu brauchen wir weniger Vergleiche. Das bedeutet, auffallend bunte Socken zuerst zu sortieren (ohne dabei vergleichen zu müssen), ist die effizienteste Nutzung ihrer auffallenden Farbe.
Mathematische Optimierungslöser beginnen eine Optimierung auch mit einigen einfachen, fast trivialen Prüfungen des gegebenen Modells. Da immer mehr Modelle automatisch durch Software generiert werden, passieren scheinbar dumme Fehler recht häufig. Es macht Sinn, solche Fehler frühzeitig zu erkennen. Ein guter Solver würde zum Beispiel redundante Nebenbedingungen in dieser Phase identifizieren. Die vielleicht einfachste redundante Nebenbedingung ist
0T * x ≤ 0.
Ein anderes Beispiel kann mit beschränkten, nicht negativen Variablen x ∈ [xlb, xub] und nicht negativen Koeffizienten aT konstruiert werden, z. B. aT * x ≤ b. Weil a und x nicht negativ sind, ist der Wert der linken Seite am größten für x=xub. Wenn also aT * xub ≤ b gilt, wird jede Lösung, die die Grenzen der Variablen x respektiert, die Nebenbedingung respektieren. In diesem Fall kann die Nebenbedingung weggelassen werden. Es kann auch nützlich sein, die unteren Schranken für die Variablen auszuprobieren. Wenn aT * xlb > b ist, kann aT * x ≤ b niemals erfüllt werden, und der Löser stuft das Modell als unlösbar ein.
Einige Löser können auch erkennen, dass eine Variable eine lineare Kombination anderer Variablen ist. Dann können sie die erste Variable automatisch durch einen geeigneten Ausdruck in Bezug auf die anderen Variablen ersetzen. So wie das Sortieren auffallend bunter Socken den übrigen Sockenhaufen reduziert, sorgen Löser von mathematischen Optimierungsproblemen dafür, dass das vorliegende Problem keine unnötigen Schwierigkeiten mitbringt.
Nachdem die buntesten Sockenpaare aus dem Haufen entfernt wurden, ist es eine gute Strategie, sich auf Socken zu konzentrieren, die mehrfach im Haufen vorkommen. Nehmen wir an, von den ursprünglich 25 Sockenpaaren konnten wir zwei bunte Sockenpaare entfernen, und von den verbleibenden 23 Sockenpaaren bestehen drei Paare aus den gleichen Socken. Nimmt man eine dieser Socken, gibt es nun fünf Socken im Haufen der verbleibenden 45 Socken, die zu dieser Socke passen würden. Im schlechtesten Fall sind nicht 45, sondern nur 41 Vergleiche nötig, bis du eine passende Socke gefunden hast, denn es gibt höchstens 40 Socken, die nicht zu deiner Socke passen.
In der Praxis ist es entscheidender, dass du - bei zufälliger Vergleichsreihenfolge - die erwartete Anzahl nötiger Vergleiche reduzierst. Ich habe beim Schreiben dieses Artikels genau nachgerechnet, und ein wenig überraschendes Ergebnis bekommen: Die erwartete Anzahl der Vergleiche, die erforderlich sind, um die erste übereinstimmende Socke zu finden, wird ungefähr gedrittelt, wenn sich drei gleiche Paare im Haufen befinden; und sie wird ungefähr halbiert, wenn sich zwei Paare der gleichen Socke im Haufen befinden. Das bedeutet auch, dass, wenn das erste der drei identischen Paare gefunden wird - und kein anderes Sockenpaar mehrfach vorkommt -, die Suche nach dem zweiten Paar unmittelbar danach sinnvoll ist. Es ist zu erwarten, dass dies immer noch doppelt so schnell ist, wie das Finden eines Paares einzelner Socken.
Mit der Cliquenidentifikation leitet in mathematischer Optimierungsalgorithmus zusätzliche Nebenbedingungen her, die nützliche Informationen für den Lösungsprozess enthalten. Hier ist ein Beispiel für eine Clique von Nebenbedingungen:
x1 + x2 ≤ 1
x1 + x3 ≤ 1
x2 + x3 ≤ 1
x1, x2, x3 ∈ {0, 1}.
Diese Gruppe von Ungleichungen ("die Clique") beschreibt, dass für höchstens eine der drei Variablen ein Wert von eins zulässig ist und sonst alle Variablen den Wert 0 haben. Die Cliquenidentifikation kann dies erkennen und die zusätzliche Nebenbedingung
x1 + x2 + x3 ≤ 1
erzeugen, um diese Eigenschaft explizit zu formulieren. Eine solche Bedingung ermöglicht es anderen Techniken in Optimierungsalgorithmen, die Beziehung zwischen x1, x2 und x3 aus nur einer Nebenbedingung zu extrahieren, anstatt aus vielen Nebenbedingungen. Dies hat einen ähnlichen Effekt wie das frühe Sortieren mehrfach vorkommender Socken: Wir machen uns das Leben zu Beginn so leicht wie möglich, weil das Problem dann noch besonders groß und herausfordernd ist.
Ein Hinweis für alle, die mit den Grundlagen gemischt-ganzzahligen Optimierung vertraut sind: Die relaxierte Lösung x1 = x2 = x3 = 1/2 ist in der kontinuierlichen Relaxierung der ursprünglichen drei Nebenbedingungen zulässig. Mit der zusätzlichen Cliquen-Ungleichung ist sie aber nicht zulässig, so dass die kontinuierliche Relaxierung durch die Cliquen-Ungleichung schärfer wird.
Eine weitere intuitive Technik beim Sortieren von Socken ist es, kurze Socken nur mit anderen kurzen Socken zu vergleichen - und lange Socken mit langen Socken. Normalerweise kennen wir unsere Socken so gut, dass wir auf einen Blick erkennen, ob eine Socke lang oder kurz ist. Ein solcher Blick kann einen genaueren Vergleich überflüssig machen. Wenn wir eine kurze und eine lange Socke vergleichen, können wir den Vergleich abkürzen, indem wir sofort wegen des Längenunterschieds die nächste Socke vergleichen. Manche Leute waschen lange Socken auch getrennt von kurzen Socken. Das ähnelt dem letzten Trick dieses Artikels im kommenden Abschnitt.
Ein mathematischer Optimierungsalgorithmus verwendet clevere Ansätze, so genannte Heuristiken, um zulässige Lösungen zu finden (d. h. Lösungen, die alle Nebenbedingungen erfüllen). Heuristiken garantieren nicht, dass sie eine zulässige Lösung finden, aber in der Praxis sind sie oft innerhalb kurzer Zeit erfolgreich. Ein Algorithmus kann daher eine kurze Zeit damit verbringen, heuristisch nach neuen Lösungen zu suchen, in der Hoffnung, dabei einige qualitativ hochwertige Lösungen zu finden. Beim Sortieren von Socken wäre ein ähnlicher Ansatz eine kurze Socke nur mit anderen kurzen Socken zu vergleichen, die im aktuellen unsortierten Haufen sichtbar sind: Vielleicht findet man ein Sockenpaar und musste den Haufen dazu nicht einmal anfassen. Allerdings gibt es keine Garantie dafür, dass dies funktioniert, da die Partnersocke auch im Haufen vergraben sein kann.
Der Vorteil, eine gute zulässige Lösung zu finden, hängt mit dem „Branch-and-Bound“-Algorithmus zusammen, mit welchem gemischt-ganzzahlige Probleme gelöst werden. Das bedeutet, dass die Löser das Problem intern in kleinere Teile aufteilen. In jedem Teil ist eine Abschätzung für die bestmögliche Lösung leicht zu finden. Zum Beispiel könnte ein Problem mit einer ganzzahligen Variablen v mit den Grenzen 0 bis 10 in drei Teile unterteilt werden: Im ersten Teil kann v Werte zwischen 0 und 3 annehmen, im zweiten Teil Werte zwischen 4 und 6 und im dritten Teil Werte zwischen 7 und 10. Gesucht wird eine Lösung mit minimalen Kosten. Die untere Schranke für die optimale Lösung im ersten Teil ist 3. Im zweiten bzw. dritten Teil sind diese unteren Schranken 6 bzw. 4. Obwohl die optimale Lösung unbekannt ist, haben wir die Garantie, dass es keine zulässige Lösung mit Kosten unterhalb dieser Grenzen gibt.
Wenn eine Heuristik nun im ersten Teil eine zulässige Lösung mit Kosten von 5 findet, ist dies ein wertvolles Ergebnis. Obwohl es noch nicht möglich ist, zu sagen, ob diese Lösung optimal ist, haben wir jetzt eine Lösung, die besser ist als jede Lösung, die wir im zweiten Teil des Problems finden könnten, wo die untere Schranke für die minimalen Kosten 6 ist. Wir wissen jetzt also, dass v in der optimalen Lösung keinen Wert zwischen 4 und 6 haben wird. Der verbleibende algorithmische Aufwand kann sich auf die anderen Teile des Problems konzentrieren. Mithilfe einer guten zulässigen Lösung konnte der Algorithmus die Problemgröße um ein Drittel reduzieren. Dies ist auch eine sehr wichtige Technik, um zu vermeiden, dass alle zulässigen Lösungen ausprobiert werden müssen.
Stell dir vor, du müsstest nicht nur deine Socken waschen, sondern die einer vier- oder fünfköpfigen Familie! Wenn jede Person seit der letzten Wäsche 10 Paar Socken getragen hat, wären das 40 bis 50 Sockenpaare. Bei einer solchen Anzahl ist der Aufwands, der erforderlich ist, um die Socken zu sortieren, ein absoluter Albtraum. Aber es gibt eine elegante Möglichkeit, dieses Problem zu umgehen: Indem du die Socken aller Familienmitglieder nicht in der gleichen Wäsche wäschst. Oder, du lässt jedes Familienmitglied sein eigenes Sockennetz verwenden, so dass du am Ende fünf Haufen mit je 10 Paaren sortieren muss, anstatt einen Haufen mit 50 Paaren. Im schlechtesten Fall können wir einen kleinen Haufen von 10 Paaren mit 100 Vergleichen sortieren, was zu 500 Vergleichen für fünf kleine Haufen führt. Der große Haufen mit 50 Sockenpaaren erfordert dagegen im schlechtesten Fall 2500 Vergleiche, also den fünffachen Aufwand für genau dieselbe Menge an Socken!
Außerdem hindern uns kleine Haufen nicht daran, die Tricks anzuwenden, die wir zuvor besprochen haben. Wenn wir mit dem Sortieren eines Haufens von 10 Sockenpaaren beginnen können, indem wir zunächst zwei sehr bunte Sockenpaare bilden, dann ein Paar finden, das zweimal vorkommt, bevor wir zwei Paar Sneaker in einem Haufen von ansonsten langen Socken aussortieren, bleiben nur fünf Sockenpaare übrig. Ein solcher Haufen kann höchstens 25 Vergleiche erfordern, um alle Socken zu finden. Wir können also selbst an einem schlechten Tag problemlos fünf Sockenhaufen sortieren und unser Leben anderen Dinge als der Wäsche widmen.
In praktischen Anwendungen mathematischer Optimierung können die Modelle, die die anstehenden Entscheidungen beschreiben, schnell sehr groß werden. Bei großen Problemen lassen sich jedoch oft einige fast unabhängige Komponenten identifizieren. Ein Experte für mathematische Optimierung kann diese Komponenten als separate Optimierungsprobleme behandeln und einen intelligenten Algorithmus entwickeln, der sicherstellt, dass die ursprüngliche Kopplung zwischen den Komponenten weiterhin berücksichtigt wird. Ich selbst habe meine ganze Doktorarbeit über die Entwicklung geeigneter Dekompositionen für reale Probleme bei der Energiewende geschrieben. Bei der Sortierung von Socken ist ein solches Fachwissen nicht erforderlich. Um sicherzustellen, dass die einzelnen Sockenhaufen voneinander unabhängig sind, reicht es aus, vor der Wäsche jeden Haufen nur mit passende Sockenpaaren zu bilden.
Wie bei kleinen Sockenhaufen sind die summierten Laufzeiten zur Lösung vieler kleiner Optimierungsprobleme im schlechtesten Fall viel kleiner ist als die Laufzeit eines großen Optimierungsproblems im schlechtesten Fall. Wieder können die anderen Tricks, vom Presolving bis zur Verwendung praktischer Heuristiken, auch bei kleineren Problemen angewandt werden. Durch die Kombination mehrerer Tricks kann die Laufzeit zur Lösung eines real relevanten Problems in der Praxis oft deutlich kürzer sein, als im schlechtesten Fall möglich wäre.
Wenn du Hilfe bei der Automatisierung komplizierter Entscheidungsprozesse auf einem unübersichtlicheren Gebiet als der Sortierung von Socken benötigst, bist du hier genau richtig. Mathematische Optimierung und ihre Tricks lassen sich auf eine Vielzahl von Problemen anwenden, zum Beispiel zur Reduktion von Energiekosten, zur Produktionsplanung oder für logistische Herausforderungen. Berichte mir von deinem Problem, und ich veranschauliche meine Gedanken mit anschaulichen Beispielen. Wir könnten den Aufwand für eine optimale Entscheidung so reduzieren, dass Sie nur noch einen Knopf drücken müssen.
Dank an Marvin Düvel und Dennis Veltmann für das Korrekturlesen dieses Artikels.
Modellbasierte digitale Transformation ist DAS Mittel der Wahl, um Branchen in die digitale Zukunft zu führen. Dieser Ansatz bietet einen schnellen Einstieg, ist agil umsetzbar und auf vielen Ebenen wertvoll.
Im Sommer habe ich meine Promotionsurkunde bekommen, die den Erfolg meiner Forschung im Bereich der Entwicklung mathematischer Optimierungsalgorithmen und -software bescheinigt. Zu diesem Anlass habe ich über meinen bisherigen Weg nachgedacht und darüber, was ich anders machen würde - hier ist das Ergebnis.
