Kombinatorische Optimierung – Wikipedia

Posted on by
before-content-x4

Kombinatorische Optimierung ist ein Teilgebiet der mathematischen Optimierung, das sich auf Operations Research, Algorithmus-Theorie und rechnerische Komplexitätstheorie bezieht. Es hat wichtige Anwendungen in verschiedenen Bereichen, einschließlich künstlicher Intelligenz, maschinellem Lernen, Auktionstheorie, Software-Engineering, angewandter Mathematik und theoretischer Informatik.

after-content-x4

Kombinatorische Optimierung ist ein Thema, das darin besteht, aus einer endlichen Menge von Objekten ein optimales Objekt zu finden.[1] Bei vielen dieser Probleme ist eine erschöpfende Suche nicht nachvollziehbar. Es befasst sich mit den Optimierungsproblemen, bei denen die Menge der möglichen Lösungen diskret ist oder auf diskret reduziert werden kann und bei denen das Ziel darin besteht, die beste Lösung zu finden. Typische Probleme sind das Problem des Handlungsreisenden (“TSP”), das Problem des minimalen Spanning Tree (“MST”) und das Rucksackproblem.

Einige Forschungsliteratur[2] betrachtet diskrete Optimierung als Ganzzahlprogrammierung zusammen mit kombinatorischer Optimierung (die sich wiederum aus Optimierungsproblemen bei Graphstrukturen zusammensetzt), obwohl alle diese Themen eng miteinander verknüpfte Forschungsliteratur aufweisen. Oft muss ermittelt werden, wie Ressourcen effizient zugewiesen werden können, um Lösungen für mathematische Probleme zu finden.

Anwendungen[edit]

Anwendungen zur kombinatorischen Optimierung umfassen, sind aber nicht beschränkt auf:

  • Logistik[3]
  • Optimierung der Lieferkette[4]
  • Entwicklung des besten Airline-Netzwerks von Speichen und Zielen
  • Entscheiden, welche Taxis in einer Flotte zum Abholen von Tarifen verwendet werden sollen
  • Bestimmen der optimalen Art der Paketzustellung
  • Erarbeitung der besten Zuordnung von Arbeitsplätzen zu Menschen
  • Gestaltung von Wasserverteilungsnetzen
  • Geowissenschaftliche Probleme (z. B. Durchflussraten des Reservoirs)[5]

Methoden[edit]

Es gibt eine große Menge an Literatur zu Polynom-Zeit-Algorithmen für bestimmte spezielle Klassen der diskreten Optimierung, von denen eine beträchtliche Menge durch die Theorie der linearen Programmierung vereinheitlicht wird. Einige Beispiele für kombinatorische Optimierungsprobleme, die in dieses Framework fallen, sind kürzeste Pfade und Bäume mit kürzesten Pfaden, Flüsse und Zirkulationen, Spannbäume, Matching- und Matroid-Probleme.

Für NP-vollständige diskrete Optimierungsprobleme umfasst die aktuelle Forschungsliteratur die folgenden Themen:

  • Polynomzeit genau lösbare Sonderfälle des vorliegenden Problems (zB siehe Tractable mit festen Parametern)
  • Algorithmen, die auf “zufälligen” Instanzen gut funktionieren (z. B. für TSP)
  • Approximationsalgorithmen, die in Polynomzeit laufen und eine Lösung finden, die “nahe” am Optimum liegt
  • Lösen von realen Instanzen, die in der Praxis auftreten und nicht unbedingt das Worst-Case-Verhalten aufweisen, das NP-vollständigen Problemen inhärent ist (z. B. TSP-Instanzen mit Zehntausenden von Knoten[6]).

Kombinatorische Optimierungsprobleme können als Suche nach dem besten Element einer Reihe diskreter Elemente angesehen werden. Daher kann im Prinzip jede Art von Suchalgorithmus oder Metaheuristik verwendet werden, um sie zu lösen. Die vielleicht universellsten Ansätze sind Branch-and-Bound (ein exakter Algorithmus, der zu jedem Zeitpunkt gestoppt werden kann, um als Heuristik zu dienen), Branch-and-Cut (verwendet lineare Optimierung, um Grenzen zu generieren) und dynamische Programmierung (rekursiv) Lösungskonstruktion mit eingeschränktem Suchfenster) und Tabu-Suche (ein gieriger Swap-Algorithmus). Es wird jedoch nicht garantiert, dass generische Suchalgorithmen zuerst eine optimale Lösung finden, und es wird auch nicht garantiert, dass sie schnell ausgeführt werden (in Polynomzeit). Da einige diskrete Optimierungsprobleme NP-vollständig sind, wie beispielsweise das Problem des Handlungsreisenden[citation needed]Dies wird erwartet, es sei denn, P = NP.

after-content-x4

Formale Definition[edit]

Formal ein kombinatorisches Optimierungsproblem

EIN{ displaystyle A}

ist ein Vierfacher[citation needed]

(ich,f,m,G){ displaystyle (I, f, m, g)}

, wo

Das Ziel ist es dann, zum Beispiel zu finden

x{ displaystyle x}

ein optimale Lösungdas heißt, eine praktikable Lösung

y{ displaystyle y}

mit

Für jedes kombinatorische Optimierungsproblem gibt es ein entsprechendes Entscheidungsproblem, das fragt, ob es für eine bestimmte Maßnahme eine praktikable Lösung gibt

m0{ displaystyle m_ {0}}

. Zum Beispiel, wenn es ein Diagramm gibt

G{ displaystyle G}

welches Eckpunkte enthält

u{ displaystyle u}

und

v{ displaystyle v}

Ein Optimierungsproblem könnte darin bestehen, “einen Pfad zu finden von

u{ displaystyle u}

zu

v{ displaystyle v}

das verwendet die wenigsten Kanten “. Dieses Problem könnte eine Antwort von beispielsweise 4 haben. Ein entsprechendes Entscheidungsproblem wäre” gibt es einen Pfad von

u{ displaystyle u}

zu

v{ displaystyle v}

das verwendet 10 oder weniger Kanten? “Dieses Problem kann mit einem einfachen” Ja “oder” Nein “beantwortet werden.

Auf dem Gebiet der Approximationsalgorithmen sollen Algorithmen nahezu optimale Lösungen für schwierige Probleme finden. Die übliche Entscheidungsversion ist dann eine unzureichende Definition des Problems, da nur akzeptable Lösungen angegeben werden. Obwohl wir geeignete Entscheidungsprobleme einführen könnten, wird das Problem natürlicher als Optimierungsproblem charakterisiert.[7]

NP-Optimierungsproblem[edit]

Ein NP-Optimierungsproblem (NPO) ist ein kombinatorisches Optimierungsproblem mit den folgenden zusätzlichen Bedingungen.[8] Beachten Sie, dass die unten angegebenen Polynome Funktionen der Größe der Eingaben der jeweiligen Funktionen sind, nicht der Größe einiger impliziter Mengen von Eingabeinstanzen.

  • die Größe jeder möglichen Lösung
  • Die Sprachen

Dies impliziert, dass das entsprechende Entscheidungsproblem in NP liegt. In der Informatik haben interessante Optimierungsprobleme normalerweise die oben genannten Eigenschaften und sind daher NPO-Probleme. Ein Problem wird zusätzlich als P-Optimierungsproblem (PO-Problem) bezeichnet, wenn es einen Algorithmus gibt, der in Polynomzeit optimale Lösungen findet. Wenn es um die Klasse NPO geht, interessiert man sich oft für Optimierungsprobleme, für die die Entscheidungsversionen NP-vollständig sind. Beachten Sie, dass sich die Härteverhältnisse immer auf eine gewisse Verringerung beziehen. Aufgrund des Zusammenhangs zwischen Approximationsalgorithmen und Berechnungsoptimierungsproblemen werden Reduktionen, die die Approximation in gewisser Hinsicht beibehalten, für dieses Thema gegenüber den üblichen Turing- und Karp-Reduktionen bevorzugt. Ein Beispiel für eine solche Reduktion wäre die L-Reduktion. Aus diesem Grund werden Optimierungsprobleme mit NP-vollständigen Entscheidungsversionen nicht unbedingt als NPO-vollständig bezeichnet.[9]

NPO wird entsprechend ihrer Annäherbarkeit in die folgenden Unterklassen unterteilt:[8]

  • NPO (I): Entspricht FPTAS. Enthält das Rucksackproblem.
  • NPO (II): Entspricht PTAS. Enthält das Makespan-Planungsproblem.
  • NPO (III):: Die Klasse der NPO-Probleme mit Polynom-Zeit-Algorithmen, die höchstens kostenintensive Lösungen berechnen c mal die optimalen Kosten (für Minimierungsprobleme) oder mindestens die Kosten
  • NPO (IV):: Die Klasse der NPO-Probleme mit Polynom-Zeit-Algorithmen, die die optimale Lösung durch ein Verhältnis approximieren, das in einem Logarithmus der Größe der Eingabe polynomisch ist. In Hromkovics Buch sind alle NPO (III) -Probleme von dieser Klasse ausgeschlossen, es sei denn, P = NP. Enthält das Problem mit der Set-Abdeckung.
  • NPO (V):: Die Klasse der NPO-Probleme mit Polynom-Zeit-Algorithmen, die die optimale Lösung durch ein Verhältnis approximieren, das durch eine Funktion auf n begrenzt ist. In Hromkovics Buch sind alle NPO (IV) -Probleme von dieser Klasse ausgeschlossen, es sei denn, P = NP. Enthält die Probleme mit TSP und Max Clique.

Ein NPO-Problem wird aufgerufen polynomiell begrenzt (PB) wenn für jeden Fall

x{ displaystyle x}

und für jede Lösung

y∈f(x){ displaystyle y in f (x)}

, die Maßnahme

m(x,y){ displaystyle m (x, y)}

ist durch eine Polynomfunktion der Größe von begrenzt

x{ displaystyle x}

. Die Klasse NPOPB ist die Klasse von NPO-Problemen, die polynomiell begrenzt sind.

Spezifische Probleme[edit]

Eine optimale Reise durch die 15 größten Städte Deutschlands. Es ist das kürzeste unter 43.589.145.600[10] mögliche Touren, die jede Stadt genau einmal besuchen.

Siehe auch[edit]

  1. ^ Schrijver 2003, p. 1.
  2. ^ Diskrete Optimierung. Elsevier. Abgerufen 08.06.2009.
  3. ^ Sbihi, Abdelkader; Eglese, Richard W. (2007). “Kombinatorische Optimierung und grüne Logistik” (PDF). 4OR. 5 (2): 99–116. doi:10.1007 / s10288-007-0047-3. S2CID 207070217.
  4. ^ Eskandarpour, Majid; Dejax, Pierre; Miemczyk, Joe; Péton, Olivier (2015). “Nachhaltiges Design von Lieferkettennetzwerken: Eine optimierungsorientierte Überprüfung” (PDF). Omega. 54: 11–32. doi:10.1016 / j.omega.2015.01.006.
  5. ^ Hobé, Alex; Vogler, Daniel; Seybold, Martin P.; Ebigbo, Anozie; Settgast, Randolph R.; Saar, Martin O. (2018). “Schätzung der Flüssigkeitsströmungsraten durch Bruchnetzwerke mithilfe kombinatorischer Optimierung”. Fortschritte bei den Wasserressourcen. doi:10.1016 / j.advwatres.2018.10.002.
  6. ^ Koch 2016.
  7. ^ Ausiello, Giorgio; et al. (2003), Komplexität und Annäherung (Korrigierte Ausgabe), Springer, ISBN 978-3-540-65431-5
  8. ^ ein b Hromkovic, Juraj (2002), Algorithmen für schwierige Probleme, Texte in Theoretischer Informatik (2. Aufl.), Springer, ISBN 978-3-540-44134-2
  9. ^ Kann, Viggo (1992), Zur Annäherbarkeit von NP-vollständigen Optimierungsproblemen, Royal Institute of Technology, Schweden, ISBN 91-7170-082-X
  10. ^ Nehmen Sie eine Stadt und nehmen Sie alle möglichen Bestellungen der anderen 14 Städte entgegen. Teilen Sie dann durch zwei, denn es spielt keine Rolle, in welche Richtung sie zeitlich nacheinander kommen: 14! / 2 = 43.589.145.600.

Verweise[edit]

  • (Dies ist ein ständig aktualisierter Katalog mit Approximationsergebnissen für NP-Optimierungsprobleme.)
  • Gerard Sierksma; Yori Zwols (2015). Lineare und ganzzahlige Optimierung: Theorie und Praxis. CRC Drücken Sie. ISBN 978-1-498-71016-9.

Externe Links[edit]

after-content-x4