PyConcorde gives clearly non-optimal solutions

[berkkarasu]

Hello, I am trying to use PyConcorde on Ubuntu 22.04.3 LTS, Python 3.10.12. First I was trying to solve an asymmetric problem but the solution was an obvious non-optimal. Then I symmetrized the distance matrix and solve it but it is also far from optimal, also having a bird-flight distance did not work. I am creating my own TSPLIB file and it is as follows. It is .tsp in the local but I cannot upload .tsp files here hence I changed the extension of it. distance_matrix.txt I followed #27 and multiplied the distances with 100,000. The reason why I do not use coordinates is if PyConcorde works I will work with walking distances. My code is as follows:

import os import numpy as np import pandas as pd from concorde.tsp import TSPSolver from concorde.tests.data_utils import get_dataset_path

def generate_tsp_file(file_name, directory): data_from_csv = pd.read_csv(file_name + '.csv') distance_matrix = data_from_csv.values file_path = os.path.join(directory, file_name) with open(file_path, 'w') as f: n = len(distance_matrix) f.write("NAME: temp\n") f.write(f"TYPE: TSP\n") f.write(f"DIMENSION: {n}\n") f.write("EDGE_WEIGHT_TYPE: EXPLICIT\n") f.write("EDGE_WEIGHT_FORMAT: FULL_MATRIX\n") f.write("EDGE_WEIGHT_SECTION\n") np.savetxt(f, distance_matrix, fmt='%d') return file_path

def solve_tsp(file_path): fname = get_dataset_path(file_path) solver = TSPSolver.from_tspfile(fname) solution = solver.solve() return solution

if name == "main": directory_path = '/pyconcorde/pyconcorde/concorde/tests/data' file_name = 'distance_matrix' tsp_file = generate_tsp_file(file_name, directory_path) solution = solve_tsp(tsp_file) print(solution.optimal_value) print(solution.tour)

[berkkarasu]

def solveTSP_grb(nodes, dist_matrix): """List of nodes (first node is depot), takes time matrix """ print(f"TSP Cluster: {nodes}") I = nodes[:] #Includes depot at index 0 m = gp.Model("CK Model")

m.setParam("LogToConsole", False)

# m.setParam('MIPGAP', 0.04)
m.setParam('TimeLimit', 5) #limit with 5 seconds
#X_ijkt
X = m.addVars(I,I, lb=0.0, vtype=GRB.BINARY, name='X')   
#U_ikt
U = m.addVars(I, lb=0.0, vtype=GRB.INTEGER, name='U')
##OBJECTIVE
obj = gp.quicksum((dist_matrix[i][j])*X[i,j] for i in I for j in I)
# obj += gp.quicksum((t_read[i])*X[i,j] for i in I for j in I)
m.setObjective(obj)
##st constraints
m.addConstrs((gp.quicksum(X[i,j] for i in I if i!=j) == 1 for j in I),"cons1")
m.addConstrs((gp.quicksum(X[i,j] for j in I if j!=i) == 1 for i in I),"cons2")
#sub-tour elimination
m.addConstrs(( U[i] - U[j] + len(I)*X[i,j] <= len(I)-1\
              for i in I[1:] for j in I[1:]),"cons3")   
m.optimize()
print('Obj: %g' % m.objVal)
x_list = np.zeros(shape = (len(I),len(I)))
for i in range(len(I)):
    for j in range(len(I)):
        x_list[i,j] = (X[nodes[i],nodes[j]].X)
visited = []
route = []
route.append(nodes[0])
i = 0
while True:
    for j in range(len(I)):
        if x_list[i,j] == 1 and nodes[j] not in visited:
            route.append(nodes[j])
            visited.append(nodes[j])
            i = j
            break
    if i == 0:
        break 
print(f"Route TSP: {route} - Obj: {m.objVal}")
solution = (m.objVal, route)
return solution

You can cross validate the tour with the following code. It uses Gurobi, if one has a license, one can check it with the above given code block. Sorry for closing the issue lately but if the distances are not so small, current version works without any problem.