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

decide whether or not to accept a trial based on simple probability

Computing degrees and minutes for GEO instances

pick a random vertex, and delete its closest neighbors

extracting a tour from the prev pointers.

build tour from scratch on a cold restart

initialize four noise values, none, low, med, and high

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.

compute the cost of inserting vertex v into position i of tour

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 http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/TSPFAQ.html

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

Update only at the end of each trial – update based on average success over the trial

return the vertex before tour[i] on tour

print best cost so far

print statement at the beginning of a cold trial

print the main parameter settings

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

print tour summary at end of execution

print details at the end of each warm trial

a string representing the progress bar

rand_select for randomize over all minimizers

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.

choose set with pdf_select, and then insert in best place with noise

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: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/TSPFAQ.html

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

removing a single continuos segment of the tour of size num_remove

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

sums the weights for all the powers (i.e., the insertion or deletion methods)

Compute the length of a tour

Checks if a tour is feasible in that it visits each set exactly once.

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.