Seit ich kürzlich auf meinem Smartphone diverse Messenger installiert habe, bekomme ich von Freunden und der Familie immer wieder Bilder und Videos geschickt, auf denen mathematische Spielereien zu sehen sind.
So auch heute Morgen: Per Video wird ein besonderes magisches 4×4-Quadrat gezeigt, bei dem alle Reihen die gleiche Summe bilden, alle Spalten, beide Diagonalen, das innere Quadrat und noch so einige andere Kombinationen aus vier Feldern. Das Besondere an diesem magischen Quadrat: Die erste Reihe bildet gleichzeitig noch Tag, Monat, Jahrhundert und Jahr des Geburtstags desjenigen Mathematikers, der laut diesem Video dieses Quadrat entdeckt haben soll.
Auch in der Vergangenheit gab es immer wieder Beispiele für magische Quadrate. Kunstinteressierte kennen sicher Albrecht Dürers „Melencolia I“, ein Kupferstich aus dem Jahre 1514, der ebenfalls ein solches magisches Quadrat enthält – in diesem Fall nur mit einer Jahreszahl statt eines Datums, dafür mit der konsequenten Verwendung der Zahlen 1-16, statt sich beliebiger Zahlen zu bedienen:
Gibt's da einen Trick?
Im Video wird anschließend eine Methode gezeigt, mit der man systematisch aus seinem eigenen Geburtstag ebenfalls ein solches magisches Quadrat entwickeln kann. Dies ist durch einfache Addition und Subtraktion der vorgegebenen ersten Zeile (das eigene Geburtsdatum) möglich. Einziges Problem dabei: Wenn eine der Zahlen zu klein ist, funktioniert die Methode nicht mehr, da die Zahlen dann in den negativen Bereich rutschen – eine Eigenschaft, die man bei magischen Quadraten vermeiden sollte.
Was macht also der Mathematiker von heute? Er greift zu Constraint Programming (CP), in diesem Fall der CP-Solver des CPLEX Optimization Studios.
Bedingungen definieren und direkt das Ergebnis erhalten
Die einzelnen Felder sind unsere Variablen, nach Vorgabe oben als positive Integerwerte definiert. Alle Summen, die nun übereinstimmen sollen, werden als Entscheidungsausdrücke definiert, so also die Summe aller Zeilen, aller Spalten, aller Diagonalen etc. Anschließend wird im subject to-Block, also in dem Bereich des Modells, in dem die Bedingungen definiert werden, angegeben, dass diese Summen alle übereinstimmen sollen.
Den Rest übernimmt der Solver: Man muss nun keine eigenen Algorithmen mehr entwickeln, um auch in solchen Spezialfällen zu einer Lösung zu gelangen. Der Computer berechnet das völlig eigenständig. In meinem Testbeispiel präsentierte mir der Solver eine Lösung nach weniger als einer Zehntelsekunde.
Warum nun Constraint Programming und nicht lineare Optimierung? Weil wir hierdurch (sofern es dann noch eine Lösung gibt) eine weitere Eigenschaft mit hinzunehmen können: Der CP-Ansatz erlaubt uns eine weitere Bedingung einzubauen, nämlich, dass alle Zahlen unterschiedlich sein sollen. Dies mit linearer Optimierung zu modellieren wäre relativ aufwändig, mit dem CP-Ansatz reicht dafür eine weitere Zeile.
Relevanz für die Praxis – zum Beispiel im Warenlager
Natürlich kommen im Alltag selten Probleme vor, in denen man einzelne Zahlen zuordnen muss. Aber nehmen wir an, diverse Waren müssen innerhalb eines Lagers aufbewahrt werden. Auch dort existiert jede Ware nur einmal, d.h. die gleiche Ware (= die gleiche Zahl) darf nicht mehrfach genutzt werden.
Außerdem muss dafür gesorgt werden, dass jede Lagerebene (= jede Zeile) gleichmäßig ausgelastet wird, das Regal nicht zu einer Seite (= Spalte) hin überlastet ist usw. Sie sehen, auch solche Spielereien können auf die reale Welt übertragen werden – und zum Glück benötigt man dann keine Magie, um eine Lösung zu finden.
Sprechen Sie uns an!
Haben wir Ihr Interesse geweckt? Wollen Sie weitere Informationen dazu, wie Sie mathematische Optimierung für Ihr Unternehmen gewinnbringend einsetzen können? Sprechen Sie uns gerne an, wir freuen uns auf das Gespräch mit Ihnen!
Autor
Marc Arnoldussen
X-INTEGRATE Software & Consulting GmbHKontakt