search

Hanjun-Dai / graph_comb_opt

Implementation of "Learning Combinatorial Optimization Algorithms over Graphs"
https://arxiv.org/abs/1704.01665
MIT License
491 stars 135 forks source link

Data generator for TSP? #17

Closed xzymustbexzy closed 4 years ago

xzymustbexzy commented 4 years ago

Hello, I'm going to run s2v_tsp2d. However, I didn't find data generator for TSP problem. So the program cannot run without data file. Is that my mistake? image

image

Hanjun-Dai commented 4 years ago

Hi,

The data is available via the dropbox link (in README). You need to download the data and put it in the path specified above.

xzymustbexzy commented 4 years ago

Thank you!!! I ran the program successfully.

But I found something confused. I write my own data generator for tsp2d according to your data. And I set n=10, which means min-n = 10 and max-n = 10.
The average cost converged on 2.72275822993. image

However, the precise answer given by my dynamic programming algorithm is 2.899085780099285.

It is weird that I got a cost lower than the standard answer. Is it possible that your program have missed adding the cost of the route back to starting point? Because I try to print the process of cost accumulation. I found there are only 9 times addition. image I'am trying to fix it but I don't know how to start. Can you give me some suggestions? Thank you!

Hanjun-Dai commented 4 years ago

Hi,

The cost printed at each step is the 'delta' between new tour length and old tour length. Our algorithm will also produce the actual solution. You can double check the tour length of the solution to verify.

xzymustbexzy commented 4 years ago

Hi,

The cost printed at each step is the 'delta' between new tour length and old tour length. Our algorithm will also produce the actual solution. You can double check the tour length of the solution to verify.

Ok, I understand. Thanks for your answer.