Mathematisches Glossar

Algorithmus - Unter einem Algorithmus versteht man eine Anleitung zur schrittweisen Lösung eines gegebenen Problems.

Dynamische Optimierung - Optimallösungen für diskrete Optimierungsprobleme lassen sich häufig rekursiv aus optimalen Teillösungen zusammensetzen. Zum Beispiel muss in einem Graphen für einen kürzesten Weg von s nach t, der über den Knoten r geht auch der Teilweg von s nach r und von r nach t optimal sein. Dieses Prinzip der Optimalität, Teillösungen von Optimallösungen sind selbst optimal, macht sich die dynamische Programmierung zu nutzen, indem Optimallösungen sukkzessive aus Teillösungen zusammengesetzt werden.

Gemischt Ganzzahlige Optimierung - Lineares Optimierungsproblem (LP), bei dem an eine Teilmenge der Menge aller Variablen Ganzzahligkeitsforderungen gestellt werden.

Genetischer Algorithmus - Die grundlegende Idee genetischer Algorithmen ist, nicht nur eine Lösung zu betrachten und zu versuchen, diese zu verbessern, sondern eine Menge von Lösungen (Population genannt) zu betrachten und durch Kombinationen dieser Lösungen zu neuen besseren Lösungen zu gelangen. Die Grundmuster und Begriffswelt sind dabei aus der Genetik entnommen. Aus einer Population werden eine Reihe von Elternpaaren (Paare von Lösungen) bestimmt, die sich kreuzen und damit eine oder mehrere neue Lösungen erzeugen. Diese Lösungen (evtl. zusammen mit den Eltern) werden teilweise noch mutiert. Basierend auf ihrer Fitness wird eine neue Generation ausgewählt und der Prozess wiederholt.

Heuristik - Eine Heuristik ist ein zur Lösung eines Problems verwendetes Verfahren, das nicht garantieren kann, die exakte Lösung zu finden. Heuristische Verfahren nützen häufig die sehr spezielle Struktur von Problemen aus, damit sie zu effizienten Verfahren werden und somit im Gegensatz zu exakten Verfahren schnell zulässige Lösungen finden. Ein bekanntes Beispiel ist die sog. Greedy-Heuristik. Das Ergebnis einer Heuristik kann allerdings deutlich schlechter sein als das Ergebnis eines exakten Algorithmus.

Lineares Optimierungsproblem (LP) - Minimierung oder Maximierung einer linearen Zielfunktion über einem Polyeder.

LP-Relaxierung - LP-Problem, das entsteht, wenn die Ganzzahligkeitsforderungen an die Variablen eines gemischt ganzzahligen Problems weggelassen werden.

LP-Verfahren - Lösungsverfahren für lineare Optimierungsprobleme. Meistverwendetes Verfahren ist der bekannte Simplex-Algorithmus, der in jedem Standardlöser integriert ist.

Polyeder - Teilmenge eines Vektorraumes, die die Schnittmenge von endlich vielen Halbräumen ist.

Schnittebenenverfahren - Unter Schnittebenen versteht man i.W. nichts weiter als lineare Ungleichungen. Diese werden in einem Schnittebenenverfahren im Prinzip wie folgt genutzt: Bei der Lösung eines gemischt ganzzahligen Problems geht man von der LP-Relaxierung des Problems aus. Erfüllt die Lösung dieses linearen Problems nicht die Ganzzahligkeitsforderungen, so werden Schnittebenen zur Problemformulierung hinzugefügt, die den Bereich der zulässigen Lösungen des gemischt ganzzahligen Problems nicht einschränken, die gefundene Lösung der LP-Relaxierung aber abschneiden. Dieser Prozess wird iterativ fortgeführt, bis die solcherart verschärfte LP-Relaxierung eine Lösung besitzt, die die Ganzzahligkeitsforderungen erfüllt. Wird dieses Schnittebenenverfahren durch geeignete Branch-and-Bound Techniken ergänzt, spricht man von einem Branch-and-Cut Verfahren.

Simulated Annealing - Simulated Annealing ist eine Heuristik, bei der innerhalb der einzelnen Lösungschritte nicht nur Verbesserungen, sondern auch zufallsgesteuert schlechtere Lösungen zugelassen werden. Die Idee dabei ist, bessere Lösungen immer zu erlauben, schlechtere jedoch nur mit einer gewissen Wahrscheinlichkeit. Dabei ist die Wahrscheinlichkeit um so geringer je schlechter die Lösung ist. Darüber hinaus wird die Wahrscheinlichkeit, schlechtere Lösungen zu akzeptieren, im Laufe des Verfahrens immer weiter verringert, so dass der Algorithmus mit einer guten Lösung enden sollte.

Standardlöser - (Kommerzielles) Tool, das zur Lösung allgemeiner gemischt ganzzahliger Optimierungsprobleme ohne Ausnutzung spezieller Strukturen des betrachteten Problems genutzt werden kann.