LLM2D
W2SAT:从加权文字关联图学习生成SAT实例
W2SAT: Learning to generate SAT instances from Weighted Literal Incidence Graphs
发布日期: 9/25/2024
arXiv ID: oai:arXiv.org:2302.00272v2

摘要

布尔可满足性 (SAT) 问题作为理论计算机科学中一个引人注目的 NP 完全问题,在广泛的计算相关应用中扮演着核心角色。在多种场景下,对 SAT 求解器的利用和优化需要大量的工业级高质量 SAT 实例,然而,现实世界中这类实例非常有限。为了解决数据不足问题,本文提出了一种名为 W2SAT 的框架,通过隐式地从给定的现实世界/工业实例中学习内在结构和属性来生成 SAT 公式。为此,我们引入了名为加权文字关联图 (WLIG) 的新型 SAT 表示,该表示具有强大的表示能力和泛化能力,并且可以通过专门的基于学习的图生成模型进行有效地生成。然后将从 WLIG 解码到 SAT 问题建模为寻找重叠团,并使用一种名为最优权重覆盖 (OWC) 的新型爬山优化方法。实验表明,与以前的方法相比,我们提出的 WLIG 诱导方法在图指标、效率和可扩展性方面具有优越性。此外,我们还讨论了基于图的 SAT 生成在现实世界应用中的局限性,特别是在利用生成的实例进行 SAT 求解器参数调优时,并提出了一些潜在的方向。