Kombinatorische Optimierung

Grundidee und Bedeutung

Die kombinatorische Optimierung ist ein Teilgebiet der mathematischen Optimierung. Sie untersucht, wie man aus einer endlichen, aber oft sehr großen Menge möglicher Lösungen ein optimales Element auswählt. Sie gehört zur diskreten Mathematik und zum Operations Research und hat enge Bezüge zur theoretischen Informatik sowie zur künstlichen Intelligenz.

Viele Probleme lassen sich mit Graphentheorie oder als (gemischt-)ganzzahlige lineare Optimierung darstellen. Typische Aufgaben sind das Problem des Handlungsreisenden, der minimale Spannbaum und das Rucksackproblem. Beim minimalen Spannbaum wird aus den möglichen Spannbäumen eines Graphen derjenige mit dem kleinsten Kantengewicht bestimmt.

Zulässige Lösungen und Zielfunktion

Bei einem kombinatorischen Optimierungsproblem wird aus diskreten Elementen, etwa Gegenständen oder Orten, eine Teilmenge konstruiert. Diese muss vorgegebene Nebenbedingungen erfüllen und soll hinsichtlich einer Zielfunktion optimal sein.

Eine Zielfunktion, auch Kosten- oder Bewertungsfunktion, bewertet eine Lösung beispielsweise nach Gewicht, Länge einer Strecke oder Kosten. Praktische Beispiele sind die optimale Wegeplanung eines Bohrers auf einer Leiterplatte, die kostenoptimale Belegung von Maschinen und eine möglichst günstige Routenplanung.

Formale Beschreibung

Ein kombinatorisches Optimierungsproblem wird als

P: minₓ f(x) s. t. x ∈ M

beschrieben. M ist die zulässige Menge aller möglichen Lösungen. Sie ist diskret, also endlich oder abzählbar unendlich. Die Zielfunktion f: M → ℝ ordnet jeder Lösung einen Zielfunktionswert zu, zum Beispiel Kosten oder Gewinn.

Bei einem Minimierungsproblem sucht man eine global optimale Lösung x* ∈ L, für die kein x ∈ M mit f(x) < f(x*) existiert. Solche Probleme lassen sich in der Regel als (gemischt-)ganzzahliges lineares Optimierungsproblem formulieren: als ILP oder MILP.

Algorithmen und Komplexität

Ein Teil der kombinatorischen Optimierungsprobleme ist effizient, also mit polynomiellem Aufwand, lösbar. Andere gehören zu den NP-schweren Problemen; mit wachsender Problemgröße wird ihre Lösung in der Regel sehr aufwändig.

Algorithmen beschränken deshalb meist den Suchraum. Branch-and-Bound und Branch-and-Cut sind exakte Verfahren: Sie erzeugen garantiert optimale Lösungen. Dazu wird das Problem als ganzzahliges Optimierungsproblem formuliert. Entscheidungsvariablen legen fest, ob bestimmte Elemente zur Lösung gehören.

Heuristiken und Meta-Heuristiken verwenden besonderes Wissen über die Problemstruktur. Beispiele sind lokale Suche, Simulierte Abkühlung und Tabu Search. Diese Verfahren können meist nicht garantieren, eine global optimale Lösung zu finden.

Bekannte Problemtypen

Zu den bekannten Problemen zählen unter anderem Briefträgerproblem, Behälterproblem (Bin-Packing), Constraint-Satisfaction-Problem, Problem des Handlungsreisenden, kürzester Pfad, Job Shop Scheduling, Mengenüberdeckungsproblem (Set cover problem), Rucksackproblem, Steinerbaumproblem, minimaler Spannbaum, Dominating set problem, Tourenplanung (Vehicle routing problem) und Zuordnungsproblem.

Weitere genannte Anwendungen sind das Egalisieren von variabel-gewichtigen Produkten im Prozess der Sortierung und Verpackung sowie die Ermittlung des globalen Optimums in fixed Assets (Capital Budgeting Problem / Projektportfolio-Optimierung).