pyconcorde still returning non-optimal solution even if multiplied by large constant

[ckckdud3]

Hi. I'm currently doing my project about TSP, and I got same problem with #27 . Then I found solution by referencing #29 . But still, I get non-optimal solution. Am I doing something wrong?

Here's the code generating test cases.

import time
import argparse
import pprint as pp
import os

import pandas as pd
import numpy as np
from concorde.tsp import TSPSolver


if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument("--num_samples", type=int, default=10000)
    parser.add_argument("--num_nodes", type=int, default=20)
    parser.add_argument("--node_dim", type=int, default=2)
    parser.add_argument("--filename", type=str, default=None)
    opts = parser.parse_args()
    
    if opts.filename is None:
        opts.filename = f"tsp{opts.num_nodes}_concorde.txt"
    
    # Pretty print the run args
    pp.pprint(vars(opts))
    
    set_nodes_coord = np.random.random([opts.num_samples, opts.num_nodes, opts.node_dim])
    with open(opts.filename, "w") as f:
        start_time = time.time()
        for nodes_coord in set_nodes_coord:
            solver = TSPSolver.from_data(nodes_coord[:,0]*1000.0, nodes_coord[:,1]*1000.0, norm="GEO")  
            solution = solver.solve()
            f.write( " ".join( str(x)+str(" ")+str(y) for x,y in nodes_coord) )
            f.write( str(" ") + str('output') + str(" ") )
            f.write( str(" ").join( str(node_idx+1) for node_idx in solution.tour) )
            f.write( str(" ") + str(solution.tour[0]+1) + str(" ") )
            f.write( "\n" )
        end_time = time.time() - start_time
    
    print(f"Completed generation of {opts.num_samples} samples of TSP{opts.num_nodes}.")
    print(f"Total time: {end_time/3600:.1f}h")
    print(f"Average time: {(end_time/3600)/opts.num_samples:.1f}h")

Here's the log comparing between dynamic programming and pyconcorde's solution. The right one is pyconcorde.

Solver's answer : {'path': [1, 8, 7, 5, 3, 4, 9, 2, 6, 10, 1], 'dist': 1931.0009165682181}, Ground truth : {'path': [1, 6, 2, 9, 4, 3, 5, 7, 8, 10, 1], 'dist': 1931.2294489317756}, Distance ratio : 0.9999 [2023-10-24 13:40:54,262] [INFO] DP_with_Python.core.DPsolver : Non-optimal ground truth detected at line 28

Solver's answer : {'path': [1, 10, 9, 6, 7, 5, 3, 4, 8, 2, 1], 'dist': 3290.7949217150517}, Ground truth : {'path': [1, 10, 9, 7, 6, 5, 3, 4, 8, 2, 1], 'dist': 3291.593381927084}, Distance ratio : 0.9998 [2023-10-24 13:40:54,513] [INFO] DP_with_Python.core.DPsolver : Non-optimal ground truth detected at line 52

Solver's answer : {'path': [1, 3, 2, 6, 8, 7, 4, 9, 5, 10, 1], 'dist': 2896.4304536001246}, Ground truth : {'path': [1, 5, 10, 9, 4, 7, 8, 6, 2, 3, 1], 'dist': 2896.52929928521}, Distance ratio : 1.0000 [2023-10-24 13:40:54,854] [INFO] DP_with_Python.core.DPsolver : Non-optimal ground truth detected at line 84

Solver's answer : {'path': [1, 4, 3, 10, 5, 7, 9, 2, 6, 8, 1], 'dist': 3422.722309388618}, Ground truth : {'path': [1, 4, 3, 10, 5, 7, 9, 6, 2, 8, 1], 'dist': 3424.7565709806477}, Distance ratio : 0.9994 [2023-10-24 13:40:54,923] [INFO] DP_with_Python.core.DPsolver : Non-optimal ground truth detected at line 90

Here's the testcase.

line 28

0.13365286681119548 0.775124291163829 0.6262407216823861 0.48417252462024896 0.37558905092819284 0.10783013927778085 0.4759268774172719 0.20764190994816112 0.4080730976916952 0.199100093947862 0.43412845426491087 0.5098472650675068 0.349925497417773 0.2993831694060224 0.39910950926391486 0.33241549058780295 0.6566711748821851 0.3557285107468181 0.1210677983466093, 0.7914883920881095

line 52

0.0027453272685807883 0.34167248494550784 0.022349077799408423 0.8431201493395777 0.48714193585105003 0.9710437386135105 0.3862264667833435 0.6820655851649218 0.9224238378936594 0.5236819947780356 0.8684722106483034 0.14622649960263912 0.7422628759059251 0.3784962058360615 0.1804027165309694 0.6682874063558575 0.662082284677872 0.30304804484945325 0.3056898561213095 0.3447664670250974

line 84

0.5011156225921699 0.6892620346835608 0.05984559581208604 0.6902225250292093 0.09110067016451284 0.7796763892564293 0.4080721372625684 0.17211963022667587 0.9197147166291071 0.7082441149989812 0.1568825257693991 0.08998892182929441 0.31922131574394164 0.0431492836236782 0.13465119636772116 0.05366263509779934 0.5249124874630288 0.5672241146168874 0.9883938400931592 0.7221472259219374

line 90 0.31352208903653245 0.756598612247736 0.7785527414766625 0.837343342644692 0.056311899155914835 0.15224489558059096 0.3926548044014855 0.3288157799999495 0.8083194509812704 0.17410051861185039 0.9958032689281642 0.9903909123857684 0.9448325448765551 0.26792900755100413 0.35770877186297223 0.8076764847556631 0.7003318390039616 0.6266679739857316 0.2918873831507476 0.052670512329223484

[ckckdud3]

By the way I found this on pyconcorde log. What does this mean?

"Basic dual change required, but no candidate edges ERROR: No dual change in basis finding code Did not find a basic optimal solution"