`Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems`

🎯 ICML 2024 Oral Paper

😊 Authors: Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lei Song, Jiang Bian

Overview

Our theoretical and experimental analysis raises doubts about the effectiveness of ML-based heatmap generation. In support of this, we demonstrate that a simple baseline method can outperform complex ML approaches in heatmap generation. Furthermore, we question the practical value of the heatmap-guided MCTS paradigm. To substantiate this, our findings show its inferiority to the LKH-3 heuristic despite the paradigm's reliance on problem-specific, hand-crafted strategies.

⚠️⚠️⚠️Addressing the Recent Commentary

We have recently received feedback from the commentary titled "Comment on paper: Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems" by the author of the UTSP algorithm, claiming that our inference times are inconsistent and questioning the validity of our conclusions. We would like to clarify the following points:

Performance Comparison: As detailed in Table 1 of our paper, even if we disregard the I/O time for UTSP, its performance remains the poorest. Furthermore, UTSP fails to scale to TSP-10000 instances. Hence, our original conclusion remains robust: UTSP lags behind SoftDist in both speed and performance metrics.
Misinterpretation of Table 3: The intent of our Table 3 experiment is to demonstrate that, with finely-tuned MCTS parameters, the impact of the heatmap diminishes. As Table 3 shows, even when using a Zero heatmap for TSP-500, the final results surpass those of UTSP. Therefore, in a scenario where MCTS parameters are optimized, the practical value of all ML-based algorithms is questionable.

Additionally, we believe that there may have been some misunderstandings or misinterpretations in the commentary. We encourage a thorough review of our paper to ensure a complete and accurate understanding of our findings.

We hope this addresses any confusion and prevents any future misinterpretations.

For a more detailed discussion, please refer to the pinned issue.

Installation

Environment Setup: The project relies on the fire, lkh, numpy, and torch libraries. Install them using the following commands:
```
pip install fire
pip install lkh
pip install numpy
```
Install torch according to your CUDA version. For CUDA 11.4, use:
```
pip install torch==1.11.0+cu113 torchvision==0.12.0+cu113 torchaudio==0.11.0 --extra-index-url https://download.pytorch.org/whl/cu113
```

Heatmap Loading

About Heatmaps: The all_heatmap folder contains all heatmaps for heatmap-guided MCTS. The heatmaps for attgcn, dimes, and utsp are directly downloaded from their official GitHub repositories. As difusco did not provide heatmaps for download, we replicated their experiments to generate these heatmaps. First, you need to unzip all the heatmaps:
```
cd all_heatmap/attgcn
unzip heatmap.zip
cd ../difusco
unzip heatmap.zip
cd ../dimes
unzip heatmap.zip
cd ../utsp
unzip TSP500_Input.zip
unzip TSP1000_Input.zip
```
Note: The heatmap format used in utsp is inconsistent with the other methods, so some format conversion is needed:
```
python reformat_to_default.py 500
python reformat_to_default.py 1000
```
Then generate heatmaps using our proposed SoftDist method: First, unzip the input files:
```
cd ../../default_mcts
unzip tsp500_test_concorde.zip
unzip tsp1000_test_concorde.zip
unzip tsp10000_test_concorde.zip
```
Start generating heatmaps using SoftDist:
```
cd ../all_heatmap/softdist
python batch_generate_heatmap.py 500 0.0066
python batch_generate_heatmap.py 1000 0.0051
python batch_generate_heatmap.py 10000 0.0018
cd ../..
```

Testing with Default MCTS Parameters

Test with default MCTS parameters. Assuming the method name to be tested is name, which can be one of attgcn, difusco, dimes, softdist, utsp. Here is an example of testing softdist on TSP-500:
```
cd default_mcts
cp -r ../all_heatmap/softdist/heatmap .
bash solve-500.sh
python summarize.py 500
cd ..
```

Testing MCTS with Varying Time Budgets

Test MCTS with different time budgets (Example for TSP-500):

cd default_mcts_varying_time
unzip tsp500_test_concorde.zip
cp -r ../all_heatmap/softdist/heatmap .
bash multiT-500.sh
cd ..

Testing with UTSP's MCTS Parameters

Test with UTSP's MCTS parameters. Here is an example of testing softdist: First, convert the softdist heatmap format to the input format required by UTSP’s MCTS:
```
cd utsp
python reformat_to_utsp.py softdist 500
python reformat_to_utsp.py softdist 1000
```
Start the MCTS, using parameters provided by UTSP:
```
cd Search
bash ./new-solve-500.sh 0 5 100 0 50 2 1 1
python summarize.py 500
bash ./new-solve-1000.sh 0 5 10 0 150 3 1
python summarize.py 1000
cd ../..
```
Note: In UTSP's MCTS implementation, you need to update the specific value of #define Max_City_Num in TSP_IO.h according to the current size of the TSP problem.

Testing UTSP's MCTS with Varying Time Budgets

Test UTSP version of MCTS with different time budgets (Example for TSP-500):
```
cd utsp_varying_time
python reformat_to_utsp.py softdist 500
python reformat_to_utsp.py softdist 1000
cd Search
bash multiT-500.sh
cd ../..
```
Again, update #define Max_City_Num in TSP_IO.h according to the TSP problem size.

Calculating Metric Score

To calculate metric indicators, you need to test the performance of LKH-3 (Example for TSP-500):

cd calculate_score_metric
unzip tsp500_test_concorde.zip

# Ensure LKH-3 is installed and the path is set in lkh_solve.py
# Adjust the 'runs' parameter to align with the running time of MCTS.
python lkh_solve.py --N 500 --runs 5

cd ..

Grid Search for SoftDist Temperature Parameter

Grid search for SoftDist's temperature parameter: First, generate a training dataset for grid search, using TSP-500 as an example:
```
cd grid_search
python generate_training_data.py --N 500 --batch 1024
bash grid_search-500.sh
```

Citation

You can find the arXiv version of the paper here: https://arxiv.org/abs/2406.03503.

🌟 If you find this resource helpful, please consider starting this repository and cite our research:

@inproceedings{xia2024position,
      title={Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems}, 
      author={Yifan Xia, Xianliang Yang, Zichuan Liu,  Zhihao Liu, Lei Song, Jiang Bian},
      booktitle={Proceedings of the 41st International Conference on Machine Learning},
      pages={54178--54190},
      year={2024},
}

xyfffff/rethink_mcts_for_tsp

Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems