Abstract
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.
Abstract (translated)
大语言模型（LLMs）是一种基于文本输入的深度学习模型，旨在生成文本。尽管研究人员已经为更复杂的任务，如代码生成和一般推理开发了这些模型，但很少有人研究过LLMs如何应用于组合问题。在本文中，我们研究了LLMs解决旅行推销员问题（TSP）的潜力。通过利用GPT-3.5涡轮，我们进行了各种实验，包括零散在上下文中学习、少量在上下文中学习和连锁思维（CoT）。因此，我们微调了GPT-3.5涡轮以解决特定问题大小，并使用一系列不同的实例大小对其进行了测试。微调后的模型在大小与训练实例相同的问题上表现出优异的性能，并且对较大问题表现出良好的泛化能力。此外，为了在不产生额外训练成本的情况下提高微调模型的性能，我们还采用了一种自集成方法来提高解决方案的质量。
URL
https://arxiv.org/abs/2405.01997
