arXiv:2409.18778cs.LGcs.AI2024-09NeurIPS被引 1

用快速检测核心的方法生成难解的布尔问题,提升求解器预测精度。

HardCore Generation: Generating Hard UNSAT Problems for Data Augmentation

  • 基于图神经网络快速识别问题核心,提升生成效率。
  • 生成的问题保持原始难题特征,且求解难度高。
  • 适用于需要真实数据增强的SAT求解器性能预测场景。

高效判断布尔方程可满足性(即SAT问题)在诸多工业应用中至关重要。近年来,深度学习方法为提升SAT求解带来了新可能,但主要瓶颈在于缺乏大规模、真实的训练数据。现有公开数据集多为随机生成或仅含少量来自不同问题家族的样本,难以支持深度学习模型的有效训练。为此,研究者开始探索生成技术以创建更贴近实际应用的SAT问题。然而,现有方法或无法生成足够困难的问题,或存在时间可扩展性问题。本文通过识别并操控决定问题“难度”的关键因素——核心,解决了上述挑战。尽管已有工作涉及核心,但传统启发式核心检测方法成本过高。我们提出一种基于图神经网络的快速核心检测方法,实验证明能高效生成仍具挑战性的SAT问题,并保留原问题的关键属性。实验表明,这些合成问题可用于数据增强,显著提升求解器运行时间的预测性能。

原文摘要 · Abstract (English)

Efficiently determining the satisfiability of a boolean equation -- known as the SAT problem for brevity -- is crucial in various industrial problems. Recently, the advent of deep learning methods has introduced significant potential for enhancing SAT solving. However, a major barrier to the advancement of this field has been the scarcity of large, realistic datasets. The majority of current public datasets are either randomly generated or extremely limited, containing only a few examples from unrelated problem families. These datasets are inadequate for meaningful training of deep learning methods. In light of this, researchers have started exploring generative techniques to create data that more accurately reflect SAT problems encountered in practical situations. These methods have so far suffered from either the inability to produce challenging SAT problems or time-scalability obstacles. In this paper we address both by identifying and manipulating the key contributors to a problem's ``hardness'', known as cores. Although some previous work has addressed cores, the time costs are unacceptably high due to the expense of traditional heuristic core detection techniques. We introduce a fast core detection procedure that uses a graph neural network. Our empirical results demonstrate that we can efficiently generate problems that remain hard to solve and retain key attributes of the original example problems. We show via experiment that the generated synthetic SAT problems can be used in a data augmentation setting to provide improved prediction of solver runtimes.

SAT求解数据增强图神经网络生成模型

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。