Code repository for paper:
Yimeng Min, Yiwei Bai, and Carla P. Gomes.
"Unsupervised Learning for Solving the Travelling Salesman Problem."
NeurIPS 2023
Here we provide an example for TSP 100, 200, 500 and 1000.
python train.py --num_of_nodes 200 --EPOCHS 300 --batch_size 32 --temperature 3.5 --C1_penalty 20.0 --nlayers 2 --hidden 64 --rescale 2.0 --moment 1 --lr 5e-3 --stepsize 20
Generate TSP 200 heatmaps (test file):
python loadmodel.py --num_of_nodes 200 --batch_size 128 --temperature 3.5 --nlayers 2 --hidden 64 --rescale 2.0 --moment 1
python train.py --num_of_nodes 500 --EPOCHS 300 --batch_size 64 --temperature 3.5 --C1_penalty 10.0 --nlayers 2 --hidden 64 --lr 3e-3 --rescale 4. --stepsize 20
python loadmodel.py --num_of_nodes 500 --batch_size 128 --temperature 3.5 --nlayers 2 --hidden 64 --rescale 4.0 --moment 1
python train.py --num_of_nodes 1000 --EPOCHS 300 --batch_size 64 --temperature 3.5 --nlayers 2 --hidden 128 --rescale 4. --C1_penalty 10.0 --lr 3e-3 --stepsize 20
python loadmodel.py --num_of_nodes 1000 --batch_size 128 --temperature 3.5 --nlayers 2 --hidden 128 --rescale 4.0 --moment 1
cd Search/
remember to mkdir Search/results/n first
change the #define Max_City_Num to n in Search/code/include/TSP_IO.h
change the instancenum in new-solve-n.sh
on TSP 200
./new-solve-200.sh 0 5 30 0 100 2 1 1
on TSP 500
./new-solve-500.sh 0 5 30 0 100 2 1 1
on TSP 1000
./new-solve-1000.sh 0 5 10 0 150 3 1 1
on TSP-500 and TSP-1000, we set T=0.04, (change Param_T in Search/code/include/TSP_IO.h)
on TSP-200, we set double Param_T=0.08;
the double Param_T controls the search time, longer time should have better results
for example, on TSP-500, if you set double Param_T=0.3; and run ./new-solve-500.sh 0 5 100 0 50 2 1 1,
you will have a gap around 0.42 % in around 10 minutes.
for example, on TSP-1000, if you set double Param_T=0.1; and run ./new-solve-1000.sh 0 5 100 0 50 2 1 1 or ./new-solve-1000.sh 0 5 10 0 150 3 1 1,
you will have a gap around 0.92 % in around 7 minutes.
python train.py --num_of_nodes 100 --EPOCHS 300 --batch_size 32 --temperature 3.5 --C1_penalty 20.0 --nlayers 2 --hidden 64 --rescale 1.0 --moment 1
python loadmodel.py --num_of_nodes 100 --batch_size 256 --temperature 3.5 --nlayers 2 --hidden 64 --rescale 1.0 --moment 1 --topk 10
when search TSP-100
in Search/code/include/TSP_IO.h
change #define Max_Inst_Num 128 to #define Max_Inst_Num 10000
set #define Max_City_Num 100
change int Total_Instance_Num = 128; to int Total_Instance_Num = 10000;
set int Inst_Num_Per_Batch = 313;
set double Param_T=0.01;
set int Rec_Num = 10; in code/include/TSP_IO.h; the Rec_Num should be equal --topk in loadmodel.py
also remember in Search/results, you need to mkdir 100 to create a file to store the results
run
./new-solve-100.sh 0.1 6 10 0 30 3 0 0
This code follows https://github.com/Spider-scnu/Monte-Carlo-tree-search-for-TSP.
If you want to construct your customized input file, you need to follow the following format:
Assume n is the number of cities
Each line represents one input
The first 2 * n floats are the coordinates following (x1, y1, ..., xn, yn)
Then there is a word "output". After it, we have n + 1 numbers, which shows the optimal solution.
Then there is a word "indices". After it, there are n * topk ints,
Then there is a word output. After it, there are n * topk float, which shows the corresponding heatmap value for each edge.
(1) Tune some paraters of code/include/TSP_IO.h and code/include/TSP_Markov_Devision.h Please search "!!!" in these two cpp healder files, and we comment what you should modifiy. (2) make (3) ./solve.sh $rec_only $M $K $alpha $beta $ph $restart 0
Note M, K, alpha and beta are exactly the same as we defined in the paper. And for their value, please check the Table 3 of the appendix.
Note for ph, we have a equation here: ph * n = T. T can also be found in the Table 3 and n is the number of cities.
rec_only: whether we only select edges from the heatmap that are greater than a threshold when we expand one node
M: maximal nodes we consider when we select the next node given one node.
K: maximal depths
restart: whether we use restart to randomly select the maximal depths