Self-Guiding Exploration for Combinatorial Problems

大型语言模型（LLMs）已成为解决各种领域的推理任务的关键，包括算术、常识和符号推理。它们利用探索思想、分解和细化等提示技术来有效地导航和解决复杂任务。尽管取得了这些进展，但LLMs在组合问题（CPs）上的应用仍未得到充分探索，而CPs以其NP难度和在物流和资源管理中的关键作用而闻名。为了填补这一空白，我们引入了一种新的提示策略：自我引导探索（SGE），旨在增强解决CPs的性能。SGE可以自主操作，为每个CP任务生成多个思路轨迹。然后将这些轨迹分解为可执行的子任务，按顺序执行它们，并对结果进行细化以确保最佳结果。我们的研究是第一个将LLMs应用于广泛的CPs，并证明SGE在CP优化性能方面比现有提示策略提高了27.84%以上。此外，在其他推理任务（算术、常识和符号）中，SGE的准确性比最佳现有结果高2.46%。

论文旨在探讨如何使用大型语言模型（LLMs）解决组合优化问题（CPs），并且提出了一种新的提示策略Self-Guiding Exploration（SGE）。

SGE是一种自主生成多个思路轨迹、将其分解为可行的子任务并进行逐个执行和优化的提示策略。论文的关键思路是将LLMs应用于组合优化问题，并提出了一种新的提示策略。

论文是第一篇将LLMs应用于广泛的组合优化问题的研究，并且证明了SGE在CP优化性能方面的表现优于现有的提示策略27.84％以上。此外，SGE在算术、常识和符号等其他推理任务中的准确性比现有最佳结果高2.46％。论文使用了多个数据集进行实验，并且开源了代码。

最近在这个领域中，也有一些相关的研究，如《Solving Combinatorial Optimization Problems using Reinforcement Learning》、《A Hybrid Algorithm for Combinatorial Optimization Problems》等。