Using Reasoning Models to Generate Search Heuristics that Solve Open Instances of Combinatorial Design Problems

📄 arXiv: 2505.23881v1 📥 PDF

作者: Christopher D. Rosin

分类: cs.AI, cs.CL, math.CO

发布日期: 2025-05-29

备注: arXiv admin note: text overlap with arXiv:2501.17725

💡 一句话要点

利用推理模型生成搜索启发式算法，解决组合设计开放问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 组合设计 大语言模型 搜索启发式算法 推理模型 代码生成 开放实例 CPro1

📋 核心要点

  1. 组合设计领域存在大量开放实例，传统方法难以有效生成解决这些实例的搜索启发式算法。
  2. 论文提出CPro1协议，利用具备推理能力的大语言模型迭代生成和优化搜索启发式算法，以解决开放实例。
  3. 实验表明，CPro1成功解决了多个长期存在的组合设计开放实例，并在多个问题上取得了超越现有方法的新成果。

📝 摘要（中文）

本文利用具备推理能力的大语言模型（LLMs），通过迭代生成和优化答案来解决数学和代码生成问题。具体而言，我们将代码生成与推理LLMs应用于组合设计这一数学领域的特定任务。该领域研究各种组合设计，其中许多存在尚未确定其存在的开放实例。我们提出了Constructive Protocol CPro1，它使用LLMs生成搜索启发式算法，从而有可能构建小型开放实例的解决方案。CPro1从特定设计的文本定义和有效性验证器开始，引导LLMs选择和实施策略，同时提供自动超参数调整和执行反馈。CPro1与推理LLMs成功解决了选自2006年《组合设计手册》的16个组合设计问题中的7个长期存在的开放实例，包括Bhaskar Rao设计、对称权重矩阵和平衡三元设计这3个CPro1与非推理LLMs未解决的新实例。它还解决了近期（2025年）文献中的几个问题的开放实例，生成了新的覆盖序列、Johnson团覆盖、删除码和均匀嵌套Steiner四元系统。

🔬 方法详解

问题定义：论文旨在解决组合设计领域中长期存在的开放实例问题。现有方法，尤其是基于非推理LLM的方法，在生成有效的搜索启发式算法方面存在局限性，难以找到这些开放实例的解决方案。

核心思路：论文的核心思路是利用具备推理能力的大语言模型（LLMs）来生成和优化搜索启发式算法。通过迭代地生成、验证和改进算法，LLMs能够逐步逼近开放实例的解决方案。这种方法模仿了人类专家解决问题的过程，即先提出假设，然后验证假设，最后根据验证结果调整假设。

技术框架：CPro1协议包含以下主要模块：1) 问题定义模块：接收组合设计的文本定义和有效性验证器。2) LLM引导模块：引导LLMs选择和实施搜索策略，生成候选的启发式算法。3) 超参数调整模块：自动调整LLMs的超参数，以优化算法的性能。4) 执行反馈模块：提供算法执行的反馈，帮助LLMs改进算法。整个流程是一个迭代的过程，LLMs不断生成、验证和改进算法，直到找到解决方案或达到最大迭代次数。

关键创新：最重要的技术创新点在于利用具备推理能力的大语言模型来生成搜索启发式算法。与传统的基于规则或基于搜索的方法相比，这种方法能够更灵活地适应不同的组合设计问题，并能够利用LLMs的强大推理能力来发现新的解决方案。此外，CPro1协议的自动化超参数调整和执行反馈机制也提高了算法的效率和有效性。

关键设计：论文中没有明确给出关键的参数设置、损失函数、网络结构等技术细节，这些细节可能依赖于所使用的具体LLM。关键的设计在于如何有效地引导LLMs进行推理和搜索，以及如何设计有效的反馈机制来指导LLMs改进算法。超参数调整模块的具体实现方式也可能对算法的性能产生重要影响。这些细节在论文中没有详细描述，属于未知内容。

📊 实验亮点

CPro1与推理LLMs成功解决了选自2006年《组合设计手册》的16个组合设计问题中的7个长期存在的开放实例，包括Bhaskar Rao设计、对称权重矩阵和平衡三元设计这3个CPro1与非推理LLMs未解决的新实例。此外，它还解决了近期（2025年）文献中的几个问题的开放实例，生成了新的覆盖序列、Johnson团覆盖、删除码和均匀嵌套Steiner四元系统。

🎯 应用场景

该研究成果可应用于解决各种组合优化问题，例如资源调度、电路设计、网络优化等。通过自动生成高效的搜索启发式算法，可以显著提高解决这些问题的效率和质量。此外，该方法还可以用于发现新的数学结构和定理，推动组合设计领域的发展。

📄 摘要（原文）

Large Language Models (LLMs) with reasoning are trained to iteratively generate and refine their answers before finalizing them, which can help with applications to mathematics and code generation. We apply code generation with reasoning LLMs to a specific task in the mathematical field of combinatorial design. This field studies diverse types of combinatorial designs, many of which have lists of open instances for which existence has not yet been determined. The Constructive Protocol CPro1 uses LLMs to generate search heuristics that have the potential to construct solutions to small open instances. Starting with a textual definition and a validity verifier for a particular type of design, CPro1 guides LLMs to select and implement strategies, while providing automated hyperparameter tuning and execution feedback. CPro1 with reasoning LLMs successfully solves long-standing open instances for 7 of 16 combinatorial design problems selected from the 2006 Handbook of Combinatorial Designs, including new solved instances for 3 of these (Bhaskar Rao Designs, Symmetric Weighing Matrices, Balanced Ternary Designs) that were unsolved by CPro1 with non-reasoning LLMs. It also solves open instances for several problems from recent (2025) literature, generating new Covering Sequences, Johnson Clique Covers, Deletion Codes, and a Uniform Nested Steiner Quadruple System.