Solving Optimization Problems Through Fully Convolutional Networks: An Application to the Traveling Salesman Problem

Zhengxuan Ling, Xinyu Tao, Yu Zhang, Xi Chen

Here is a summary of the paper:

TL;DR

This paper introduces a novel approach to solving the NP-hard Traveling Salesman Problem (TSP) by framing it as an image segmentation task. By converting city coordinates and all possible paths into a 2D image, the authors successfully train a Fully Convolutional Network (FCN) to predict the optimal route in milliseconds, demonstrating that deep learning can map optimization parameters directly to high-quality solutions without iterative searching.

What Problem Does This Paper Address?

While optimization algorithms are the mathematical engine behind training deep neural networks, the reverse application—using deep learning to solve complex optimization problems—remains relatively unexplored. Traditional solvers for NP-hard problems like the TSP rely on iterative search strategies (such as branch-and-bound or genetic algorithms). These are computationally expensive and must restart from scratch for every new problem instance.

Previous attempts to use neural networks for these tasks often failed because the raw numerical parameters of optimization problems are difficult for networks to map directly to solutions. This paper asks: can we convert an optimization problem into a visual format that neural networks are naturally good at processing to achieve instant, non-iterative solutions?

Methods

The core innovation is an image representation method for the TSP. Instead of feeding raw coordinate vectors into a network, the authors render the TSP as a 224x224 RGB image. Cities are plotted as distinct pixel blocks, and all possible paths between them are drawn as lines, forming a fully connected graph.

To process this, they use a Fully Convolutional Network (FCN) based on the VGGNet architecture. Unlike standard CNNs that output a single image-level label (e.g., "cat"), this FCN performs pixel-wise classification. It outputs a probability map indicating whether each pixel belongs to the "optimal path" or the "background." To capture both fine details and global structure, the network uses deconvolution layers that concatenate feature maps from multiple pooling stages.

Finally, a post-processing algorithm acts as a decoder. It traces the highest-density paths in the FCN's output probability map to construct a valid, continuous loop that visits every city exactly once, ensuring the strict constraints of the TSP are met.

Datasets

  • Training Data: A custom dataset of randomly generated 10-city TSP instances. The authors generated up to 21,000 samples, dynamically adding batches of 3,000 during training to combat overfitting (ultimately finding 9,000 samples to be sufficient).
  • Labels: Ground-truth optimal paths were generated using a deterministic dynamic programming algorithm.
  • Test Data: 480 unseen 10-city TSP samples. Additional datasets of 4 to 12 cities were generated to test the model's generalization capabilities.

Key Insights and Ideas

  • "Subtraction" is easier than "Addition": Providing the network with a fully connected graph (all possible paths drawn) works vastly better than just providing a scatter plot of cities. The network performs better when it can "subtract" bad paths from a visible superstructure rather than having to "invent" lines in empty space.
  • Interpretable Learning Stages: By visualizing the FCN's output during training, the authors found the network learns in distinct, human-like stages. It starts by locating cities, then outlines the outermost edge cities (a common human heuristic), explores internal paths, and finally stabilizes on the optimal route.
  • Zero-Shot Generalization: Even though the network was trained exclusively on 10-city problems, it successfully generalized to problems with 4 to 12 cities without retraining. This suggests the FCN actually learned the underlying concept of the TSP rather than just memorizing 10-node patterns.

Key Results

  • High Accuracy: On the 10-city test set, the FCN found the exact global optimal solution in 86.88% of cases.
  • Near-Optimal Guarantees: 95.42% of the predicted routes were within 1% of the optimal distance, and 100% were within 5% of the optimal distance. The average overall distance ratio was 100.16% (equivalent to only a 160m deviation per 100km).
  • Millisecond Inference: Once trained, the FCN forward pass takes only ~6.5 to 7 milliseconds on an RTX 2080ti. Even with the post-processing algorithm, total time is around 46ms for 10 cities, offering massive speedups over exact algorithms as complexity scales, without the need for iterative searching.

Limitations and Future Work

  • Extreme Edge Cases: The FCN struggles with highly atypical TSP layouts, such as extremely concave path loops or instances where multiple cities are clustered very close together (causing paths to overlap and blur in the image representation).
  • Scale Limitations: The study is limited to small-scale TSPs (up to 12 cities). Scaling this to hundreds or thousands of cities would require massive image resolutions to prevent pixel overlap, which would be computationally prohibitive for standard FCNs.
  • Reliance on Post-Processing: The neural network does not strictly enforce TSP constraints (like visiting every city exactly once) on its own; it relies heavily on the post-processing algorithm to fix broken or redundant paths in the probability map.
  • Future Work: The authors suggest using transfer learning with small amounts of data to further improve generalization to different problem sizes.

Summary updated

Abstract

In the new wave of artificial intelligence, deep learning is impacting various industries. As a closely related area, optimization algorithms greatly contribute to the development of deep learning. But the reverse applications are still insufficient. Is there any efficient way to solve certain optimization problem through deep learning? The key is to convert the optimization to a representation suitable for deep learning. In this article, a traveling salesman problem (TSP) is studied. Considering that deep learning is good at image processing, an image representation method is proposed to transfer a TSP to an image. Based on samples of a ten city TSP, a fully convolutional network (FCN) is used to learn the mapping from a feasible region to an optimal solution. The training process is analyzed and interpreted through stages. A visualization method is presented to show how an FCN can understand the training task of a TSP. Once the training is completed, no significant effort is required to solve a new TSP and the prediction is obtained on the scale of milliseconds. The results show good performance in finding the global optimal solution. Moreover, the developed FCN model has been demonstrated on TSP’s with different city numbers, proving excellent generalization performance.
BibTeX
@article{ling2021solving,
  author = {Zhengxuan Ling and Xinyu Tao and Yu Zhang and Xi Chen},
  title = {{Solving Optimization Problems Through Fully Convolutional Networks: An Application to the Traveling Salesman Problem}},
  journal = {IEEE Trans. Syst. Man Cybern. Syst.},
  year = {2021},
  url = {https://openreview.net/forum?id=FR3fJS8lve},
}

Loading related content...

Figure