Loading AI tools
Zweig der diskreten Mathematik Aus Wikipedia, der freien Enzyklopädie
Die kombinatorische Optimierung ist ein Teilgebiet der mathematischen Optimierung, welches sich damit beschäftigt, ein optimales Element in einer endlichen, aber sehr großen, Menge zu bestimmen. Die meisten kombinatorischen Optimierungsprobleme können natürlich in der Sprache der Graphentheorie oder der (gemischt-) ganzzahligen linearen Optimierung dargestellt werden.[1] Typische kombinatorische Optimierungsprobleme sind das Problem des Handlungsreisenden, der minimale Spannbaum und das Rucksackproblem. Die kombinatorische Optimierung ist Teil der diskreten Mathematik und des Operations Research mit engem Bezug zur theoretischen Informatik und der künstlichen Intelligenz.
Wie der Name bereits andeutet, geht es in der kombinatorischen Optimierung darum, aus einer großen Menge von diskreten Elementen (Gegenstände, Orte) eine Teilmenge zu konstruieren, die gewissen Nebenbedingungen entspricht und bezüglich einer Zielfunktion (auch Kosten- oder Bewertungsfunktion) optimal ist (kleinstes Gewicht, kürzeste Strecken, …). Derartige Fragestellungen spielen in der Praxis eine große Rolle. Die optimale Wegeplanung eines Bohrers auf einer Leiterplatte[2], die kostenoptimale Belegung von Maschinen[3] oder die möglichst günstige Routenplanung[4] sind allesamt Vertreter dieser Problemklasse.
Ein kombinatorisches Optimierungsproblem besteht aus einer diskreten, d. h. endlichen oder abzählbar unendlichen, Menge aller möglicher Lösungen , die als zulässige Menge bezeichnet wird und einer Zielfunktion darstellt, die jedem Element aus einen Zielfunktionswert (Kosten, Gewinn, …) zuweist. Ziel ist, eine global optimale Lösung zu finden, so dass kein mit existiert (bei einem Minimierungsproblem). Es lässt sich in der Regel als (gemischt-)ganzzahliges lineares Optimierungsproblem (ILP oder MILP) darstellen.
Die Probleme, mit denen man sich in der kombinatorischen Optimierung beschäftigt, sind teilweise effizient, d. h. mit polynomiellem Aufwand, lösbar. Andere Vertreter gehören zur Klasse der NP-schweren Probleme, deren Lösung sich für wachsende Problemgröße in der Regel als sehr aufwändig gestaltet.
Die Algorithmen, die die Lösungen erzeugen sollen, versuchen daher meist, den Suchraum zu beschränken. Vertreter dieser Algorithmen sind beispielsweise Branch-and-Bound bzw. Branch-and-Cut, welche exakte, garantiert optimale Lösungen erzeugen. Dafür wird das Problem als ganzzahliges Optimierungsproblem formuliert, bei dem dann die Belegung von Entscheidungsvariablen darüber entscheidet, ob bestimmte Elemente zur Lösung gehören oder nicht.
Andere Algorithmen nutzen spezielles Wissen über die Problemstruktur, sog. Heuristiken oder Meta-Heuristiken. Hierzu gehört z. B. die lokale Suche mit ihren Ausprägungen Simulierte Abkühlung oder Tabu Search. Diese Verfahren können aber meist nicht garantieren, dass eine global optimale Lösung gefunden werden kann.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
