Generieren interessanter kombinatorischer Optimierungsprobleme

9

Ich unterrichte einen Kurs über Meta-Heuristik und muss interessante Beispiele für klassische kombinatorische Probleme für den Begriff Projekt generieren . Konzentrieren wir uns auf TSP. Wir beschäftigen uns mit Graphen der Dimension und größer. Ich habe natürlich versucht, ein Diagramm mit einer Kostenmatrix mit Werten aus einem zufälligen U ( 0 , 1 ) zu erstellen, und herausgefunden, dass (wie erwartet) das Histogramm für die Pfadkosten (gezeichnet durch Abtasten vieler zufälliger Pfade) hat eine sehr enge Normalverteilung ( μ ist 100, aber σ ist ungefähr 4200U(0,1)μ 100σ4). Dies bedeutet meiner Meinung nach, dass das Problem sehr einfach ist, da die meisten zufälligen Pfade unter dem Durchschnitt liegen und der Pfad mit den minimalen Kosten einem zufälligen Pfad sehr nahe kommt.

Also habe ich den folgenden Ansatz versucht: Nachdem Sie die -Matrix erzeugt haben, machen Sie einen langen zufälligen Spaziergang um den Graphen und verdoppeln oder halbieren Sie zufällig (Bernoulli mit p = 0,5 ) den Wert der Kante. Dies neigt dazu, alle Werte zu senken und schließlich Null zu erreichen. Wenn ich jedoch genau die richtige Anzahl von Schritten mache, kann ich eine Verteilung mit μ um 2 und σ um 1 erhalten .U(0,1)p=0.5μ2σ1

Meine Frage ist zunächst, ob dies überhaupt eine gute Definition für ein interessantes Problem ist. Idealerweise möchte ich eine Instanz, die sehr multimodal ist (für die gängigsten Nachbarschaftsfunktionen) und nur sehr wenige Pfade in der Nähe des Minimalwerts aufweist, sodass die meisten zufälligen Lösungen sehr weit vom Optimum entfernt sind. Die zweite Frage ist angesichts dieser Beschreibung, wie ich Instanzen mit solchen Merkmalen generieren kann.

Alejandro Piad
quelle
3
Suchen Sie nach Bibliotheken von TSP-Benchmarks, wie sie im OP untersucht wurden (z. B. Suche nach Arbeiten zu TSP von Applegate et al., ZB hier )?
Neal Young
2
Es gibt die TSPLIB mit vielen Instanzen.
AdrianN
Vielen Dank, ich habe den Link überprüft und er ist hilfreich, aber meine Frage bezieht sich auf das Generieren von Instanzen, nicht weil ich eine bestimmte Instanz lösen möchte, sondern weil ich einen Einblick in das suche, was gute kombinatorische Probleme ausmacht, einen Einblick, auf den später erweitert werden kann andere Probleme neben TSP.
Alejandro Piad
verwandter Beitrag: cstheory.stackexchange.com/questions/739/…
Neal Young
1
@Alejandro, Das versteckte Cliquenproblem könnte ein Beispiel dafür sein, wonach Sie suchen. Sie können auch nach Nachforschungen suchen, welche zufälligen Fälle von Zufriedenheit als schwierig angesehen werden.
Neal Young

Antworten:

6

Ein allgemeiner Ansatz zum Generieren härterer Instanzen lautet wie folgt:

  • Beginnen Sie mit einer zufälligen Probleminstanz.
  • Einbetten einer "versteckten Hintertür": Wählen Sie nach dem Zufallsprinzip eine gute Lösung aus (eine, die wahrscheinlich viel besser ist als jede bereits vorhandene Lösung), und ändern Sie die Probleminstanz, um diese Lösung zwangsweise in die Probleminstanz einzubetten.

U(0,1)U(0,c)c<1;; das vorhandene Gewicht reduzieren; oder ändern Sie die vorhandene Kante mit einer festen Wahrscheinlichkeit). Dieses Anpassungsverfahren stellt sicher, dass die optimale Lösung mit hoher Wahrscheinlichkeit die von Ihnen ausgewählte Spezialtour ist. Wenn Sie Glück haben und eine vernünftige Einbettung auswählen, ist es auch nicht so einfach zu erkennen, wo Sie die spezielle Lösung versteckt haben.

Dieser Ansatz leitet sich aus allgemeinen Ideen in der Kryptographie ab, bei denen wir Einwegprobleme für Falltüren erstellen möchten: Wenn das Problem ohne Kenntnis der geheimen Falltür schwer zu lösen ist, aber mit Kenntnis der geheimen Falltür, wird das Problem sehr einfach. Es gab viele Versuche, geheime Falltüren in eine Vielzahl von schwierigen Problemen einzubetten (wobei die Härte des Problems auch nach dem Hinzufügen der Falltür erhalten bleibt), mit gemischtem Erfolg. Dieser allgemeine Ansatz scheint jedoch für Ihre Zwecke praktikabel zu sein.

Die daraus resultierenden Problemfälle mögen schwierig sein , aber werden sie aus praktischer Sicht interessant sein ? Ich weiß es nicht. Schlägt mich. Sie sehen für mich ziemlich künstlich aus, aber was weiß ich?

Wenn Ihr primäres Ziel darin besteht, Probleminstanzen auszuwählen, die praktisch relevant und repräsentativ für reale TSP-Anwendungen sind, wäre mein Vorschlag ein völlig anderer Ansatz. Beginnen Sie stattdessen mit der Untersuchung realer TSP-Anwendungen, suchen Sie dann nach repräsentativen Instanzen dieser Probleme und konvertieren Sie sie in die entsprechende TSP-Probleminstanz. Sie arbeiten also mit Probleminstanzen, die aus einem realen Problem abgeleitet wurden.

DW
quelle
Ich mag diesen Ansatz sehr, bin in der Tat sehr nahe an dem, was ich mir ausgedacht habe, und scheint ziemlich anpassungsfähig an verschiedene Probleme zu sein. Meine anfängliche Motivation bestand darin, Testprobleme für Schüler zu machen, obwohl ich die Probleme mit dem richtigen Wort verstehe, aber mich für diese eher künstliche Situation (den Versuch, Algorithmen für Schüler zu bewerten) gut unterstützt. In jedem Fall werde ich versuchen, es auch an meine Forschungsbedürfnisse anzupassen, aber das erfordert, wie Sie sagen, einen genaueren Blick, um festzustellen, ob die so erstellten Instanzen repräsentativ genug sind. Vielen Dank, du hast meine +1 und Akzeptanz bekommen.
Alejandro Piad
3

Ein Ansatz, der Ihnen häufig eine hohe Kontrolle über die Art der Lösungen gibt, ist die Umstellung von einem vollständigen NP-Problem auf ein anderes. Jetzt definieren Sie "interessant" in Ihrer Frage auf statistische Weise, aber ein anderer guter Ansatz besteht darin, klassische Probleme aus dem Feld zu verwenden. Mein Favorit ist Factoring / SAT. Es ist trivial, entweder "glatte" Zahlen mit vielen Faktoren oder Primzahlen mit nur zwei "Faktoren" (einer und der Primzahl) zu finden. Erstellen Sie die SAT-Instanz, um das Factoring zu lösen, und die Lösungen sind die Faktoren (tatsächlich Permutationen von Faktoren, aber auch, die nicht schwer im Voraus zu zählen sind).

Bei diesem Ansatz gibt es eine natürliche Definition von "interessant" - harte Instanzen, die nicht in P-Zeit gelöst werden können. und dieser Ansatz erzeugt garantiert harte Instanzen für das Faktorisieren nicht glatter Zahlen, andernfalls würde er eine der offensten Fragen in der Komplexitätstheorie lösen, dh die Härte des Faktorisierens .

Konvertieren Sie dann möglicherweise zu Ihrem Problem, in diesem Fall TSP. Um diese Antwort auszufüllen, wäre es schön, eine direkte SAT-zu-TSP-Konvertierung zu haben. Ich denke, sie sind da draußen, aber ich kenne sie nicht. Hier sind jedoch einige Hinweise zum Faktorisieren auf SAT in dieser Frage: Reduzieren des Problems der ganzzahligen Faktorisierung auf ein NP-vollständiges Problem

Wenn Sie Factoring nicht mögen, ist es aus verschiedenen Gründen möglicherweise immer noch vorzuziehen, die Instanzen zuerst in SAT zu erstellen. Sie könnten mit zufälligen SAT-Instanzen beginnen, die so eingestellt sind, dass sie im leicht-schwer-leicht-Übergangspunkt usw. zentriert sind. oder Sie können mit DIMACS- Hard-Instanzen arbeiten, die von der Community generiert wurden. oder erstellen Sie andere logische "Programme" in SAT.

vzn
quelle
1
Ich mag den Konvertierungsansatz, obwohl Sie keine weiteren Links speziell zu TSP bereitstellen, aber trotzdem danke für die Idee, ich werde ihn genauer untersuchen. Du hast meine +1.
Alejandro Piad
1
@alejandro thx ok hier ist ein Link dazu. siehe zB ab Folie 28 hier [Grundschulklasse!], CMSC 451: SAT, Färbung, Hamilton-Zyklus, TSP Folien Von: Carl Kingsford . Konvertieren von SAT → Hamilton-Zyklus (TSP). Es kann effizientere (weniger Overhead-) Konvertierungsansätze oder andere maßgeschneiderte Aspekte in der Literatur geben, wenn dies gewünscht wird. Ich hoffe, mehr von Ihrer Arbeit zu hören, vielleicht antworten Sie hier oder auf meinem Blog, wenn Sie
möchten
1
Ich habe das PDF überprüft, sehr hoch, aber verständlich genug. Obwohl ich mit der @ DW-Antwort vorerst das bekommen habe, was ich brauche, scheint mir Ihr Ansatz sehr interessant zu sein. Ich muss es selbst versuchen. Ich hatte die Reduzierung zuvor gesehen (in einem Komplexitätsstudiengang), aber nicht über eine tatsächliche Implementierung speziell für die Erstellung harter Instanzen nachgedacht. Ich habe ein langfristiges Interesse an Optimierung und Metaheuristik, und einer meiner Interessenbereiche besteht darin, interessante Benchmark-Probleme zu schaffen. Übrigens, ich habe gerade Ihr Blog überprüft und werde auf jeden Fall wiederkommen !!!
Alejandro Piad