Statistics on solver

[sn0rkmaiden]

Hello, I am researching LKH algorithm and trying to compare it to other methods of solving TSP (I am interested in asymmetric case). For this I would like to collect some information of how the cost of the final tour has been changing throughout the run. I have found some methods that collect statistics in LKH-3.0.8 folder in Statistics.c file. I forked the repo and tried returning the statistics I need from LKHmain.c file. However, I was not able to install the changed version of repository to try it out. I tried running:

!pip install git+https://github.com/sn0rkmaiden/elkai.git

after installing the original package but nothing seems to have changed.

Could you please advise what would be the correct way of doing something like this? Thanks in advance.

[fikisipi]

Do pip uninstall elkai, and then cd to your cloned repo and do pip install -e ..

Note that you'll need to store the data somewhere - or print it to stdout.

On one hand I want to rewrite the LKH source code to have easy FFI to Python, but on the other hand the original author releases new updates so every change will require days worth of work.

[sn0rkmaiden]

@fikisipi Thank you very much for your answer! I tried what you have suggested but got this error:

Do you know what could be the problem? Or is it not the best approach for this? Thanks again.

[fikisipi]

@sn0rkmaiden

I tried running it on my M1 and I can see that you have error in your fork's code:

You need the std namespace.

[sn0rkmaiden]

@fikisipi Hello again! I've been working on this repository for a couple of days and I think I have figured out how to return statistics on how the value of cost has been changing throughout the run. Currently I'm just returning the history of the last run but I think I can fix that and be able to return history of all runs. I tested it on a problem ftv70.atsp and got this plot:

I made returning history as an optional argument in the function solve_tsp. I've made these changes to my own copy of elkai repo. So this is full testing code:

import elkai
import gzip
import numpy as np
import matplotlib.pyplot as plt

def read_atsplib(filename):
     "basic function for reading a ATSP problem on the TSPLIB format"
     "NOTE: only works for explicit matrices"

     if filename[-3:] == ".gz":
         f = gzip.open(filename, 'r')
         data = f.readlines()
     else:
         f = open(filename, 'r')
         data = f.readlines()

     for line in data:
         if line.find("DIMENSION") >= 0:
             n = int(line.split()[1])
             break
     else:
         raise IOError("'DIMENSION' keyword not found in file '%s'" % filename)

     for line in data:
         if line.find("EDGE_WEIGHT_TYPE") >= 0:
             if line.split()[1] == "EXPLICIT":
                 break
     else:
         raise IOError("'EDGE_WEIGHT_TYPE' is not 'EXPLICIT' in file '%s'" % filename)

     for k, line in enumerate(data):
         if line.find("EDGE_WEIGHT_SECTION") >= 0:
             break
     else:
         raise IOError("'EDGE_WEIGHT_SECTION' not found in file '%s'" % filename)

     c = {}
     # flatten list of distances
     dist = []
     for line in data[k + 1:]:
         if line.find("EOF") >= 0:
             break
         for val in line.split():
             dist.append(int(val))

     k = 0
     for i in range(n):
         for j in range(n):
             c[i + 1, j + 1] = dist[k]
             k += 1

     return n, c

w = 'ftv70.atsp'
n, c = read_atsplib(f'C:/elkai-stats/{w}')

adj = np.zeros((n, n))
for pair, distance in c.items():
  adj[pair[0] - 1][pair[1] - 1] = int(distance)
adj = adj.astype(int)

cities = elkai.DistanceMatrix(adj.tolist())

tour, history = cities.solve_tsp(runs=2, returnHistory=True)
s = sum([adj[tour[i]][tour[i+1]] for i in range(len(tour) - 1)])
print(tour)
print(s)


plt.plot([abs(s - x) for x in history])
plt.ylabel('Error')
plt.xlabel('Iteration')
plt.show()

[fikisipi]

@sn0rkmaiden Thank you, that's awesome. I'll take a look and expose it through the FFI.