基于情境示例的学习方法用于组合优化问题的MAX-SAT求解
本文提出了一种新的路线,即通过引入可微(平滑)的最大可满足性(MAXSAT)求解器,将逻辑推理纳入更大的深度学习系统的循环中,从而在端到端学习系统中学习有挑战性的问题的逻辑结构,表现出集成逻辑结构于深度学习的潜力。
May, 2019
本文综述了近期文献,重点介绍了利用机器学习技术来解决布尔可满足性问题(SAT)的方法,包括从基于手工特征的朴素分类器到最新的端到端SAT求解器NeuroSAT,以及将现有的CDCL和本地搜索求解器与机器学习相结合的最新进展。总体而言,利用机器学习解决SAT是一个有前途但充满挑战的研究课题,文章指出了当前研究的局限性并提出了未来可能的方向。
Mar, 2022
介绍了一种名为NSNet的神经网络模型,通过使用一种新型的图神经网络(GNN)在潜在空间中对BP进行参数化,可以灵活配置以解决SAT和#SAT问题。
Nov, 2022
应用深度学习解决困难的组合问题具有巨大的潜力。该研究侧重于布尔可满足性(SAT)问题,并通过基本的概率方法消除了由于训练集仅限于小于实际问题规模几个数量级的随机公式导致的难题。使用我们的生成器,我们对现有的最先进模型进行训练,以预测具有10,000个变量的公式的可满足性,提出了新的分类器,可以对大多数困难水平的相同数据集进行显着改进,从而打破了过去基于公式的句法特征学习的方法,并使用求解器计算的简短前缀进行学习。
Nov, 2022
本文介绍了针对最大可满足性问题提出的UCTMAXSAT算法,探讨了两种算法变化对算法性能的影响,提出了使用静态翻转限制并动态设置预算来达到相似性能的建议。
Feb, 2023
使用强化学习来学习有效的变量评分函数和噪声参数,针对不同的实例分布学习专门的启发式方法,实验证明与基线方法以及另一个学习到的局部搜索启发式方法相比获得了改进。
Jul, 2023
布尔可满足性 (SAT) 是一个基础的 NP-complete 问题,具有许多应用,包括自动计划和调度。为了解决大规模的情况,SAT 求解器必须依赖启发式算法,如在 DPLL 和 CDCL 求解器中选择一个分支变量。我们建议使用机器学习模型来改进这些启发式算法,通过减少步数来降低运行时间,但是由于有用的模型相对较大和较慢,这通常会阻碍运行时间。我们建议首先使用训练好的机器学习模型进行几个初始步骤,然后将控制权交给经典启发式算法,这简化了 SAT 求解的冷启动,并可以减少步数和总运行时间,但需要单独决定何时将控制权交给求解器。此外,我们介绍了一种改进的 Graph-Q-SAT,专门针对从其他领域转换而来的 SAT 问题,例如开放式车间调度问题。我们通过随机和工业 SAT 问题验证了我们方法的可行性。
Jul, 2023
通过使用监督式机器学习方法,探讨选择伪布尔约束和线性约束的编码问题,我们展示了使用标准特征集和专门设计的特征集可以有效地选择编码,甚至对于未见过的问题类别也能取得良好的结果,相比使用相同特征集的AutoFolio结果有优势。我们讨论了实例特征对选择最佳编码任务的相对重要性,并比较了多种机器学习方法的变体。
Jul, 2023