Main GTSP solver, which takes as input a problem instance and some optional arguments


A struct to store each insertion/deletion method using its power, its weight, and its score on the last segment


tour type that stores the order array and the length of the tour


decide whether or not to accept a trial based on simulated annealing criteria


initialize the insertion methods. Use powers between -10 and 10 the spacing between weights is chosen so that when you increase the weight, the probability of selecting something that is a given distance farther is cut in half.


Given a tour and a set, this function finds the vertex in the set with minimum insertion cost, along with the position of this insertion in the tour. If best_position is i, then vertex should be inserted between tour[i-1] and tour[i].


Find the set with the smallest number of vertices


Find the set with the smallest number of vertices


Sequentially moves each vertex to its best point on the tour. Repeats until no more moves can be found


init function defined by TSPLIB


repeatedly perform moveopt and reopt_tour until there is no improvement


Three different parameter settings for the GTSP solver default – moderate runtime. ~ 10-20 seconds for 100 sets fast – very quick, lower quality solution slow – slower, but potentially higher quality solution


selecting a random k in 1 to length(weights) according to power and then selecting the kth smallest element in weights


some insertions break tie by taking first minimizer – this randomization helps avoid getting stuck choosing same minimizer


function takes in a set of bins and a weights array of the same length and selects a bin with probability equal to weight


Update both insertion and deletion powers along with the total weights if we are a multiple of param[:adaptive_iter] iterations in trial


Print the powers in an easy-to-read format for debugging the adaptive weights


Randomly shuffle the sets, and then insert the best vertex from each set back into the tour where sets are considered in shuffled order.


Randomly shuffle the sets, and then insert the best vertex from each set back into the tour where sets are considered in shuffled order.


parse the problem instance file given as a text file with the following format: N: int M: int Symmetric: true/false Triangle: true/false 1 5 5 1 8 9 10 11 8 2 3 4 6 7 12 13 14 DISTANCE_MATRIX

Note: the line 5 1 8 9 10 11 shows that the second set contains 5 vertices: 1,8,9,10,11.

TSPLIB Parser defined by:


outputs the new cost and prev for vertex v2 after relaxing does not actually update the cost


relaxes the cost of each vertex in the set set2 in-place.


determine the cost of removing the vertex at position i in the tour


Select a removal and an insertion method using powers, and then perform removal followed by insertion on tour. Operation done in place.


Given an ordering of the sets, this alg performs BFS to find the optimal vertex in each set


Select an integer between 1 and num according to and exponential distribution with lambda = power

goes from left of array if power is positive

and right of array if it is negative


Remove the vertices randomly, but biased towards those that add the most length to the tour. Bias is based on the power input. Vertices are then selected via pdf select.


determine the cost of removing each vertex from the tour, given that all others remain.