/benchmarking-tsp

Primary LanguageC

How Good is Neural Combinatorial Optimization?

This repository contains the source code for paper: How Good is Neural Combinatorial Optimization?

Table of Contents

Directory Structure

benchmarking-tsp/
├── problems/
├── solvers/              # NCO solvers, LKH, EAX and LKH(tuned)
├── utils/
│
├── data_large/      ──┐  # TSPLIB, National, etc.
├── data_test/         │
│                      │
├── pretrained/        │
│   ├── dact/          ├── our generated/used datasets, trained models
│   ├── pomo/          │   and test results, provided as *.tar.gz
│   ├── lkh/           │
│   └── nlkh/          │
│                      │
└── test_results/    ──┘

data.tar.gz, pretrained.tar.gz, and test_results.tar.gz

Installation

git clone https://github.com/yzhang-gh/benchmarking-tsp.git
cd benchmarking-tsp
# clone neural solvers
git submodule update --init --recursive

Environment

The code requires at least Python 3.8. Conda is recommended for managing the packages.

conda create -n tsp python=3.8
conda activate tsp

Install packages

conda install pytorch==1.7.1 torchvision==0.8.2 cudatoolkit=10.1 -c pytorch
conda install tqdm tensorboard

# === POMO specific ===
conda install pytz

# === NeuroLKH specific ===
conda install scikit-learn cython swig
# PyConcorde
git clone https://github.com/jvkersch/pyconcorde.git
cd pyconcorde
pip install -e .
# use `pip install -e . --no-build-isolation --no-binary :all:`
# if you get the 'ValueError: numpy.ndarray size changed, ...' error

# === Clustered TSP data generation ===
conda install r r-essentials
R
# in the R session
> install.packages("devtools", repos='...') # select a mirror from https://cran.r-project.org/mirrors.html
> Sys.setenv(TAR = "/bin/tar")
> devtools::install_github("jakobbossek/netgen")
> q()  # quit

Build NeuroLKH

cd solvers/nlkh
bash setup.sh

Build LKH

cd solvers/nlkh
make

Build EAX

cd solvers/EAXrestart/src
g++ -o ../bin/GA-EAX-restart -O3 main.cpp environment.cpp cross.cpp evaluator.cpp indi.cpp randomize.cpp kopt.cpp sort.cpp -lm

Test

Test on synthetic TSP problems

python test.py

The TSP problem settings can be changed with variables Test_Distribution, Graph_Size, Testset_Size, and Num_Runs. Change pomo_options_list, dact_options_list, and nlkh_options_list to use different pretrained models.

Test on TSPLIB/National/VLSI datasets

Make LKH first

cd solvers/nlkh
make
# cd ../..
python test_tsplib_nlkh.py

Test energy consumption

You need to install PowerJoular first (which requires administrative privileges).

python test_energy.py

Remember to change Python_Abs_Path and test_script accordingly.

Pretrained models

You can download our pretrained models as provided in the Directory Structure section above. Some of them are obtained from the original authors.

Training

Please check train_pomo.py, train_dact.py, and solvers/nlkh/train.py (need to generate training data with generate_data_nlkh.py first).

Tuning

The Sequential Model-based Algorithm Configuraiton (SMAC) is used to tune LKH:

  • Configuration scenario file: SMAC_scenario.txt
  • Parameter configuration space file: LKH_pcs.txt
  • Solver wrapper of LKH and the execution monitoring tool (Runsolver): the same as in CEPS.
  • Time budgets for tuning LKH: 24 hours for rue/clustered/mix-100, and 96 hours for rue/clustered/mix-500/1000.

Others

Abbreviations Used in the Source Code
Abbr. Meaning
rue random uniform Euclidean
clust cluster(ed)
feat feature
opt(s) option(s)
optim optimum
sol solution

TSP Data Generation

There are two types of TSP data: rue and clustered. For rue, the nodes (cities) are randomly and uniformly distributed within a unit square where the coordinates $x, y \in [0, 1)$.

Acknowledgements

Compared neural solvers

  • DACT, Ma et al., NeurIPS, 2021
  • NeuroLKH, Xin et al., NeurIPS, 2021
  • POMO, Kwon et al., NeurIPS, 2020

Others