LLM2D
使用LLMs提取问题结构以优化SAT局部搜索
Extracting Problem Structure with LLMs for Optimized SAT Local Search
作者: Andr\'e Schidler, Stefan Szeider
发布日期: 2/5/2025
arXiv ID: oai:arXiv.org:2501.14630v2

摘要

arXiv:2501.14630v2 通知类型: 修订 摘要:局部搜索预处理通过提供高质量的初始点使冲突导向字句学习(CDCL)求解器更快,并且现代SAT求解器已经将其纳入预处理步骤中。然而,这些工具依赖于基本策略,而这些策略忽略了问题中的结构性模式。我们提出了一种方法,该方法应用大型语言模型(LLMs)来分析基于Python的编码代码。这揭示了问题转换为SAT中的隐藏结构性模式。我们的方法会自动生成针对这些模式的专业局部搜索算法,并利用它们生成强大的初始分配。这种方法适用于同一编码类型的任何问题实例。我们的测试结果显示了令人鼓舞的结果,与基线预处理系统相比,实现了更快的求解时间。