Hintergrund

Das Travelling Salesman Problem (TSP) fragt nach dem kürzesten Rundgang, der eine bestimmte Sammlung von Städten besucht. Für die Zwecke dieser Frage sind die Städte Punkte in der Ebene und die Abstände zwischen ihnen sind die üblichen euklidischen Abstände (auf die nächste ganze Zahl gerundet). Die Strecke muss "Hin- und Rückfahrt" sein, dh sie muss in die Ausgangsstadt zurückkehren.

Der Concorde TSP-Solver kann Instanzen des euklidischen Problems der reisenden Verkäufer genau und viel schneller lösen, als man es erwarten würde. Zum Beispiel konnte Concorde eine Instanz mit 85.900 Punkten genau lösen. Teile davon sehen so aus:

Einige TSP-Instanzen dauern jedoch zu lange, selbst für Concorde. Zum Beispiel war niemand in der Lage, diese Instanz mit 100.000 Punkten basierend auf der Mona Lisa zu lösen . (Es wird ein Preisgeld von 1.000 USD angeboten, wenn Sie es lösen können!)

Concorde steht als Quellcode oder ausführbare Datei zum Download zur Verfügung . Standardmäßig wird der integrierte LP-Löser QSopt verwendet , es können jedoch auch bessere LP-Löser wie CPLEX verwendet werden.

Die Herausforderung

Was ist die kleinste TSP-Instanz, die Sie generieren können und für deren Lösung Concorde mehr als fünf Minuten benötigt ?

Sie können ein Programm schreiben, um die Instanz auszugeben, oder eine andere Methode verwenden, die Sie möchten.

Wertung

Je weniger Punkte in der Instanz, desto besser. Die Bindungen werden durch die Dateigröße der Instanz getrennt (siehe unten).

Standardisierung

Verschiedene Computer laufen schneller oder langsamer, daher verwenden wir den NEOS-Server für Concorde als Messstandard für die Laufzeit. Sie können eine Liste von Punkten in der folgenden einfachen 2D-Koordinatenform einreichen:

#cities
x_0 y_0
x_1 y_1
.
.
.
x_n-1 y_n-1

Die Einstellungen, die unter NEOS verwendet werden sollten, sind "Concorde-Daten (xy-Listendatei, L2-Norm)", "Algorithmus: Concorde (QSopt)" und "Random Seed: Fixed".

Grundlinie

Die 1889-Punkte-Instanz rl1889.tspvon TSPLIB benötigt "Gesamtlaufzeit: 871,18 (Sekunden)", was mehr als fünf Minuten entspricht. Es sieht aus wie das:

88 Städte, 341 Sekunden Laufzeit auf NEOS

In einem kürzlich erschienenen Artikel haben wir eine Familie von schwer zu lösenden euklidischen TSP-Instanzen konstruiert. Sie können die Instanzen aus dieser Familie sowie den Code zum Generieren hier herunterladen:

http://www.or.uni-bonn.de/%7Ehougardy/HardTSPInstances.html

Die 88-Städte-Instanz dieser Familie benötigt Concorde auf dem NEOS-Server mehr als 5 Minuten. Das Lösen der 178-Städte-Instanz dieser Familie dauert bereits mehr als einen Tag.

77 Städte, 7,24 Minuten durchschnittliche Laufzeit auf NEOS

Ich bin ein bisschen spät dran an der Party, aber ich würde gerne eine 77-Node-Instanz beitragen, weruSnowflake77.

Ich habe diese Instanz erstellt, als ich zu verstehen versuchte, welche lokalen und globalen Merkmale einen Aufwärtsdruck auf die Zeitspanne ausüben, die Concorde benötigt, um die beste Untergrenze mit der Länge der kürzesten gefundenen Tour in Einklang zu bringen.

Um diese Instanz zu konstruieren, begann ich mit einem Basisgraphen (13 x 13 Quadrat) und führte dann systematisch neue Punkte ein oder übersetzte alte Punkte, wobei die Anpassungen beibehalten wurden, die die Concorde vor dem Schneiden im Durchschnitt tiefer in ihre Zweige eindringen ließen.

Die Technik ähnelt der Art und Weise, wie ein genetischer Algorithmus vorhandene Touren mutiert und kürzere Touren für die nächste Generation von Mutationen beibehält, mit der Ausnahme, dass die Grafik selbst mutiert und die schwieriger zu lösenden Grafiken beibehalten werden. Es ähnelt auch der Art und Weise, wie wir Graphen mithilfe von Relaxationen mutieren, um gute Untergrenzen zu konstruieren. Es sei denn, ich gehe den umgekehrten Weg und mutiere einen vorhandenen Graphen, um einen Graphen mit schwer zu findenden Untergrenzen zu konstruieren.

Dabei habe ich ein paar kleinere Diagramme gefunden, deren Auflösung einige Minuten in Anspruch nimmt, aber dies ist das erste kleine Diagramm, das mindestens 5 Minuten in Anspruch nimmt.

Bei 10 Testläufen unter NEOS mit dem festen Startwert und QSopt betrug die durchschnittliche Laufzeit 7,24 Minuten (434,531 Sekunden). Die Mindestlaufzeit betrug 5,6 Minuten (336,64 Sekunden). Die maximale Laufzeit betrug 8,6 Minuten (515,80 Sekunden). Es wurden keine Versuche verworfen. Vollständige Benchmark-Tabelle unten:

Benchmark-Ergebnisse über 10 Läufe:

----------------------------------
| Run | Job ID# | Total running  |
|     |         | time (seconds) |
|-----|---------|----------------|
| 1   | 7739963 | 513.44         |
| 2   | 7740009 | 336.64         |
| 3   | 7740023 | 514.25         |
| 4   | 7740029 | 447.97         |
| 5   | 7740038 | 357.10         |
| 6   | 7740072 | 447.47         |
| 7   | 7740073 | 336.19         |
| 8   | 7740075 | 515.80         |
| 9   | 7740088 | 361.26         |
| 10  | 7740091 | 515.19         |
----------------------------------

weruSnowflake77 (xy Liste, L2 Norm):

77
-700 -700
700 -700
200 0
0 200
-200 0
0 -200
0 0
-600 600
-500 600
-400 600
-300 600
-200 600
-100 600
0 600
100 600
200 600
300 600
400 600
500 600
600 600
-600 -600
-500 -600
-400 -600
-300 -600
-200 -600
-100 -600
0 -600
100 -600
200 -600
300 -600
400 -600
500 -600
600 -600
600 -500
600 -400
600 -300
600 -200
600 -100
600 0
600 100
600 200
600 300
600 400
600 500
-600 -500
-600 -400
-600 -300
-600 -200
-600 -100
-600 0
-600 100
-600 200
-600 300
-600 400
-600 500
-500 -500
-400 -400
-300 -300
-200 -200
-100 -100
100 100
200 200
300 300
400 400
500 500
100 -100
200 -200
300 -300
400 -400
500 -500
-100 100
-200 200
-300 300
-400 400
-500 500
700 700
-700 700

Repository

• Github-URL: https://github.com/LDubya/weruSnowflake77

Problem Set-Dateien aus Repo:

• weruSnowflake77.txt (XY-Listendatei, L2-Norm)
• weruSnowflake77.tsp (TSPLIB-Format, EUC_2D)

Python 3, 911 Städte, 1418 Sekunden Laufzeit auf NEOS

Das folgende Python 3.x-Skript generiert die Koordinaten von 911 Städten. Die Berechnung dauerte 1418 Sekunden den kürzesten Weg von 47739 .

Hier ist ein Bild von dir auf dem kürzesten Weg (danke an A. Rex):

Der Code / Algorithmus basiert auf der Feigenbaum-Bifurkation , mit der ich eine Reihe von Werten generiert habe, auf deren Basis ich die Koordinaten der Städte erstellt habe. Ich habe mit den Parametern experimentiert, bis ich eine Reihe von Städten unter 1000 gefunden habe, für die NEOS überraschend viel Zeit benötigte (deutlich über den erforderlichen 5 Minuten).

x = 0.579
coords = []
for _ in range(1301):
    if int(3001*x) not in coords:
        coords.append(int(3001*x))
    x = 3.8*x*(1-x)
coords = list(zip(coords, coords[::-1]))
print(len(coords))
for coord in coords:
    print(f"{coord[0]} {coord[1]}")

PS: Ich habe ein Skript, das auf der Suche nach einer geringeren Anzahl von Städten ausgeführt wird, die auf NEOS auch länger als 5 Minuten dauern. Ich werde sie in dieser Antwort posten, wenn ich welche finde.

PS: Verdammt! Das Ausführen dieses Skripts mit l- Parameter 1811 anstelle von 1301 führt zu 1156 Städten mit einer Laufzeit auf NEOS von etwas mehr als 4 Stunden , was viel mehr ist als in anderen Fällen mit ähnlichen Parametern ...