Linear Function Approximation as a Resource Efficient Method to Solve the Travelling Salesman Problem


  • Rolan Guang Mentor High School
  • Sajad Khodadian



Linear Function Approximation, Travelling Salesman Problem, Combinatorial Optimization, Machine Learning, Reinforcement Learning


This paper presents an approach to combinatorial optimization problems using linear function approximation (LFA) to solve the Travelling Salesman Problem (TSP). We create a reinforcement learning model in which we parameterize our policy using linear function approximation instead of the more commonly used neural networks. We then evaluated our models based on two factors: training time and optimality. When we compared our results with a state-of-the-art neural network solver, we found that our model was able to solve the TSP accurately while using drastically less computational resources and time to train than the neural network algorithm (Kool et al., 2019).


Download data is not yet available.

References or Bibliography

Applegate, D., Bixby, R., Chvatal, V., and Kool, W. (2003). Concorde tsp solver.

Bello, I., Pham, H., Le, Q. V., Norouzi, M., and Bengio, S. (2017). Neural combinatorial optimization with reinforcement learning.

Cappart, Q., Chételat, D., Khalil, E., Lodi, A., Morris, C., and Velickovíc, P. (2021). Combinatorial optimization and reasoning with graph neural networks.

Cappart, Q., Moisan, T., Rousseau, L.-M., Pr ́emont-Schwarz, I., and Cire, A. (2020). Combining reinforcement learning and constraint programming for combinatorial optimization.

Drori, I., Kharkar, A., Sickinger, W. R., Kates, B., Ma, Q., Ge, S., Dolev, E., Dietrich, B., Williamson, D. P., and Udell, M. (2020). Learning to solve combinatorial optimization problems on real-world graphs in linear time.

Gurobi Optimization, LLC (2021). Gurobi Optimizer Reference Manual.

Joshi, C. K., Laurent, T., and Bresson, X. (2019). An efficient graph convolutional network technique for the travelling salesman problem.

Kool, W., van Hoof, H., and Welling, M. (2019). Attention, learn to solve routing problems!

Mazyavkina, N., Sviridov, S., Ivanov, S., and Burnaev, E. (2020). Reinforcement learning for combinatorial optimization: A survey.

Mulder, S. and Wunsch, D. (2003). Million city traveling salesman problem solution by divide and conquer clustering with adaptive resonance neural networks.



How to Cite

Guang, R., & Khodadian, S. (2022). Linear Function Approximation as a Resource Efficient Method to Solve the Travelling Salesman Problem. Journal of Student Research, 10(4).



HS Research Projects