Kombinatorische Optimierung

Kombinatorische Optimierung ist ein Zweig der diskreten Mathematik und spielt in vielen Bereichen einschließlich der Operations Research, der Informatik, der künstlichen Intelligenz und den Ingenieurwissenschaften eine wichtige Rolle.

Informelle Definition

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 Kostenfunktion 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, die kostenoptimale Belegung von Maschinen oder die möglichst günstige Routenplanung sind allesamt Vertreter dieser Problemklasse.

Formale Definition

Eine Instanz eines kombinatorischen Optimierungsproblems ist ein Paar $(L,f)$ , bei dem die Menge $L$ eine abzählbare Menge aller möglicher Lösungen bezeichnet und die Funktion $f$ eine Abbildung $f\colon L\rightarrow \mathbb {R}$ darstellt, die jedem Element aus $L$ einen Zielfunktionswert (Kosten, Gewinn, …) zuweist. Ziel ist, eine global optimale Lösung $i\in L$ zu finden, so dass kein $u\in L$ mit $f(u)<f(i)$ existiert (bei einem Minimierungsproblem).

Algorithmen und Komplexität

Die Probleme, mit denen man sich in der kombinatorischen Optimierung beschäftigt, sind meist sehr schwierig (NP-schwer).

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.

Bekannte Probleme

Das Problem des Handlungsreisenden
Spannbaum
Rucksackproblem
Egalisieren von variabel-gewichtigen Produkten im Prozess der Sortierung und Verpackung (Betriebswirtschaft)
Behälterproblem (Bin-Packing)

Literatur

William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver: Combinatorial Optimization. 1. Auflage. John Wiley & Sons, 1997, ISBN 047155894X.
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger: A compendium of NP optimization problems.
Bernhard Korte, Jens Vygen: Kombinatorische Optimierung: Theorie und Algorithmen. 2. Auflage. Springer Spektrum, Berlin 2012, ISBN 978-3-642-25400-0.
Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization: Algorithms and Complexity. Dover Publications Inc., 1998, ISBN 0486402584.
Eugene Lawler: Combinatorial Optimization: Networks and Matroids, Oxford University Press 1995 (zuerst 1976)
Alexander Schrijver: Combinatorial optimization – polyhedra and efficiency, 3 Bände, Springer 2003

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.