tło

Problem komiwojażera (TSP) prosi o najkrótszym obwodzie, które odwiedza dany zbiór miast. Na potrzeby tego pytania miasta będą punktami na płaszczyźnie, a odległości między nimi będą zwykłymi odległościami euklidesowymi (zaokrąglonymi do najbliższej liczby całkowitej). Obwód musi być „w obie strony”, co oznacza, że ​​musi wrócić do miasta początkowego.

Concorde TSP Solver może rozwiązać wystąpień euklidesowej problemu komiwojażera, dokładnie i dużo szybciej niż można by się spodziewać. Na przykład Concorde był w stanie rozwiązać dokładnie 85.900 punktów , których części wyglądają tak:

Jednak niektóre instancje TSP trwają zbyt długo, nawet w przypadku Concorde. Na przykład nikt nie był w stanie rozwiązać tej 100 000-punktowej instancji na podstawie Mona Lisa . (Jeśli możesz rozwiązać ten problem, otrzymasz nagrodę w wysokości 1000 $!)

Concorde jest dostępny do pobrania jako kod źródłowy lub plik wykonywalny. Domyślnie używa wbudowanego solwera programu liniowego (LP) QSopt , ale może także używać lepszych solverów LP, takich jak CPLEX.

Wyzwanie

Jaka jest najmniejsza generowana instancja TSP, której rozwiązanie zajmuje Concorde dłużej niż pięć minut ?

Możesz napisać program, który wyświetli instancję lub użyć dowolnej innej metody.

Punktacja

Im mniej punktów w instancji, tym lepiej. Więzy zostaną zerwane przez rozmiar pliku instancji (patrz poniżej).

Normalizacja

Różne komputery działają szybciej lub wolniej, więc użyjemy serwera NEOS dla Concorde jako standardu pomiaru czasu wykonywania. Możesz przesłać listę punktów w następującym prostym formularzu współrzędnych 2D:

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

Ustawienia, które powinny być używane w NEOS to: „Dane Concorde (plik xy-list, norma L2)”, „Algorytm: Concorde (QSopt)” i „Losowe ziarno: naprawione”.

Linia bazowa

Instancja 1889 punkt rl1889.tspz TSPLIB odbywa „Całkowity czas trwania: 871.18 (s)”, który jest więcej niż pięć minut. To wygląda tak:

88 miast, 341 sekund czasu działania na NEOS

W ostatnim artykule skonstruowaliśmy rodzinę trudnych do rozwiązania euklidesowych instancji TSP. Możesz pobrać wystąpienia z tej rodziny, a także kod do ich wygenerowania tutaj:

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

Wystąpienie 88 miasta z tej rodziny zabiera Concorde na serwerze NEOS dłużej niż 5 minut. Wystąpienie 178-tej rodziny z tej rodziny zajmuje już ponad dzień.

77 miast, 7,24 minuty (434,4 sekundy) średni czas pracy na NEOS

Jestem trochę spóźniony na imprezę, ale chciałbym wnieść wkład do 77-węzłowej instancji, weruSnowflake77.

Stworzyłem to wystąpienie, próbując zrozumieć, które cechy lokalne i globalne wywierają presję w górę na ilość czasu, jaką concorde potrzebuje, aby dopasować swoją najlepszą dolną granicę do długości najkrótszej znalezionej trasy.

Aby skonstruować ten przykład, zacząłem od grafu bazowego (kwadrat 13 x 13), a następnie systematycznie wprowadzałem nowe punkty lub tłumaczyłem stare punkty, zachowując korekty, które wydawały się powodować, że concorde średnio zagłębiał się w gałęzie przed cięciem.

Technika ta jest podobna do sposobu, w jaki algorytm genetyczny mutuje istniejące trasy i zachowuje krótsze trasy dla następnej generacji mutacji, z wyjątkiem tego, że sam wykres jest mutowany, a trudniejsze do rozwiązania wykresy są zachowywane. Jest to również podobne do sposobu, w jaki mutujemy wykresy za pomocą relaksacji, aby pomóc konstruować dobre dolne granice, z wyjątkiem tego, że idę w drugą stronę, mutując istniejący wykres, aby utworzyć wykres z trudnymi do znalezienia dolnymi granicami.

W trakcie procesu znalazłem kilka mniejszych wykresów, których rozwiązanie zajmuje Concorde minut, ale jest to pierwszy mały wykres, który znalazłem Concorde minimum 5 minut.

Przy 10 próbnych uruchomieniach na NEOS przy użyciu ustalonego materiału siewnego i QSopt średni czas działania wyniósł 7,24 minuty (434,531 sekund). Minimalny czas pracy wynosił 5,6 minuty (336,64 sekundy). Maksymalny czas działania wynosił 8,6 minuty (515,80 sekund). Żadne próby nie zostały odrzucone. Pełna tabela porównawcza poniżej:

Wyniki testu porównawczego dla 10 przebiegów:

----------------------------------
| 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 (lista xy, norma 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

Magazyn

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

Problem z ustawieniem plików z repozytorium:

• weruSnowflake77.txt (plik listy xy, norma L2)
• weruSnowflake77.tsp (format TSPLIB, EUC_2D)

Python 3, 911 miast, 1418 sekund czasu działania na NEOS

Poniższy skrypt w języku Python 3.x generuje współrzędne 911 miast. Obliczenie najkrótszej ścieżki z 47739 zajęło NEOS 1418 sekund .

Oto zdjęcie twojej najkrótszej ścieżki (dzięki A. Rex):

Kod / algorytm oparty jest na bifurkacji Feigenbauma , której użyłem do wygenerowania szeregu wartości, które posłużyłem jako podstawa do wygenerowania współrzędnych miast. Eksperymentowałem z parametrami, dopóki nie znalazłem liczby miast poniżej 1000, które zajęły NEOS zaskakująco dużo czasu (znacznie powyżej wymaganych 5 minut).

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: Mam skrypt działający w poszukiwaniu mniejszej liczby miast, które także zajmują> 5 minut w NEOS. Prześlę je w tej odpowiedzi, jeśli ją znajdę.

PS: Cholera! Uruchomienie tego skryptu z parametrem l 1811 zamiast 1301 powoduje, że w 1156 miastach czas działania na NEOS wynosi nieco ponad 4 godziny , co stanowi znacznie więcej niż w innych przypadkach o podobnych parametrach ...