G2-opgave: Konkurrence

Instanser:

• swiss42.tsp (1273)
• gr48.tsp (5046)
• gr120.tsp (6942)
• rand50.tsp (966)
• rand90.tsp (996)

Bedste køretider:

Metoder:

• Anders Schack-Nielsen (m.fl.): Forgreningsstrategi: Vi tager udgangspunkt i den foreslåede, men vi har gjort løsningsrummene disjunkte på følgende måde: Find en knude i 1-træet med valens>2 og vælg tre af kanterne. Branch med første kant udelukket. Branch med første kant tvunget med og anden kant udelukket. Branch med føRste og anden kant tvunget med og tredje kant udelukket. Øvre grænseværdier: Når vi finder grænseværdier, ser vi på om 1-træet næsten er en hamiltonkreds; hvis det er tilfældet bruger vi den grådige algoritme baseret på den metrik, der ligger til grund for 1-træet til at finde en løsning. For at måle hvor meget 1-træet ligner en hamiltonkreds betragtes summen af valensernes afstand til 2. Tanken er at hvis metrikken er blevet modificeret på en sådan måde at 1-træet næsten er en hamiltonkreds, vil den grådigt genererede hamiltonkreds ligne 1-træet, og dermed vil den grådige løsning være tæt på den optimale løsning. Modificering af metrikken: Ved modificeringen bruges følgende formel: c'(i,j)=c(i,j)+k(d_i+d_j-4) Det interessante er her valget af k. Vi initialiserer k til cirka 10% af den gennemsnitlige kantvægt af det genererede 1-træ. Når iterationerne så ser ud til at holde op med at give forbedringer sænker vi k en anelse og itererer videre. Ideen er først at lave store ændringer i metrikken for dernæst at finpudse mere og mere indtil der ikke kan presses en bedre grænseværdi ud.
• Niels Teglsbo, Mads Lundemann: 1-træ-relaxering med heuristik i hver branch-and-bound-knude
• David Pisinger: Nedre grænseværdi: 1-træ relaxering. Alle coefficienter scaleres med en passende faktor, for at have en finere opløsning. Iterering bruger max 5000 iterationer, men standser hvis grænseværdien er tilpas god til at branch-and-bound algoritmen kan "back-tracke" eller hvis der ikke er sket nogen forbedring i 20 iterationer. Øvre grænseværdi: I hver knude af branch-and-bound træet køres tabu-søgning med et lille antal iterationer. Problemet løses endvidere heuristisk som del af den itererede 1-træ grænseværdi (men kun når der er fundet en forbedret 1-træ grænseværdi) i alle branch-and-bound knuder indtil dybde 10. Forgreningsstrategi: Her udvælges en knude i 1-træet som har mere end 2 incidente kanter, og differencen mellem den dyreste kant og næstdyreste kant er størst mulig. For den valgte knude vælges billigste kant først. Sortering: Da sortering tager temmelig lang tid i Kruskal, bruges "forsinket" sortering. Denne tager udgangspunkt i en randomiseret version af quicksort, hvor alene venstre-intervallet sorteres, mens højre-intervallet skubbes på en stak. Efterhånden som Kruskal får brug for flere kanter, poppes næste interval fra stakken. Store intervaller sorteres med "quicksort" mens små intervaller sorteres med "insertionsort". Overlappende delproblemer: Da den valgte forgreningsstategi kan føre til overlappende delproblemer er der forsøgt med en tabel over alle tidligere besøgte delproblemer (givet ved forbudte kanter). Hashing bruges til at finde et allerede besøgt delproblem. Dette gav dog ingen signifikant forbedring af køretiden.