# Exploring Combinatorial Problem Solving with Large Language Models: A Case Study on the Travelling Salesman Problem Using GPT-3.5 Turbo

arXiv: https://arxiv.org/abs/2405.01997 · HTML: https://mlsanity.com/paper/2405.01997/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 2 references that are in the map.
- First posted on arXiv 3 May 2024.

## Builds on (most cited first, 2 of 2)

- [Finetuned Language Models Are Zero-Shot Learners](https://mlsanity.com/paper/2109.01652/) (2021)
- [Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models](https://mlsanity.com/paper/2206.04615/) (2022)

## Built on by (most cited first, 8 of 8)

- [Self-Guiding Exploration for Combinatorial Problems](https://mlsanity.com/paper/2405.17950/) (2024)
- [Visual Reasoning and Multi-Agent Approach in Multimodal Large Language Models (MLLMs): Solving TSP and mTSP Combinatorial Challenges](https://mlsanity.com/paper/2407.00092/) (2024)
- [Bridging Large Language Models and Optimization: A Unified Framework for Text-attributed Combinatorial Optimization](https://mlsanity.com/paper/2408.12214/) (2024)
- [ConstraintBench: Benchmarking LLM Constraint Reasoning on Direct Optimization](https://mlsanity.com/paper/2602.22465/) (2026)
- [Large Language Models in Operations Research: Methods, Applications, and Challenges](https://mlsanity.com/paper/2509.18180/) (2025)
- [ACCORD: Autoregressive Constraint-satisfying Generation for COmbinatorial Optimization with Routing and Dynamic attention](https://mlsanity.com/paper/2506.11052/) (2025)
- [MARIC: Multi-Agent Reasoning for Image Classification](https://mlsanity.com/paper/2509.14860/) (2025)
- [Budget-Efficient Automatic Algorithm Design via Code Graph](https://mlsanity.com/paper/2605.10598/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) are deep learning models designed to generate text based on textual input. Although researchers have been developing these models for more complex tasks such as code generation and general reasoning, few efforts have explored how LLMs can be applied to combinatorial problems. In this research, we investigate the potential of LLMs to solve the Travelling Salesman Problem (TSP). Utilizing GPT-3.5 Turbo, we conducted experiments employing various approaches, including zero-shot in-context learning, few-shot in-context learning, and chain-of-thoughts (CoT). Consequently, we fine-tuned GPT-3.5 Turbo to solve a specific problem size and tested it using a set of various instance sizes. The fine-tuned models demonstrated promising performance on problems identical in size to the training instances and generalized well to larger problems. Furthermore, to improve the performance of the fine-tuned model without incurring additional training costs, we adopted a self-ensemble approach to improve the quality of the solutions.