Die Struktur pathologischer Instanzen für Simplex-Algorithmen

17

Soweit ich weiß, haben alle bekannten deterministischen Pivot-Regeln für Simplex-Algorithmen bestimmte Eingaben, für die der Algorithmus exponentielle Zeit (oder zumindest kein Polynom) benötigt, um das Optimum zu finden. Nennen wir diese Instanzen "pathologisch", da der Simplex-Algorithmus normalerweise (dh bei den meisten Eingaben) schnell beendet wird. Ich erinnere mich aus meinem Mathematikkurs, dass die Standardbeispiele für pathologische Instanzen für bestimmte Regeln sehr strukturiert waren. Meine allgemeine Frage ist, ob dies ein Artefakt der spezifischen Beispiele oder ein Merkmal von pathologischen Fällen im Allgemeinen ist.

Ergebnisse wie die geglättete Analyse und der Polynom-Zeit-Algorithmus , der sie erweitert, beruhen auf der Störung der Eingabe - was darauf hindeutet, dass die pathologischen Beispiele sehr speziell sind. Daher scheint die Intuition, dass die pathologischen Instanzen stark strukturiert sind, nicht so weit hergeholt.

Hat jemand spezielle Einsichten dazu? Oder einige Verweise auf bestehende Arbeiten? Ich war mir nicht sicher, was ich unter "strukturiert" verstehe, um zu versuchen, so umfassend wie möglich zu sein, aber Vorschläge, wie man "strukturiert" besser definieren kann, wären auch nützlich. Alle Ratschläge oder Referenzen sind sehr dankbar!

cc.complexity-theory reference-request linear-programming simplex Artem Kaznatcheev
quelle
1
Ich bin mir nicht sicher, ob ich Ihre Frage verstanden habe, aber das Gegenteil von "strukturiert" scheint "zufällig" zu sein. Wenn ein Simplex-Algorithmus mit einer bestimmten Pivotierungsregel bereits für zufällige Instanzen ineffizient ist (mit hoher Wahrscheinlichkeit, gemäß einer natürlichen Verteilung) ), wahrscheinlich sind die Leute nicht daran interessiert, ein schlechtes Beispiel für diese bestimmte Schwenkregel zu konstruieren, da diese bestimmte Schwenkregel meistens unbrauchbar ist.
Tsuyoshi Ito
Fragen Sie sich: Wie groß ist die Wahrscheinlichkeit, dass eine zufällige Instanz für eine feste Pivot-Regel pathologisch ist? dh die Durchschnittsanalyse des Algorithmus?
Kaveh
Ich frage nicht nach der Wahrscheinlichkeit, dass eine zufällige Instanz pathologisch ist. Ich frage wirklich nur, ob pathologische Instanzen eine besondere Struktur haben. Wie Tsuyoshi betont, sollte ich es wirklich auf "gute" Pivot-Regeln beschränken, was auch immer das bedeutet. Irgendwelche Vorschläge, wie man dies klarer machen kann?
Artem Kaznatcheev
4
Ich glaube, dass viele pathologische Fälle Würfel sind, deren Seiten böswillig gestört wurden, aber ich habe mir das schon lange genug angesehen, damit mein Gedächtnis völlig falsch sein könnte.
Peter Shor

Antworten:

16

Amenta und Ziegler haben bewiesen, dass alle derzeit bekannten Konstruktionen von Exponential-Zeit-Instanzen für Simplex einer bestimmten Struktur folgen, die sie "deformierte Produkte" nennen:

Verformte Produkte und maximale Schatten von Polytopen von Amenta und Ziegler

Ich glaube jedoch nicht, dass es Grund zur Annahme gibt, dass alle schlechten Instanzen für Simplex diese Struktur haben. Dies ist wahrscheinlich nur ein Artefakt des Forschungsprozesses:

  1. Klee und Minty fanden das erste Exponentialzeit-Beispiel.
  2. Andere Forscher untersuchten die Techniken von Klee und Minty und erweiterten sie auf andere Pivot-Regeln. Sie gingen natürlich den Weg des geringsten Widerstands und folgten dem Klee-Minty-Würfel so genau wie möglich.
  3. Sobald jemand ein schlechtes Beispiel für eine Pivot-Regel findet, gibt es keinen Anreiz mehr, nach mehr zu suchen. Infolgedessen haben alle uns bekannten schlechten Beispiele eine ähnliche Struktur.
Ian
quelle
1
Ich liebe immer soziologische Antworten auf mathematische Fragen;). Danke für die Antwort! Ich werde AmentaZiegler1996 näher betrachten. Kennen Sie die Ergebnisse seit '96, die bei deformierten Produkten gut funktionieren? Ich fand eine Arbeit von Norman Zadeh (1980 und 2009), die sogar in der 80er-Version [ stanford.edu/group/SOL/reports/OR-80-27.pdf ] die Überwindung der deformierten Produktkonstruktion erwähnt.
Artem Kaznatcheev
"Deformed Product" war eindeutig ein intuitiver Begriff in der LP-Community, bevor Nina und Gunter ihn formalisierten. Das ist sicherlich eine genaue Beschreibung der Klee-Minty-Würfel!
Jeffs
1
Siehe auch Matoušeks und Szabos exponentielle untere Schranken für RANDOM EDGE auf "abstrakten Würfeln", die als kombinatorische
Verwandten