专栏首页arxiv.org翻译专栏关于PB求解器的弱化策略(CS AI)
原创

关于PB求解器的弱化策略(CS AI)

当前的伪布尔解决器实现不同的变种切割面证明系统推断新的约束在冲突分析。 其中一个变量是广义分辨率,它允许推断出强制约束,但是在结合伪布尔约束时,会受到系数增长的影响。 另一种变体包括使用削弱和分割,这在实践中更有效,但可能推断出较弱的约束。 在这两种情况下,削弱都是强制性的,以产生相互冲突的约束。 然而,它对伪布尔求解器性能的影响到目前为止还没有被评估。 本文针对小系数强约束问题,研究了该规则的新的应用策略。 我们在 sat4j 中实现了它们,并且观察到它们每个都改进了求解器的运行时。 虽然在所有基准测试中,没有一个测试表现比其他测试表现更好,但是在冲突一方使用弱化方法有着惊人的优异表现,而在冲突和原因双方使用部分弱化和分裂方法提供了最佳的总体结果。

原文题目:On Weakening Strategies for PB Solvers

原文:Current pseudo-Boolean solvers implement different variants of the cutting planes proof system to infer new constraints during conflict analysis. One of these variants is generalized resolution, which allows to infer strong constraints, but suffers from the growth of coefficients it generates while combining pseudo-Boolean constraints. Another variant consists in using weakening and division, which is more efficient in practice but may infer weaker constraints. In both cases, weakening is mandatory to derive conflicting constraints. However, its impact on the performance of pseudo-Boolean solvers has not been assessed so far. In this paper, new application strategies for this rule are studied, aiming to infer strong constraints with small coefficients. We implemented them in Sat4j and observed that each of them improves the runtime of the solver. While none of them performs better than the others on all benchmarks, applying weakening on the conflict side has surprising good performance, whereas applying partial weakening and division on both the conflict and the reason sides provides the best results overall.

原文作者: Romain Wallon

原文地址:https://arxiv.org/abs/2005.04466

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 从流感预测到智能决策,深度学习能帮企业做哪些事?

    这句话大概可以总结两层意思,一方面人工智能让更多的企业面对更广阔的商业前景,另一方面是如果要运用人工智能创造价值,就必须拥抱技术,实现真正的落地。

    AI科技大本营
  • Decolonial AI:人工智能社会技术预见的Decolonial理论(CS Computers and Society)

    本文探讨了批判性科学,特别是后殖民和非殖民理论在理解和塑造人工智能不断进步方面的重要作用。人工智能(AI)被视为将重塑现代社会及其关系的技术进步之一。 尽管设计...

    Rosalie
  • 在人工智能的浪尖上,如何抉择?

    知友:李麟 人工智能可以说是一门高尖端学科,属于社会科学和自然科学的交叉,涉及了数学、心理学、神经生理学、信息论、计算机科学、哲学和认知科学、不定性论以及控制论...

    IT派
  • 斯坦福AI课程10年发展史:CS 229最受欢迎,课程数量增两倍

    AI 正在改变世界,斯坦福大学处于这一趋势的最前沿。多年来,斯坦福已经涌现出许多 AI 方面的重大研究突破,斯坦福研究者也是 AI 领域的开拓者。

    机器之心
  • AI赌神称霸德扑的秘密,刚刚被《科学》“曝光”了

    夏乙 问耕 发自 凹非寺 量子位 出品 | 公众号 QbitAI 称霸德州扑克赛场的赌神Libratus,是今年最瞩目的AI明星之一。 刚刚,《科学》最新发布的...

    量子位
  • 训练时间降低90%以上!世界最大的芯片WSE有望打破AI计算瓶颈

    人工智能计算机初创公司Cerebras Systems CEO兼联合创始人Andrew Feldman表示,如今的人工智能仅仅只是开始。

    新智元
  • 【前沿】Purdue&UCLA提出梯度Boosting网络,效果远好于XGBoost模型!

    Gradient Boosting Neural Networks: GrowNet

    zenRRan
  • Purdue&UCLA提出梯度Boosting网络,效果远好于XGBoost模型!

    Gradient Boosting Neural Networks: GrowNet

    炼丹笔记
  • 思科公司发布强大的AI服务器UCS C480 ML M5

    AI算法在理论上是很好的,但如果你没有强大的硬件来部署它们,它们基本上是无用的。使用传统计算机,复杂的模型可能需要数小时,数天甚至数周才能进行训练。

    AiTechYun

扫码关注云+社区

领取腾讯云代金券