DE
von Tim Varelmann
Wer das Buch "Harry Potter und der Stein der Weisen" gelesen hat, weiß, dass nach dem von Professor McGonagall verzauberten Schachspiel noch weitere Herausforderungen auf Harry und Hermine warten, bevor sie zum Stein der Weisen kommen und den von der weißen Schach-Dame ausgeknockten Ron zum Krankenflügel bringen können: Nach einem glücklicherweise schon bewusstlosen Troll müssen die beiden noch ein Zaubertränke-Rätsel von Professor Snape lösen: Sie stehen vor einem Tisch mit 7 verschiedenen Flaschen, als plötzlich ein schwarzes Feuer vor ihnen den Weg zum Stein der Weisen blockiert und ein purpurfarbenes Feuer den Weg zurück zu Ron versperrt. Neben den Flaschen liegt ein Pergament mit folgendem Rätsel:
Die Gefahr liegt vor euch, die Rettung zurück,
Zwei von uns helfen, bei denen habt ihr Glück,
Eine von uns sieben, die bringt euch von dannen,
Eine andere führt den Trinker zurück durch die Flammen,
Zwei von uns enthalten nur guten Nesselwein,
Drei von uns sind Mörder, warten auf eure Pein.
Wählt eine, wenn ihr weiterwollt und nicht zerstäuben hier.
Euch helfen sollen Hinweis' - und davon ganze vier:
Erstens: so schlau das Gift versteckt mag sein,
's ist immer welches zur Linken vom guten Nesselwein;
Zweitens: die beiden an den Enden sind ganz verschied'ne Leut,
doch wenn ihr eine weitergeht, so ist keine davon euer Freund;
Drittens: wie ihr deutlich seht, sind alle verschieden groß.
Doch weder der Zwerg noch der Riese enthalten euren Tod.
Viertens: die zweite von links und die zweite von rechts werden Zwillinge sein,
so verschieden sie schauen auf den ersten Blick auch drein.
J. K. Rowling, Harry Potter und der Stein der Weisen
Im Buch löst Hermine dieses Rätsel mit kühlem Kopf. Für Muggel wie mich, welche seit ihrem 11. Geburtstag noch immer auf ihre Einladung nach Hogwarts warten, bleibt nur die Möglichkeit Hilfe vom Computer in Anspruch zu nehmen. Genial, diese Muggel!
Die erste Aufgabe bei der Formulierung eines Optimierungsproblems ist - in der realen wie der magischen Welt - das Ausräumen von Missverständnissen durch klare Kommunikation. Der Teil "wenn ihr eine weitergeht" im zweiten Hinweis klingt, als würde er sich auf die Nachbarn der vorher genannten Flaschen beziehen. Auch ich habe diesen Satz so verstanden. Aber als ich alle vier Hinweise gelesen hatte, fiel mir auf, dass kein einziger Hinweis dabei hilft zu unterscheiden welcher Trank sicher durchs schwarze Feuer und welcher Trank sicher durchs purpurfarbene Feuer führt. Hermine hingegen wählt im Buch sicher aus, welcher Trank durch welches Feuer führt. Ich musste das Problem also irgendwo missverstanden haben und tat was jeder guter Programmierer tut, wenn er nicht weiterkommt. Ich googelte nach Snape's Rätsel. Es stellt sich heraus, dass ich eine alte Auflage von Harry Potter und der Stein der Weisen hatte, später wurde die Stelle korrigiert. In der korrigierten Fassung wird klar, dass keine der beiden Flaschen am Ende den Zaubertrank zum Weitergehen enthält.
Nun können wir endlich das magische Rätsel in die Sprache von Computern übersetzen. Dazu spezifizieren wir eine ganze Menge von Entscheidungen, die der Computer treffen soll, und geben ihm dazu einen Haufen Bedingungen, die er dabei erfüllen muss: Wir haben 4 verschiedene Inhalte: 3x Gift, 2x Nesselwein, 1x Purpur-Feuer-Trank und 1x Schwarzes-Feuer-Trank und wollen herausfinden an welcher der 7 Positionen wir welchen Flascheninhalt finden. Darum geben wir dem Computer für jede Position vier Entscheidungen, die er mit 'Ja' oder 'Nein' beantworten muss. Steht an dieser Position Gift? Steht an dieser Position Nesselwein? Steht an dieser Position Purpur-Feuer-Trank? Steht an dieser Position Schwarzes-Feuer-Trank?
Da ein Computer Mathematik besser versteht als Text, programmieren wir den Computer so, dass er sogenannte Binäre Variablen anlegt. Dies sind Variablen, denen er entweder den Wert 1 oder den Wert 0 zuweisen kann. Die 1 entspricht der Antwort 'Ja', die 0 entspricht der Antwort 'Nein'. Wir nummerieren die Positionen p von 1 (ganz links) bis 7 (ganz rechts) durch und kürzen die Inhalte i mit den Buchstaben G für Gift, N für Nesselwein, P für Purpur-Feuer-Trank, und S für Schwarzes-Feuer-Trank ab. Um dem Computer eine Entscheidung zu erlauben, führen wir binäre Variablen F für die Flaschenentscheidungen ein. Mit den kleinen Buchstaben p und i geben wir die Position und den Inhalt an, um die es bei der Entscheidung geht.
So ist die Variable F1,G Repräsentant der Entscheidung "Steht an Position 1 Gift?".
Da wir den Computer nun 28 Entscheidungen treffen lassen (4x 'Ja'/'Nein' an 7 Positionen), müssen wir ihm auch besondere Bedingungen mitgeben, wie diese Entscheidungen zu treffen sind. Und bevor wir die Hinweise von Snape's Rätsel in Mathematik übersetzen können, müssen wir erstmal verhindern, dass der Computer mit seinen 28 Entscheidungen groben Blödsinn anstellen kann. Grober Blödsinn wäre es beispielsweise, wenn an Position 1 sowohl Gift, als auch Nesselwein stünden. Andererseits könnte der Computer alle Entscheidungen auf Position 2 mit 'Nein' beantworten, was ebenfalls in die Kategorie grober Blödsinn fällt. Wir fordern den Computer daher auf, die folgenden Bedingungen einzuhalten:
Nun wird für alle Positionen immer genau eine unserer 4 Fragen mit 'Ja' beantwortet. Das ist besser, erlaubt aber immer noch etwas Blödsinn, zum Beispiel auf jeder Position die Frage nach dem Nesselwein mit 'Ja' zu beantworten. Wir ergänzen darum weitere Bedingungen:
Jetzt muss der Computer genau an 3 Positionen die Frage nach dem Gift mit 'Ja' beantworten, genau an 2 Positionen die Frage nach dem Nesselwein mit 'Ja' beantworten, und so weiter...
Wir können nun also die einzelnen Hinweise des Rätsels modellieren:
Diesen Hinweis übersetzen wir in zwei Teile: Die ganz linke Flasche und alle anderen. Für die ganz linke Flasche gilt einfach: sie kann keinen Nesselwein enthalten, weil links von ihr kein Platz für Gift ist.
Falls an einer Position Nesselwein ist, muss links davon Gift stehen. Da der Wert für die Gift-Entscheidung nur 0 oder 1 sein kann, erzwingt die folgende größer-gleich-Bedingung eine 1 beim Gift, wenn der rechte Nachbar eine 1 beim Nesselwein hat. Es muss aber nicht rechts von jedem Gift ein Nesselwein zu finden sein (es gibt schließlich nur zwei). Letzteres würde zusätzlich gefordert, wenn wir ein Gleichzeichen in der Bedingung nutzen würden.
Auch hier teilen wir den Hinweis in zwei Teile auf, denn die beiden Satzteile enthalten jeweils einen Hinweis. Im ersten Teil fordern wir für jeden Inhalt, das von den Flaschen 1 und 7 nur eine Entscheidung für diesen Inhalt mit 'Ja' beantwortet werden darf. Dies verbietet, dass Flaschen 1 und 7 denselben Inhalt haben, da dann für diesen selben Inhalt die Entscheidung auf beiden Positionen 'Ja' (=1) sein müsste, so dass die Summe aus beiden Entscheidungswerten 2 werden würde.
Der zweite Teil verbietet den Schwarzes-Feuer-Trank für die Flaschen 1 und 7 komplett. Hier zahlt es sich aus, dass wir zum Rechnen 0 und 1 verwenden, statt 'Ja' und 'Nein'. Wir können die binären Variablen aufsummieren und fordern, dass die Summe Null sein muss. Diese eine Forderung kann nur erfüllt sein, wenn beide Werte 0 sind, also die Frage nach dem Schwarzes-Feuer-Trank an beiden Positionen mit 'Nein' beantwortet wird. Obwohl wir also eine Forderung für Position 1 und eine Forderung für Position 7 hatten, reicht es aus, nur eine Bedingung zu formulieren.
Es wäre auch möglich gewesen, diese Bedingung auf 2 Bedingungen aufzuteilen, um die jeweilige Entscheidung "Ist Schwarzes-Feuer-Trank auf Position 1?" und "Ist Schwarzes-Feuer-Trank auf Position 7?" einzeln mit 'Nein' zu beantworten bzw. die jeweilige Variable auf 0 zu setzen. Der Rechenaufwand für den Computer ist aber in aller Regel geringer, wenn er weniger Bedingungen erfüllen muss, darum ist die Summenformulierung sehr elegant.
Bei genauem Hinsehen fällt außerdem auf, dass der erste Teil von Hinweis 2 schon eine Bedingung an die Summe der Entscheidungen "Ist Schwarzes-Feuer-Trank auf Position 1?" und "Ist Schwarzes-Feuer-Trank auf Position 7?" gestellt hatte, nämlich dass die Summe kleiner oder gleich 1 sein muss. Sobald jedoch die zweite Bedingung, dass diese Summe 0 sein muss, erfüllt ist, ist die vorherige Bedingung natürlich auch immer erfüllt. Weil wir dem Computer nur wenige Bedingungen stellen wollen, korrigieren wir, und fordern die erste Bedingung von Hinweis 2 nur für die Inhalte, Gift, Nesselwein, und Purpur-Feuer-Trank:
Während Hermine die Flaschen vor sich auf dem Tisch sehen kann, können wir nur spekulieren, wo die größte und wo die kleinste Flasche steht. Wir nutzen zur Formulierung der Bedingungen an den Computer daher erstmal Platzhalter R für Riese und z für Zwerg und kommen später auf das Problem zurück, wo Riese und Zwerg nun stehen:
Auch hier haben wir wieder eine Summe gebildet um zwei Entscheidungen mit nur einer Bedingung festzulegen, nämlich dass sowohl beim Riesen als auch beim Zwerg die Entscheidung für Gift 'Nein' sein muss.
Für jeden Inhalt muss also die Entscheidung an den Positionen 2 und 6 gleich ausfallen - entweder sind beide Entscheidungen 'Nein', oder es sind beide Entscheidungen 'Ja'.
Nicht vergessen: Wir haben bereits gefordert, dass an jeder Position die Entscheidung für genau einen Inhalt mit 'Ja' beantwortet werden muss, darum kann es nicht passieren, dass wir gleichzeitig Gift und Nesselwein auf den Positionen 2 und 6 haben. Ein Mensch hat außerdem auch die Intuition, dass weder Schwarzes-Feuer-Trank noch Purpur-Feuer-Trank auf Position 2 oder 6 platziert sein können, weil es beide nur einmal gibt, und sie darum keine Zwillinge haben können. Ob dem Computer das auch klar ist? Das ist es: Der Computer kennt auch die Bedingung, dass die Summe der Schwarzes-Feuer-Trank-Variablen über alle 7 Positionen genau 1 sein muss und auch die Summe der Purpur-Feuer-Trank-Variablen über alle 7 Positionen genau 1 sein muss. Die einzige Möglichkeit, alle Bedingungen zu erfüllen, ist also , dass irgendwelche Flaschen an anderen Positionen als 2 und 6 den Schwarzes-Feuer-Trank und den Purpur-Feuer-Trank enthalten.
Wir haben das Problem nun vollständig modelliert. Mit der passenden Software, die das Problem lösen kann, kann der Computer nun herausfinden, welche Flaschen an welchen Positionen welchen Inhalt haben. Dafür müssen wir aber noch spezifizieren, wo Riese und Zwerg stehen. Ganz entscheidend ist, dass das Rätsel im Buch für Hermine eindeutig lösbar ist, weil sie sehen kann, wo Riese und Zwerg stehen. Wir haben diese Information nicht. Darum erweitern wir hier das Gesamtproblem: Wir wollen nicht mehr nur wissen, wie die Lösung zu Snapes Rätsel aussieht, sondern wir wollen auch wissen was Harry und Hermine vor sich auf dem Tisch sehen. Um das herauszufinden, haben wir zwei Möglichkeiten, die auch häufig bei Optimierungsproblemen in der Muggelwelt zum Einsatz kommen: Rohe Rechengewalt und cleveres Umschauen.
Die Methode rohe Rechengewalt bedeutet, alle Möglichkeiten auszuprobieren. Der Riese kann an einer von 7 Positionen stehen. Wenn der Riese feststeht, bleiben noch 6 andere Positionen an denen der Zwerg stehen könnte, da jede Flasche verschieden groß ist. Das heißt, wir müssten 7*6=42 Einzelprobleme lösen. Für unser kleines Optimierungsproblem wäre das möglich.
Bei genauem Hinsehen, wäre das aber schon zu viel Aufwand: Was der Zwerg und was der Riese ist, ist für das Optimierungsproblem unwichtig. Entscheidend ist, dass an beiden Positionen kein Gift stehen kann. Wenn wir das Optimierungsproblem also beispielsweise lösen würden mit dem Riesen an Position 1 und dem Zwerg an Position 2 kann kein Gift auf Position 1 und 2 sein. Würden wir jedoch den Zwerg an Position 1 und den Riesen an Position 2 platzieren, kann genauso kein Gift auf Position 1 und 2 sein. Mathematiker sprechen in solch einer Situation von Symmetrie: Das Problem ist symmetrisch in Bezug auf die Positionen von Riese und Zwerg. Wenn man auf die Symmetrie achtet, kann man diese Eigenschaft ausnutzen, um sich Rechenarbeit zu ersparen: Hier rechnen wir die Lösung nur dann aus, wenn der Riese links vom Zwerg steht. Dann sind alle verschiedenen Möglichkeiten eindeutig und wir wissen, dass wir jedes Mal auch die Position von Riese und Zwerg tauschen könnten, ohne dass sich die einmal ausgerechnete Lösung verändern würde. Somit müssen wir weniger Probleme lösen, wie die folgende Tabelle veranschaulicht:
Es bleiben also 21 Szenarien für die wir das Rätsel durch Optimierung lösen. Einige der Szenarien haben möglicherweise gar keine Lösung.
Als Beispiel dafür nehmen wir an, Riese und Zwerg seien auf den Positionen 1 und 2. Nun kann laut Hinweis 3 kein Gift auf den Positionen 1 und 2 sein kann. Laut Hinweis 4 sind die Flaschen auf den Positionen 2 und 6 Zwillinge. In diesem Beispiel müssen die Zwillinge Nesselwein sein weil Gift nicht auf Position 2 stehen kann (Riese/Zwerg) und die beiden Feuer-Tränke keine Zwillinge haben. Allerdings fordert Hinweis 1, dass links vom Nesselwein Gift stehen muss. Da auf Position 2 und 6 Nesselwein steht, müsste um Hinweis 1 zu erfüllen auf Position 1 und 5 Gift stehen. Da Position 1 aber Riese oder Zwerg ist, darf hier in unserem Beispiel kein Gift sein, um Hinweis 3 nicht zu widersprechen.
Wir können die Hinweise 1, 3, und 4 nicht gleichzeitig erfüllen wenn Riese und Zwerg auf den Positionen 1 und 2 sind. Weil Hermine im Buch aber eine Lösung findet, die alle Hinweise beachtet, können Riese und Zwerg nicht auf den Positionen 1 und 2 stehen. So eine Situation ist in der folgenden Lösungstabelle mit Strichen dargestellt.
Andererseits gibt es auch Szenarien, wo mehrere Lösungen alle Bedingungen erfüllen können. In diesem Fall habe ich eine Lösung in der Tabelle dargestellt, und pro Alternativer Lösung ein Stern hinter die Spezifikation von Riese und Zwerg gemacht:
Bei Optimierungsproblemen in der Muggelwelt ist es ganz normal, dass einige Informationen fehlen, unklar oder widersprüchlich sind. Dann hilft es, mit vielen verschiedenen Leuten zu reden, kleine Prototypen zu zeigen und zu erklären und aufmerksam zuzuhören, was Mitarbeiter, falls möglich Kunden und Manager sagen. Und auch in der magischen Welt können wir noch ein paar kleine weitere Hinweise finden, indem wir aufmerksam lesen, was rund um das Rätsel passiert:
Als Hermine das Rätsel gelöst hatte, sagte sie zu Harry: "Ich hab's. Die kleinste Flasche bringt uns durch das schwarze Feuer". Harry fragt daraufhin, welche zurück durch die Purpurflammen führe, und Hermine "deutete auf eine bauchige Flasche am einen Ende der Reihe".
Wir könnten diese Informationen nun auch in unser Modell einfließen lassen. Beispielsweise könnten wir die Bedingung, dass genau ein Purpur-Feuer-Trank existiert neu formulieren, und anstatt über alle Positionen zu summieren, nur Position 1 und 7 summieren und für Positionen 2-6 gar keinen Purpur-Feuer-Trank erlauben.
Andererseits kann man aus den neuen Hinweisen auch nicht klar schließen, wo Riese und Zwerg platziert sind. Im Gegenteil: Die Information, dass in der kleinsten Flasche der Schwarzes-Feuer-Trank ist, ist erst hilfreich, wenn wir die Zwergposition schon festgelegt haben. Daher müssen wir ohnehin auch etwas rohe Rechengewalt anwenden, um herauszufinden wie genau Harry und Hermine rätseln mussten. Außerdem bricht diese Bedingung die Symmetrie, weil nun im Zwerg mehr Information als im Riesen steckt, von dem wir nur wissen, dass sein Inhalt kein Gift ist.
Anstelle der unsymmetrischen Berechnung können wir nochmal durch die Lösungen aus dem vorherigen Abschnitt gehen. Wir streichen alle Lösungen als unpotterhaft, in denen der Purpur-Feuer-Trank weder auf Position 1 noch auf Position 7 ist. Außerdem muss der Schwarzes-Feuer-Trank der Zwerg sein. Falls der Schwarzes-Feuer-Trank der Riese sein sollte, können wir aus der Tabelle mit symmetrischen Lösungen die Position von Riese und Zwerg vertauschen, um trotzdem eine potterhafte Lösung zu finden. Schließlich können wir davon ausgehen, dass die Lösung eindeutig ist weil Hermine sicher zuordnen kann, wo welcher Trank steht. Darum können wir auch alle Szenarien streichen, die einen oder mehrere Sterne hatten, also mögliche alternative Lösungen. Dann bleiben folgende Lösungen übrig:
Für die nächste Potter-Fan Party, hast du mit diesem Rätsel also immer noch mehrere Szenarien zur Auswahl, die zu der Beschreibung im Buch passen. Der Riese muss aber immer einer der Zwillinge sein, und der einzige Unterschied in den Inhalten der Flaschen hängt davon ab, ob der Zwerg auf Position 3 oder 4 ist.
Wir haben gesehen, dass magische und nicht-magische Optimierungsprobleme komplizierte Entscheidungen mittels Mathematik für den Computer verständlich übersetzen. Dabei ist es entscheidend, Kommunikationsschwierigkeiten oder Übersetzungsfehler zu erkennen und auszuräumen. Manchmal ist es durch cleveren Einsatz mathematischer Eigenschaften möglich, mehrere Bedingungen in der echten Welt als eine mathematische Bedingung darzustellen - das spart Rechenaufwand, genauso wie das Erkennen und Ausnutzen von Symmetrie im Problem. Schließlich kann es trotz aller Sorgfalt vorkommen, dass nicht alle Informationen oder Daten vorliegen. Mit einem sauber formulierten Optimierungsproblem finden wir auch dann noch Mittel und Wege zu einer oder mehreren zufriedenstellenden Lösungen zu kommen.
Wenn du noch weiter experimentieren möchtest, findest du meine implementierten Modelle in den öffentliche Repositories für die Implementierung in GAMS und Pyomo.
Und wenn du dir für deine Entscheidungen selbst mehr digitale und intelligentere Unterstützung von deinem Computer wünscht, gib mir Bescheid.
Vielen Dank an Sophie Ziegler für das Korrekturlesen dieses Artikels und ihre wertvollen Hinweise.
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.
