TSP_exp

Case Study I: Neural Solver for Traveling Salesman Problem with Extra Constraints

The Traveling Salesman Problem (TSP) is a classic NP-hard problem. The standard TSP aims at finding a cycle visiting all cities with minimal length. Beyond standard TSP, in this case study, we develop a neural solver for TSP with extra constraints using LinSATNet layer.

TSP-SE and TSP-PRI

We consider 1) TSP with starting and ending cities constraint (TSP-SE); 2) TSP with priority constraint (TSP-PRI).

Left: TSP-SE: one needs to find the shortest tour starting from the black node, visiting other nodes exactly once, and ending in the orange node; Right: TSP-PRI: besides the starting and ending nodes, the priority node (i.e. red one) has to be visited within 5 steps starting from the black node.

In TSP-SE, the salesman is given a starting city $s$ and an ending city $e$. The salesman needs to find the shortest tour starting from city $s$, visiting other cities exactly once, and ending in city $e$. TSP-SE can be converted to standard TSP by adding a dummy node. The distance from the dummy node to starting and ending nodes is 0 and the distance to other nodes is infinity. Then we can use start-of-the-art methods for standard TSP to solve TSP-SE.

In TSP-PRI, besides the starting and ending cities, the salesman is also given a priority city $p$ that has to be visited within $m$ steps starting from beginning. Converting TSP-PRI to standard TSP is non-trivial, making it hard to use standard solvers to solve TSP-PRI.

Constraint Formulation with LinSATNet

Given the starting and ending cities $s, e \in {1, ... , n}$. The distance matrix $\mathbf{D}$ records the distances between city pairs. We use $\mathbf{X} \in {0, 1}^{n \times n}$ as our decision variable, where $X_{i, k} = 1$ indicates city $i$ is the $k$-th visited city in the tour. Then TSP-SE can be formulated with the following objective function and constraints:

$$\min_\mathbf{X}\sum_{i = 1}^n\sum_{j = 1}^nD_{i,j}\sum_{k = 1}^{n-1}X_{i, k}X_{j, k+1}$$

s.t.

$$\sum_{i = 1}^nX_{i,k}=1, \forall k \in {1, ... , n}$$

$$\sum_{k = 1}^nX_{i,k}=1, \forall i \in {1, ... , n}$$

$$X_{s,1} = 1, X_{e,n} = 1$$

$$X_{i, k} \in {0, 1}, \forall i,k \in {1, ... , n}$$

For TSP-PRI, we need one more constraint to ensure city $p$ is visited within the first $m$ steps: $$\sum_{k = 1}^{m + 1}X_{p, k} = 1$$

Note that in this formulation, the objective is quadratic w.r.t. $\mathbf{X}$, thus it is hard for a MIP solver to get a satisfactory solution within reasonable time limit. However, if we relaxe the binary constraint to $[0,1]$, all other constraints can be enforced with the equality constraint $\mathbf{Ex} = \mathbf{f}$ of LinSATNet, where $\mathbf{x}$ is the flattened $\mathbf{X}$.

Therefore, we input the TSP instance into a Transformer and let it output the pre-projected matrix $\mathbf{Y} \in \mathbb{R}^{n \times n}$. Then $\mathbf{Y}$ is flattened into a $n^2$-dimensional vector and projected into $\tilde{\mathbf{X}}$ via LinSATNet to enforce all the aforementioned constraints. In training, the objective with continuous $\tilde{\mathbf{X}}$ as the decision variable is used as the unsupervised loss. For inference, we first output $\tilde{\mathbf{X}}$ and view it as the marginal distributions of the binary $\mathbf{X}$. We perform beam search on it to get $\mathbf{X}$ in post-processing.

Reproducibility

To train the model for TSP-SE, run:

python run_train.py --task StartEnd

The checkpoints and log file will be saved in outputs/StartEnd_20_timestamp. After training, you can evaluate the trained model by running:

python run_evaluate.py --model_dict outputs/StartEnd_20_timestamp --test_epoch 50 --test_dataset datasets/tsp20_test_seed1234.pkl

The checkpoint epoch-50 will be evaluated on the test dataset and the result will be saved in the same directory. The test set here is generated by the same process as https://github.com/wouterkool/attention-learn-to-route and we treat the first node in each sequence as starting node and last node as ending node.

To run experiments for TSP-PRI, run:

python run_train.py --task Priority

and evaluate it with similar process.