Solving Optimization Problems through Fully Convolutional Networks: an Application to the Travelling Salesman Problem

Zhengxuan Ling, Xinyu Tao, Yu Zhang, Xi Chen

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 paper, 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 10 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 a 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.

Introduction

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

Previous attempts to use neural networks for these tasks often struggled because raw numerical parameters are difficult for networks to map directly to solutions. This research proposes a shift in perspective: converting an optimization problem into a visual format that neural networks are naturally adept at processing, thereby achieving instant, non-iterative solutions.

Methodology

The core innovation of this work is an image representation method for the TSP. Instead of feeding raw coordinate vectors into a network, the TSP is rendered 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. This "subtraction" approach—where the network identifies the optimal path from a visible superstructure—proved more effective than requiring the network to "invent" paths in empty space.

The architecture of the proposed FCN model, illustrating the pipeline from image representation to post-processing.

To process these images, a Fully Convolutional Network (FCN) based on the VGGNet architecture is employed. Unlike standard CNNs that output a single label, this FCN performs pixel-wise classification, generating a probability map that distinguishes the "optimal path" from the "background." The network utilizes deconvolution layers and skip connections to concatenate feature maps from multiple pooling stages, capturing both fine details and global structure. Finally, a post-processing algorithm acts as a decoder, tracing the highest-density paths in the probability map to construct a valid, continuous loop that visits every city exactly once.

Experimental Setup

  • Training Data: The model was trained on a custom dataset of randomly generated 10-city TSP instances. The authors found that 9,000 samples were sufficient to achieve convergence and combat overfitting.
  • Labels: Ground-truth optimal paths were generated using a deterministic dynamic programming algorithm.
  • Test Data: The model was evaluated on 480 unseen 10-city TSP samples. To test generalization, additional datasets with 4 to 12 cities were also generated.

Results and Discussion

The FCN demonstrated remarkable efficiency and accuracy. On the 10-city test set, the model found the exact global optimal solution in 86.88% of cases. Furthermore, 95.42% of predicted routes were within 1% of the optimal distance, and 100% were within 5%. The average overall distance ratio was 100.16%, representing a negligible deviation.

Crucially, the inference time is extremely low. A forward pass takes approximately 6.5 to 7 milliseconds on an RTX 2080ti. Including post-processing, the total time is roughly 46ms, offering a significant speedup over exact algorithms as complexity scales.

Visualization of the learning process revealed that the FCN learns in distinct stages: first locating cities, then identifying the outermost edge cities (a common human heuristic), and finally stabilizing on the optimal internal routes. The model also exhibited zero-shot generalization, successfully solving problems with 4 to 12 cities despite being trained only on 10-city instances.

Conclusion and Future Work

This study demonstrates that framing optimization as an image segmentation task allows FCNs to learn the underlying logic of the TSP. While highly effective, the approach faces limitations in extreme edge cases, such as highly concave layouts or dense city clusters that cause pixel overlap. Future work will explore scaling the method to larger TSPs, which may require higher image resolutions or transfer learning to maintain performance without prohibitive computational costs.

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 paper, 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 10 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 a 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 Travelling Salesman Problem}},
  journal = {IEEE Trans. Syst. Man Cybern. Syst.},
  year = {2021},
  url = {https://openreview.net/forum?id=FR3fJS8lve},
}
Figure