PaperlayerView exact revision on arXiv

Source-linked AI summary

The Transformer Network for the Traveling Salesman Problem

Xavier Bresson, Thomas Laurent

arXiv:2103.03012v1cs.LG

TL;DR

TSP research asks whether deep learning can learn better heuristics from data than hand-crafted rules for an NP-hard problem. This paper adapts the Transformer to TSP, trains it with reinforcement learning, and decodes tours with beam search. It reports improved performance over recent learned heuristics, with optimal gaps of 0.004% for TSP50 and 0.39% for TSP100.

  • Problem

    The paper asks whether deep learning can learn better heuristics from data than hand-crafted rules for NP-hard combinatorial problems whose algorithms can take years to develop.

    Source: §2 · p. 2

  • Method

    The method adapts the Transformer to translate a set of 2D points into a minimal-length tour, trains with reinforcement learning, and uses beam search for decoding.

    Source: §3 · p. 3, §5 · p. 6

  • Results

    The learned method improves over recent learned heuristics, with optimal gaps of 0.004% for TSP50 and 0.39% for TSP100.

    Source: §7 · p. 7

  • Takeaways & Limitations

    The authors conclude that a Transformer architecture can successfully solve the TSP combinatorial-optimization problem and improve on recent learned heuristics.

    Source: §7 · p. 7

    Traditional solvers such as Concorde and LKH-3 still outperform learning solvers in performance and generalization, while scaling beyond n = 100 is challenging because of limited GPU memory and O(n^2) Transformer and autoregressive-decoding complexity.

    Source: §7 · p. 7

Abstract

from arXiv · show

The Traveling Salesman Problem (TSP) is the most popular and most studied combinatorial problem, starting with von Neumann in 1951. It has driven the discovery of several optimization techniques such as cutting planes, branch-and-bound, local search, Lagrangian relaxation, and simulated annealing. The last five years have seen the emergence of promising techniques where (graph) neural networks have been capable to learn new combinatorial algorithms. The main question is whether deep learning can learn better heuristics from data, i.e. replacing human-engineered heuristics? This is appealing because developing algorithms to tackle efficiently NP-hard problems may require years of research, and many industry problems are combinatorial by nature. In this work, we propose to adapt the recent successful Transformer architecture originally developed for natural language processing to the combinatorial TSP. Training is done by reinforcement learning, hence without TSP training solutions, and decoding uses beam search. We report improved performances over recent learned heuristics with an optimal gap of 0.004% for TSP50 and 0.39% for TSP100.

1 Traditional TSP Solvers

Traditional TSP solvers trade guaranteed optimality for tractability: exact methods become intractable as instances grow, while heuristics offer faster approximate solutions. The section surveys exact solvers and prominent heuristic approaches.

1 Traditional TSP Solvers

  • Heuristics trade optimality for computational efficiency, using problem-specific rules whose quality is characterized by an approximate ratio.Their complexity is polynomial, unlike exact methods that become intractable as n grows.Source: §1 · p. 1
  • Exact TSP methods include exhaustive search, dynamic programming, and integer programming; the dynamic-programming algorithm in [16] becomes intractable for n > 40.Concorde combines linear integer programming, cutting planes, and branch-and-bound and is described as the fastest exact solver for large instances.Source: §1 · p. 1
  • Christofides [7] has O(n^2 log n) complexity and guarantees a tour within a factor 3/2 of optimum, while farthest insertion has an approximation ratio of 2.43.Farthest insertion is identified as the best insertion algorithm in practice.Source: §1 · p. 2
  • OR-Tools combines simulated annealing, greedy descent, and tabu search with local-search refinement; 2-Opt improves tours by replacing two edges.The cited 2-Opt approximation ratio is 4/√n.Source: §1 · p. 2
  • LKH-3 [18], an extension of LKH and LKH-2 based on 2-Opt/3-Opt with minimum-spanning-tree edge candidates, is presented as the leading heuristic and handles multiple TSP-type problems.The 2-Opt discussion also notes that its search may require many tested node-pair moves before reaching a local minimum.Source: §1 · p. 2

2 Neural Network Solvers

The section frames whether neural networks can learn better combinatorial heuristics than hand-crafted rules, and surveys supervised and reinforcement-learning approaches to TSP. These approaches differ in their representations, training signals, and tour-construction strategies.

2 Neural Network Solvers

  • Neural approaches learn combinatorial algorithms with supervision or reinforcement learning, addressing whether data can yield better heuristics than hand-crafted rules.The motivation is that developing algorithms for NP-hard problems can take years and many industry problems are combinatorial.Source: §2 · p. 2
  • PointerNets [39] use recurrent encoders and attention-based autoregressive decoding, trained with approximate TSP solutions; PointerNets+RL [5] removes the need for those supervised solutions by using tour length as reward.The RL work studies reinforce and active search.Source: §2 · p. 2
  • Order-invariant PointerNets+RL [33] make the encoder permutation-invariant, addressing the original PointerNets' dependence on input-city order.The original model otherwise requires random input permutations to learn this invariance.Source: §2 · p. 2
  • S2V-DQN [9] takes a graph and partial tour as input and uses reinforcement learning with replay memory to estimate next-node values and encourage farthest-node insertion.Its output is a state-valued Q function for selecting the next node.Source: §2 · p. 2
  • Other approaches predict tour edges or fractional solutions, use beam search to obtain feasible tours, or combine graph networks with Monte Carlo tree search to explore next-node candidates.GraphConvNet [22] predicts edge probabilities in a single pass; the multiple-salesman network [23] is non-autoregressive, while transformer models [25, 11] decode sequentially.Source: §2 · pp. 2–3

3 Proposed Architecture

The proposed method adapts Transformers by treating TSP as translation from a set of 2D points to a minimal-length tour, and trains with reinforcement learning rather than TSP solution labels. Its autoregressive decoder selects the next unvisited city through four stages.

3 Proposed Architecture

  • The model casts TSP as translation from a source set of 2D points to a target tour sequence with minimal length, and trains by reinforcement learning without TSP training solutions.Tour length is the reward; the baseline is updated when the trained network improves it on random TSP instances.Source: §3 · p. 3
  • The encoder is a standard multi-head Transformer with residual connections and batch normalization instead of layer normalization, with O(n^2) memory/speed complexity.A randomly initialized start token is also introduced.Source: §3 · pp. 3–4
  • Autoregressive decoding predicts one city at a time through four steps, beginning by encoding the previously selected city with positional encoding.The positional encoding orders nodes in the tour; its even and odd dimensions use sine and cosine, respectively.Source: §3 · pp. 4–5
  • The decoder prepares its query with self-attention over the partial tour, then queries candidate cities among those not yet visited.The self-attention step has O(t) memory/speed complexity at decoding step t, and the candidate-query stage has O(n) complexity per recursive step.Source: §3 · p. 5
  • A final single-head attention produces a distribution over unvisited cities; training samples the next city, while inference selects the maximum-probability city greedily.The final step has O(n) memory/speed complexity; the visited-city mask is combined using a Hadamard product.Source: §3 · p. 5

4 Architecture Comparison

The proposed model keeps the Transformer encoder used by earlier neural TSP methods but changes how the decoder forms and starts its query. Its query summarizes the partial tour through self-attention, and a new token initializes decoding.

4 Architecture Comparison

  • The comparison says both TSP and NLP encode output order with positional encodings, while TSP input order is irrelevant; it also contrasts batch normalization for the TSP encoder with layer normalization for its autoregressive decoder.The passage attributes the normalization choices to encoding all cities together versus decoding one vector at a time.Source: §4 · p. 5
  • Unlike [25] and, the proposed decoder forms its query with self-attention over all cities in the partial tour.[25] uses the first and last cities plus a global city representation; uses the last three cities.Source: §4 · pp. 5–6
  • A learned-start token z ∈ R2 lets the model begin decoding by querying all cities with self-attention, whereas [25] and initialize from random or encoded representations of selected cities.[25] uses the mean encoding representation and a random token for the first and current cities; uses a random token for the last three cities.Source: §4 · p. 6

5 Decoding Technique

The section formulates TSP decoding as maximizing the probability of a city-index sequence, then considers approximate sequential search because exhaustive search is intractable. Greedy decoding is linear-time, while beam search retains multiple candidate paths.

5 Decoding Technique

  • The decoding objective is to find the city-index sequence that maximizes the TSP sequence probability given the city set.The sequence probability is factorized into successive conditional probabilities for autoregressive city selection.Source: §5 · p. 6
  • Exhaustive search is intractable at O(n!), so the section considers approximate decoding.Greedy search selects the highest-probability next city at each step.Source: §5 · p. 6
  • Greedy decoding has linear complexity O(n).Source: §5 · p. 6
  • Beam search is a breadth-first search with limited width B, retaining the Top-B probabilities as candidate paths are extended.With B = 1, decoding is greedy; with B > 1, each step extends the existing beams and keeps the Top-B probabilities.Source: §5 · p. 6
  • Beam search and Monte Carlo Tree Search are described as improving results over greedy search, with complexity O(Bn).B denotes the number of beams or explored paths.Source: §5 · p. 6

6 Numerical Experiments

The experiments compare the proposed architecture with existing methods on 10,000 TSP50 and TSP100 test instances. The section identifies the hardware and timing measures used for the comparison.

6 Numerical Experiments

  • The test set contains 10k TSP50 and TSP100 instances, and the comparison includes Concorde and Transformers.Concorde ran on an Intel Xeon Gold 6132 CPU; Transformers ran on an Nvidia 2080Ti GPU.Source: §6 · p. 6
  • Figure 4 presents experimental complexity for inference time on a single TSP.Source: §6 · p. 6, Figure 4 · p. 7
  • Table 1 reports total time for 10k TSP in parallel and inference time for one TSP in serial; starred results come from other papers.Source: Table 1 · p. 7

7 Discussion

The discussion reports that the Transformer improves recent learned heuristics, while traditional solvers retain advantages in performance and generalization. It identifies scaling and solver integration as future directions.

7 Discussion

  • The Transformer improves recent learned heuristics, with optimal gaps of 0.004% for TSP50 and 0.39% for TSP100.The authors state that this work focused essentially on the architecture.Source: §7 · p. 7
  • Group beam search and MCTS are proposed as sampling developments, and 2-Opt intermediate rewards have shown improvements over waiting for the completed-tour reward.The tour-length global reward requires waiting until tour construction ends.Source: §7 · p. 7
  • Concorde and LKH-3 still outperform learning solvers in performance and generalization, although neural solvers offer faster inference.The comparison gives neural solvers O(n2L) inference versus O(n2.5b(n)) for branch-and-bound, where b(n) is the number of branches explored.Source: §7 · p. 7
  • Scaling to TSP sizes n > 100 is a proposed next step, but GPU memory limits and O(n2) Transformer and autoregressive-decoding complexity make it challenging.Source: §7 · p. 7
  • The authors propose testing harder TSP/routing settings where traditional solvers provide weaker solutions or take a long time, and other problems where Gurobi cannot be used.Source: §7 · p. 8
  • A further direction is to use learning to improve branch-and-bound, moving beyond imitation of human-engineered branching heuristics toward learned novel heuristics.Variable selection is critical to search efficiency; Strong Branching is described as high-quality but expensive.Source: §7 · p. 8

8 Conclusion

The conclusion places deep learning for combinatorial optimization in an early stage, despite traditional solvers still providing better solutions. It anticipates continued research and possible software combining continuous, discrete, and learning techniques.

8 Conclusion

  • Traditional solvers still provide better solutions than learning models.Source: §8 · p. 8
  • The authors characterize deep learning for combinatorial optimization as a newer research area than traditional solvers, which have been studied since the 1950s.Source: §8 · p. 8
  • The conclusion anticipates growth in this research as companies use combinatorial problems in assignment, routing, planning, and scheduling.It also notes possible software combining continuous and discrete optimization with learning techniques.Source: §8 · p. 8

Related papers

Loading 2103.03012v1…