Kombinatorische Optimierung

A Minimum Spanning Tree eines gewichteten Planare Graph. Das Finden eines minimalen Spannungsbaums ist ein häufiges Problem mit einer kombinatorischen Optimierung.

Kombinatorische Optimierung ist ein Unterfeld von Mathematische Optimierung Das besteht darin, ein optimales Objekt von a zu finden endliche Menge von Objekten,^[1] wo der Satz von realisierbare Lösungen ist diskret oder kann auf einen diskreten Satz reduziert werden. Typische kombinatorische Optimierungsprobleme sind die Problem mit reisenden Verkäufern ("TSP"), die minimales Spannungsbaumproblem ("MST") und die Rucksackproblem. In vielen solchen Problemen, wie die zuvor erwähnten, erschöpfende Suche ist nicht nachvollziehbar, und daher müssen spezielle Algorithmen, die schnell große Teile des Suchraums oder Annäherungsalgorithmen ausschließen, stattdessen zurückgegriffen werden.

Die kombinatorische Optimierung hängt mit dem Zusammenhang mit Unternehmensforschung, Algorithmustheorie, und Computerkomplexitätstheorie. Es verfügt über wichtige Anwendungen in mehreren Bereichen, einschließlich künstliche Intelligenz, maschinelles Lernen, Auktionstheorie, Softwareentwicklung, angewandte Mathematik und Theoretische Informatik.

Einige Forschungsliteratur^[2] überlegt Diskrete Optimierung bestehen aus Ganzzahlprogrammierung zusammen mit kombinatorischer Optimierung (was wiederum aus besteht aus Optimierungsprobleme umgehen mit Grafikstrukturen), obwohl all diese Themen eine eng miteinander verflochtene Forschungsliteratur haben. Es besteht häufig die Bestimmung der Art und Weise, wie Sie Ressourcen, die verwendet werden, um Lösungen für mathematische Probleme zu finden, effizient zugewiesen.^{[Klarstellung erforderlich]}

Anwendungen

Anwendungen der kombinatorischen Optimierung umfassen, sind jedoch nicht beschränkt auf:

Logistik^[3]
Lieferkette Optimierung^[4]
Entwicklung des besten Fluggesellschaften von Speichen und Zielen
Entscheidung, welche Taxis in einer Flotte zur Route, um Tarife abzuholen
Bestimmung der optimalen Möglichkeit, Pakete zu liefern
Menschen optimal Jobs zuweisen
Entwerfen von Wasserverteilungsnetzwerken
Erdkunde Probleme (z. Reservoir Fließraten)^[5]

Methoden

Es gibt eine große Menge an Literatur zu Polynom-Zeit-Algorithmen für bestimmte spezielle Klassen diskreter Optimierung. Eine beträchtliche Menge davon ist durch die Theorie von einheitlich Lineares Programmieren. Einige Beispiele für kombinatorische Optimierungsprobleme, die in diesem Rahmen behandelt werden, sind kürzeste Wege und kürzeste Pfadbäume, Flüsse und Zirkulationen, Bäume überspannen, Matching, und Matroid Probleme.

Zum NP-Complete Diskrete Optimierungsprobleme, aktuelle Forschungsliteratur umfasst die folgenden Themen:

Polynom-Zeit genau lösbare Sonderfälle des jeweiligen Problems (z. Fix-Parameter-Traktable Probleme)
Algorithmen, die in "zufälligen" Instanzen gut abschneiden (z. B. für die Problem mit reisenden Verkäufern)
Näherungsalgorithmen Dieser Lauf in Polynomzeit und findet eine Lösung, die nahezu optimal ist
Lösen realer Instanzen, die in der Praxis entstehen und nicht unbedingt das schlechteste Verhalten von in NP-Complete-Problemen aufweisen (z. B. reale TSP-Instanzen mit Zehntausenden von Knoten^[6]).

Kombinatorische Optimierungsprobleme können als die Suche nach dem besten Element einiger diskreter Elemente angesehen werden. im Prinzip jeder Art von Suchalgorithmus oder metaheuristisch kann verwendet werden, um sie zu lösen. Vielleicht die universell anwendbarsten^{[Wieselwörter]} Ansätze sind Zweig und gebunden (Ein exakter Algorithmus, der zu jedem Zeitpunkt gestoppt werden kann, um als Heuristik zu dienen), Zweig und Schnitt (verwendet lineare Optimierung, um Grenzen zu generieren), Dynamische Programmierung (eine rekursive Lösungskonstruktion mit begrenztem Suchfenster) und Tabu -Suche (Ein gieriger Austauschalgorithmus). Generische Suchalgorithmen finden jedoch nicht garantiert zuerst eine optimale Lösung, und es wird auch nicht garantiert, dass sie (in Polynomzeit) garantiert laufen. Da einige diskrete Optimierungsprobleme sind NP-Complete, wie das Problem des reisenden Verkäufers (Entscheidung),^[7] Dies wird erwartet, es sei denn P = np.

Formale Definition

Formal ein kombinatorisches Optimierungsproblem ${\ displayStyle a}$ ist ein Vierfach ${\ displayStyle (i, f, m, g)}$ , wo

${\ displayStyle i}$ ist ein einstellen von Instanzen;
eine Instanz gegeben ${\ displayStyle x \ in i}$ , ${\ displayStyle f (x)}$ ist der endliche Satz von realisierbaren Lösungen;
eine Instanz gegeben ${\ displayStyle x}$ und eine realisierbare Lösung ${\ displayStyle y}$ von ${\ displayStyle x}$ , ${\ displayStyle m (x, y)}$ bezeichnet die messen von ${\ displayStyle y}$ , was normalerweise a ist positiv real.
${\ displayStyle g}$ ist die Zielfunktion und ist entweder ${\ displayStyle \ min}$ oder ${\ displayStyle \ max}$ .

Das Ziel ist es dann, für einen Fall zu finden ${\ displayStyle x}$ ein optimale Lösungdas heißt eine praktikable Lösung ${\ displayStyle y}$ mit

{\ displayStyle m (x, y) = g \ {m (x, y ') \ mid y' \ in f (x) \}.}

Für jedes kombinatorische Optimierungsproblem gibt es eine entsprechende Entscheidungsproblem Das fragt, ob es eine praktikable Lösung für eine bestimmte Maßnahme gibt ${\ displayStyle m_ {0}}$ . Zum Beispiel, wenn es a gibt Graph ${\ displayStyle g}$ das enthält Eckpunkte ${\ displayStyle u}$ und ${\ displayStyle v}$ Ein Optimierungsproblem könnte sein "einen Weg finden aus ${\ displayStyle u}$ zu ${\ displayStyle v}$ Das verwendet die wenigsten Kanten ". Dieses Problem könnte eine Antwort auf beispielsweise 4 haben. Ein entsprechendes Entscheidungsproblem wäre" Es gibt einen Weg von ${\ displayStyle u}$ zu ${\ displayStyle v}$ Das verwendet 10 oder weniger Kanten? "Dieses Problem kann mit einem einfachen" Ja "oder" Nein "beantwortet werden.

Das Feld von Näherungsalgorithmen befasst sich mit Algorithmen, um nahezu optimale Lösungen für harte Probleme zu finden. Die übliche Entscheidungsversion ist dann eine unzureichende Definition des Problems, da sie nur akzeptable Lösungen spezifiziert. Obwohl wir geeignete Entscheidungsprobleme einführen könnten, wird das Problem dann als Optimierungsproblem natürlicher charakterisiert.^[8]

NP -Optimierungsproblem

Ein NP-Optimierungsproblem (NPO) ist ein kombinatorisches Optimierungsproblem mit den folgenden zusätzlichen Bedingungen.^[9] Beachten Sie, dass das unten verwies Polynome sind Funktionen der Größe der Eingänge der jeweiligen Funktionen, nicht der Größe einiger impliziter Eingabeinstanzen.

die Größe jeder realisierbaren Lösung ${\ displayStyle y \ in f (x)}$ ist polynomial begrenzt in der Größe der angegebenen Instanz ${\ displayStyle x}$ ,
Die Sprachen ${\ displaystyle \ {\, x \, \ Mid \, x \ in i \, \}}$ und ${\ displayStyle \ {\, (x, y) \, \ mid \, y \ in f (x) \, \}}$ kann sein anerkannt in Polynomzeit, und
${\ displayStyle m}$ ist Polynomzeit berechnet.

Dies impliziert, dass das entsprechende Entscheidungsproblem in liegt Np. In der Informatik haben interessante Optimierungsprobleme normalerweise die oben genannten Eigenschaften und sind daher NPO -Probleme. Ein Problem wird zusätzlich als P-Optimisierung (PO) -Problem bezeichnet, wenn es einen Algorithmus gibt, der optimale Lösungen in der Polynomzeit findet. Oft ist man beim Umgang mit der Klasse NPO an Optimierungsproblemen interessiert, für die die Entscheidungsversionen sind NP-Complete. Beachten Sie, dass Härtebeziehungen immer in Bezug auf eine Reduzierung der Reduzierung sind. Aufgrund des Zusammenhangs zwischen Approximationsalgorithmen und Rechenoptimierungsproblemen sind Reduktionen, die die Approximation in gewisser Hinsicht beibehalten Turing und KARP -Reduktionen. Ein Beispiel für eine solche Reduzierung wäre L-Reduktion. Aus diesem Grund werden Optimierungsprobleme mit NP-Complete-Entscheidungsversionen nicht unbedingt als NPO-Complete bezeichnet.^[10]

NPO ist gemäß ihrer Annäherung in die folgenden Unterklassen unterteilt:^[9]

Npo (i): Gleich Fptas. Enthält die Rucksackproblem.
NPO (ii): Gleich PTAs. Enthält die Makespan Planungsproblem.
NPO (III):: Die Klasse der NPO-Probleme, die Polynomzeitalgorithmen aufweisen, die lösungen höchstens mit Kosten berechnet c mal die optimalen Kosten (für Minimierungsprobleme) oder mindestens die Kosten ${\ displayStyle 1/c}$ der optimalen Kosten (für Maximierungsprobleme). Im Hromkovič's Buch^[die?], aus dieser Klasse ausgeschlossen sind alle NPO (ii) -probleme speichern, wenn p = np. Ohne Ausschluss gleich APX. Enthält Max-sa und Metrik TSP.
NPO (iv):: Die Klasse der NPO-Probleme mit Polynomzeitalgorithmen, die die optimale Lösung durch ein Verhältnis näherten, das in einem Logarithmus der Größe des Eingangs Polynom ist. In Hromkovičs Buch sind alle NPO (III) -Probleme von dieser Klasse ausgeschlossen, es sei denn, P = NP. Enthält die Deckung festlegen Problem.
NPO (v):: Die Klasse der NPO-Probleme mit Polynom-Zeit-Algorithmen, die die optimale Lösung durch ein Verhältnis näherten, das durch eine gewisse Funktion auf n begrenzt ist. In Hromkovics Buch sind alle NPO (IV) -Probleme aus dieser Klasse ausgeschlossen, es sei denn, P = NP. Enthält die TSP und Clique Problem.

Ein NPO -Problem heißt polynomisch begrenzt (PB) Wenn, für jeden Fall ${\ displayStyle x}$ Und für jede Lösung ${\ displayStyle y \ in f (x)}$ , die Maßnahme ${\ displayStyle m (x, y)}$ wird durch eine Polynomfunktion der Größe von begrenzt ${\ displayStyle x}$ . Die Klasse NPOPB ist die Klasse von NPO-Problemen, die polynomisch gebunden sind.

Spezifische Probleme

Eine optimale Reiseverkäufer -Tour durch Deutschland15 größte Städte. Es ist der kürzeste unter den 43.589.145.600^[11] Mögliche Touren, die jede Stadt genau einmal besuchen.

Siehe auch

Einschränkungs -zusammengesetzter Diagramm

Anmerkungen

^ Schrijver 2003, p. 1.
^ Diskrete Optimierung. Elsevier. Abgerufen 2009-06-08.
^ 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.
^ Eskandarpour, Majid; Dejax, Pierre; Miemczyk, Joe; Péton, Olivier (2015). "Nachhaltiges Lieferkettennetzwerkdesign: Eine optimierungsorientierte Überprüfung" (PDF). Omega. 54: 11–32. doi:10.1016/j.omega.2015.01.006.
^ Hobé, Alex; Vogler, Daniel; Seybold, Martin P.; Ebigbo, Anozie; Settgast, Randolph R.; Saar, Martin O. (2018). "Schätzung der Flüssigkeitsdurchflussraten durch Bruchnetzwerke mit kombinatorischer Optimierung". Fortschritte in den Wasserressourcen. 122: 85–97. Arxiv:1801.08321. Bibcode:2018Adwr..122 ... 85H. doi:10.1016/j.advwatres.2018.10.002. S2CID 119476042.
^ Cook 2016.
^ "Approximation-TSP" (PDF).
^ Ausiello, Giorgio; et al. (2003), Komplexität und Näherung (Korrigiert.), Springer, ISBN 978-3-540-65431-5
^ ^a ^b Hromkovic, Juraj (2002), Algorithmik für harte Probleme, Texte in theoretischer Informatik (2. Aufl.), Springer, ISBN 978-3-540-44134-2
^ Kann, Viggo (1992), Bei der Annäherung an NP-Complete-Optimierungsprobleme, Royal Institute of Technology, Schweden, ISBN 91-7170-082-x
^ Nehmen Sie eine Stadt und nehmen Sie alle möglichen Bestellungen der anderen 14 Städte auf. Dann dividieren Sie durch zwei, weil es in der Zeit, in die sie sich in der Zeit befinden, keine Rolle spielen: 14!/2 = 43.589.145.600.

Verweise

Beasley, J. E. "Ganzzahlprogrammierung" (Vorlesungsnotizen).

Cook, William J.; Cunningham, William H.; Pulleyblank, William R.; Schrijver, Alexander (1997). Kombinatorische Optimierung. Wiley. ISBN 0-471-55894-x.

Cook, William (2016). "Optimale TSP -Touren". Universität von Waterloo. (Informationen zu den größten TSP -Instanzen, die bisher gelöst wurden.)

Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (Hrsg.). "Ein Kompendium von NP -Optimierungsproblemen". (Dies ist ein kontinuierlich aktualisierter Katalog der Annäherungsergebnisse für NP -Optimierungsprobleme.)

Das, Arnab; Chakrabarti, Bikas K., eds. (2005). Quantenglühungen und verwandte Optimierungsmethoden. Vorlesungsnotizen in der Physik. Vol. 679. Springer. Bibcode:2005qnro.book ..... d.

Das, Arnab; Chakrabarti, Bikas K (2008). "Kolloquium: Quantenglühen und analoge Quantenberechnung". Rev. Mod. Phys. 80 (3): 1061. Arxiv:0801.2193. Bibcode:2008rvmp ... 80.1061d. Citeseerx 10.1.1.563.9990. doi:10.1103/revmodphys.80.1061. S2CID 14255125.

Lawler, Eugene (2001). Kombinatorische Optimierung: Netzwerke und Matroide. Dover. ISBN 0-486-41453-1.

Lee, Jon (2004). Ein erster Kurs in kombinatorischer Optimierung. Cambridge University Press. ISBN 0-521-01012-8.

Papadimitriou, Christos H.; Steiglitz, Kenneth (Juli 1998). Kombinatorische Optimierung: Algorithmen und Komplexität. Dover. ISBN 0-486-40258-4.

Schrijver, Alexander (2003). Kombinatorische Optimierung: Polyeder und Effizienz. Algorithmen und Kombinatorik. Vol. 24. Springer. ISBN 9783540443896.

Schrijver, Alexander (2005). "Über die Geschichte der kombinatorischen Optimierung (bis 1960)" (PDF). Im Aardal, K.; Nemhauser, G. L.; Weismantel, R. (Hrsg.). Handbuch der diskreten Optimierung. Elsevier. S. 1–68.

Schrijver, Alexander (1. Februar 2006). Ein Kurs in kombinatorischer Optimierung (PDF).

Sierksma, Gerard; Ghosh, Diptesh (2010). Netzwerke in Aktion; Text- und Computerübungen in der Netzwerkoptimierung. Springer. ISBN 978-1-4419-5512-8.

Gerard Sierksma; Yori Zwols (2015). Lineare und ganzzahlige Optimierung: Theorie und Praxis. CRC Press. ISBN 978-1-498-71016-9.

Pintea, C-M. (2014). Fortschritte beim bio-inspirierten Computing für das Problem des kombinatorischen Optimierungsproblems. Intelligente Systemreferenzbibliothek. Springer. ISBN 978-3-642-40178-7.

Externe Links

[1] Schrijver 2003, p. 1.

[2] Diskrete Optimierung. Elsevier. Abgerufen 2009-06-08.

[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 Lieferkettennetzwerkdesign: 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üssigkeitsdurchflussraten durch Bruchnetzwerke mit kombinatorischer Optimierung". Fortschritte in den Wasserressourcen. 122: 85–97. Arxiv:1801.08321. Bibcode:2018Adwr..122 ... 85H. doi:10.1016/j.advwatres.2018.10.002. S2CID 119476042.

[6] Cook 2016.

[7] "Approximation-TSP" (PDF).

[Ausiello03-8] Ausiello, Giorgio; et al. (2003), Komplexität und Näherung (Korrigiert.), Springer, ISBN 978-3-540-65431-5

[Hromkovic02-9] Hromkovic, Juraj (2002), Algorithmik für harte Probleme, Texte in theoretischer Informatik (2. Aufl.), Springer, ISBN 978-3-540-44134-2

[Kann92-10] Kann, Viggo (1992), Bei der Annäherung an NP-Complete-Optimierungsprobleme, Royal Institute of Technology, Schweden, ISBN 91-7170-082-x

[11] Nehmen Sie eine Stadt und nehmen Sie alle möglichen Bestellungen der anderen 14 Städte auf. Dann dividieren Sie durch zwei, weil es in der Zeit, in die sie sich in der Zeit befinden, keine Rolle spielen: 14!/2 = 43.589.145.600.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]