Contexte

Le problème des vendeurs ambulants (TSP) demande le circuit le plus court qui visite une collection donnée de villes. Aux fins de cette question, les villes seront des points dans le plan et les distances entre elles seront les distances euclidiennes habituelles (arrondies à l'entier le plus proche). Le circuit doit être "aller-retour", c'est-à-dire qu'il doit retourner dans la ville de départ.

Le solveur Concorde TSP peut résoudre les cas du problème des vendeurs itinérants euclidiens, exactement et beaucoup plus rapidement que ce à quoi on pourrait s'attendre. Par exemple, Concorde a pu résoudre une instance de 85 900 points exactement, dont certaines parties ressemblent à ceci:

Cependant, certaines instances TSP prennent trop de temps, même pour Concorde. Par exemple, personne n'a pu résoudre cette instance de 100 000 points basée sur la Joconde . (Il y a un prix de 1000 $ offert si vous pouvez le résoudre!)

Concorde est disponible en téléchargement sous forme de code source ou d'exécutable. Par défaut, il utilise le solveur de programme linéaire (LP) intégré QSopt , mais il peut également utiliser de meilleurs solveurs LP comme CPLEX.

Le défi

Quelle est la plus petite instance TSP que vous pouvez générer et qui met Concorde plus de cinq minutes à résoudre?

Vous pouvez écrire un programme pour sortir l'instance, ou utiliser toute autre méthode que vous souhaitez.

Notation

Moins il y a de points dans l'instance, mieux c'est. Les liens seront rompus par la taille du fichier de l'instance (voir ci-dessous).

Standardisation

Différents ordinateurs fonctionnent plus rapidement ou plus lentement, nous allons donc utiliser le serveur NEOS pour Concorde comme standard de mesure pour l'exécution. Vous pouvez soumettre une liste de points sous la forme de coordonnées 2D simple suivante:

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

Les paramètres qui doivent être utilisés sur NEOS sont "Données Concorde (fichier xy-list, norme L2)", "Algorithme: Concorde (QSopt)" et "Graine aléatoire: fixe".

Référence

L'instance rl1889.tspde 1 889 points de TSPLIB prend "Total Running Time: 871.18 (seconds)", soit plus de cinq minutes. Cela ressemble à ceci:

88 villes, 341 secondes d'exécution sur NEOS

Dans un article récent, nous avons construit une famille d'instances TSP euclidiennes difficiles à résoudre. Vous pouvez télécharger les instances de cette famille ainsi que le code pour les générer ici:

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

L'instance de 88 villes de cette famille prend Concorde sur le serveur NEOS plus de 5 minutes. L'instance de 178 villes de cette famille prend déjà plus d'une journée à résoudre.

77 villes, 7,24 minutes (434,4 secondes) de durée moyenne d'exécution sur NEOS

Je suis un peu en retard à la fête, mais j'aimerais contribuer à une instance de 77 nœuds, weruSnowflake77.

J'ai créé cette instance tout en essayant de comprendre quelles caractéristiques locales et mondiales imposent une pression à la hausse sur le temps nécessaire à la concorde pour correspondre à sa meilleure limite inférieure avec la durée de sa tournée la plus courte trouvée.

Pour construire cette instance, j'ai commencé par un graphe de base (carré 13 x 13), puis j'ai systématiquement introduit de nouveaux points ou traduit d'anciens points, en conservant les ajustements qui semblaient faire en sorte que la concorde s'enfonce plus profondément dans ses branches en moyenne avant de couper.

La technique est similaire à la façon dont un algorithme génétique mute les circuits existants et conserve des circuits plus courts pour la prochaine génération de mutations, sauf que le graphique lui-même est muté et que les graphiques plus difficiles à résoudre sont conservés. C'est aussi similaire à la façon dont nous mutons les graphiques en utilisant des relaxations pour aider à construire de bonnes limites inférieures, sauf que je vais dans le sens inverse, en mutant un graphique existant pour construire un graphique avec des limites inférieures difficiles à trouver.

Dans le processus, j'ai trouvé quelques petits graphiques qui prennent des minutes concorde à résoudre, mais c'est le premier petit graphique que j'ai trouvé qui prend concorde un minimum de 5 minutes.

Avec 10 essais sur NEOS utilisant le germe fixe et QSopt, le temps d'exécution moyen était de 7,24 minutes (434,531 secondes). Le temps d'exécution minimum était de 5,6 minutes (336,64 secondes). Le temps d'exécution maximal était de 8,6 minutes (515,80 secondes). Aucun essai n'a été rejeté. Tableau de référence complet ci-dessous:

Résultats de référence sur 10 essais:

----------------------------------
| 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 (liste xy, norme L2):

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

Dépôt

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

Problème défini dans les fichiers du référentiel:

• weruSnowflake77.txt (fichier de liste xy, norme L2)
• weruSnowflake77.tsp (format TSPLIB, EUC_2D)

Python 3, 911 villes, 1418 secondes de temps d'exécution sur NEOS

Le script Python 3.x suivant génère les coordonnées de 911 villes. Il a fallu NEOS 1418 secondes pour calculer le trajet le plus court de 47739.

Voici une photo du chemin le plus court (merci à A. Rex):

Le code / algorithme est basé sur la bifurcation de Feigenbaum , que j'ai utilisée pour générer une série de valeurs, que j'ai utilisée comme base pour générer les coordonnées des villes. J'ai expérimenté les paramètres jusqu'à ce que je trouve un certain nombre de villes de moins de 1000 qui ont pris NEOS un temps surprenant (bien au-dessus des 5 minutes requises).

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: J'ai un script en cours d'exécution à la recherche d'un nombre inférieur de villes qui prennent également> 5 minutes sur NEOS. Je les posterai dans cette réponse si j'en trouve.

PS: Merde! L'exécution de ce script avec le paramètre l 1811 au lieu de 1301 entraîne 1156 villes avec un temps d'exécution sur NEOS d'un peu plus de 4 heures , ce qui est beaucoup plus que d'autres cas avec des paramètres similaires ...