Using Code Generation to Solve Open Instances of Combinatorial Design Problems

📄 arXiv: 2501.17725v1 📥 PDF

作者: Christopher D. Rosin

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

发布日期: 2025-01-29

💡 一句话要点

CPro1协议利用代码生成解决组合设计开放问题，成功构造六种设计。

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

关键词: 组合设计 代码生成 大型语言模型 自动化 开放问题

📋 核心要点

  1. 组合设计领域存在大量开放实例，传统方法难以有效解决这些问题，需要新的探索方法。
  2. CPro1协议利用LLM生成代码来构造组合设计，通过自动化的策略选择和代码实现，探索多种解决方案。
  3. 实验表明，CPro1成功解决了六种组合设计的开放实例，证明了该方法在解决此类问题上的有效性。

📝 摘要（中文）

组合设计手册收录了多种组合设计类型，并列出了尚未确定其存在的开放实例。我们开发了一种构造性协议CPro1，它使用大型语言模型（LLM）生成代码来构造组合设计，并解决其中一些开放实例。该协议从特定类型设计的定义和一个可靠验证提议设计是否有效的验证器开始。LLM选择策略并在代码中实现它们，脚手架提供自动超参数调整和使用验证器的执行反馈。虽然大多数生成的代码都失败了，但通过生成大量候选方案，该协议可以自动探索各种标准方法（例如，模拟退火、遗传算法）并试验各种变体（例如，成本函数）以找到成功的方法。在16种不同类型的设计上进行测试，CPro1构造了6种设计的开放实例的解决方案：对称和斜对称称重矩阵、等距置换阵列、填充阵列、平衡三元设计和佛罗伦萨矩形。

🔬 方法详解

问题定义：论文旨在解决组合设计中存在的开放实例问题，即某些特定类型的组合设计是否存在。现有方法，如人工搜索或特定算法，在面对复杂或未知的组合设计时效率低下，难以找到有效的构造方法。这些方法通常需要大量的领域知识和手动调整，并且难以自动化。

核心思路：论文的核心思路是利用大型语言模型（LLM）的代码生成能力，自动化地探索各种可能的组合设计构造方法。通过定义设计类型和验证器，LLM可以生成代码来尝试不同的策略，并根据验证器的反馈进行调整，从而找到满足要求的组合设计。

技术框架：CPro1协议的技术框架主要包括以下几个阶段：1) 定义组合设计类型和验证器；2) LLM选择策略并生成相应的代码；3) 使用脚手架进行自动超参数调整；4) 执行生成的代码并使用验证器进行验证；5) 根据验证结果进行迭代和优化。整个过程通过自动化执行和反馈循环，探索各种可能的解决方案。

关键创新：该方法最重要的创新点在于利用LLM的代码生成能力，将组合设计问题转化为代码生成问题，从而可以自动化地探索各种可能的解决方案。与传统方法相比，该方法不需要人工干预，可以自动适应不同的组合设计类型，并且可以通过调整LLM的策略和超参数来提高搜索效率。

关键设计：CPro1协议的关键设计包括：1) LLM的策略选择机制，用于选择不同的组合设计构造策略；2) 代码生成模块，用于将策略转化为可执行的代码；3) 验证器，用于验证生成的组合设计是否满足要求；4) 超参数调整模块，用于自动调整LLM的超参数，以提高搜索效率。此外，成本函数的设计也至关重要，它指导LLM朝着正确的方向搜索。

🖼️ 关键图片

fig_0

📊 实验亮点

CPro1协议在16种不同类型的组合设计上进行了测试，成功解决了6种设计的开放实例，包括对称和斜对称称重矩阵、等距置换阵列、填充阵列、平衡三元设计和佛罗伦萨矩形。这些结果表明，CPro1协议在解决组合设计开放问题上具有显著的优势。

🎯 应用场景

该研究成果可应用于组合数学、密码学、编码理论等领域，为解决实际问题提供新的思路和方法。例如，可以利用该方法设计新的密码算法、构造更有效的纠错码等。此外，该方法还可以推广到其他类型的组合优化问题，具有广泛的应用前景。

📄 摘要（原文）

The Handbook of Combinatorial Designs catalogs many types of combinatorial designs, together with lists of open instances for which existence has not yet been determined. We develop a constructive protocol CPro1, which uses Large Language Models (LLMs) to generate code that constructs combinatorial designs and resolves some of these open instances. The protocol starts from a definition of a particular type of design, and a verifier that reliably confirms whether a proposed design is valid. The LLM selects strategies and implements them in code, and scaffolding provides automated hyperparameter tuning and execution feedback using the verifier. Most generated code fails, but by generating many candidates, the protocol automates exploration of a variety of standard methods (e.g. simulated annealing, genetic algorithms) and experimentation with variations (e.g. cost functions) to find successful approaches. Testing on 16 different types of designs, CPro1 constructs solutions to open instances for 6 of them: Symmetric and Skew Weighing Matrices, Equidistant Permutation Arrays, Packing Arrays, Balanced Ternary Designs, and Florentine Rectangles.