Issue with big coordinates
27am opened this issue · 4 comments
Hi there!
First of all thanks for the great repo ;)
I am getting the following error when I try to solve the 52 cities dataset with rescaled coordinates so that they are in the order of 1 billion (1e9)
Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)
I was wondering if somebody else is getting the same
Cheers
@27am Thanks for flagging this -- can you post an example to replicate the problem?
Sure! The code reads the file, scales the value of the coordinates and tries to compute the solution
from concorde.tsp import TSPSolver
from concorde.tests.data_utils import get_dataset_path
import numpy as np
X = []
Y = []
numbers = "0123456789"
fname = get_dataset_path("berlin52")
with open(fname) as file:
for line in file.readlines():
if line[0] in numbers:
X.append(float(line.split()[1]))
Y.append(float(line.split()[2]))
magnification = 10000000
scaledX = np.array([(coordinate * magnification) for coordinate in X])
scaledY = np.array([(coordinate * magnification) for coordinate in Y])
solver = TSPSolver.from_data(xs=scaledX, ys=scaledY, norm="EUC_2D")
solution = solver.solve()
Output:
Problem Name: berlin52
Problem Type: TSP
52 locations in Berlin (Groetschel)
Number of Nodes: 52
Rounded Euclidean Norm (CC_EUCLIDEAN)
Problem Name: 358c4b7ad5574fbb80e4b2313ef35431
Problem Type: TSP
Number of Nodes: 52
Rounded Euclidean Norm (CC_EUCLIDEAN)
CCtsp_solve_dat ...
Finding a good tour for compression ...
linkern ...
Starting Cycle: -91441622145
Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)
Thanks! Judging from the output (e.g. the Starting Cycle: -91441622145
) it looks like you're running into some kind of integer overflow. Is it possible to start with a lower magnification, and see if the problem can be solved? You can always start with e.g. magnification 100, round all the coordinates, obtain an approximate solution, and then increase the magnification repeatedly to get a better solution.
Thank you! Indeed with a smaller magnification there is no problem. The bug for me arises when the value is around 1000000 but I think there is no easy workaround.
I wanted to rescale the coordinate so that they lie in the space between 0 and 2^128 but I guess I need to "rescale" my expectation :)