A Branching Heuristic Based on Variable Decision Levels

被引：0
|
作者：
Du, Zhonghe [1 ]
Song, Zhenming [1 ]
机构：
[1] Southwest Jiaotong Univ, Natl Local Joint Engn Lab Syst Credibil Automat V, Chengdu 610031, Sichuan, Peoples R China
来源：
2017 12TH INTERNATIONAL CONFERENCE ON INTELLIGENT SYSTEMS AND KNOWLEDGE ENGINEERING (IEEE ISKE) | 2017年
基金：
中国国家自然科学基金;
关键词：
SAT problem; branching heuristic; decision level; VSIDS;
D O I：
暂无
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
Efficient branching heuristic is a key feature of modern SAT solvers. Firstly, this paper introduced VSIDS heuristic and VSIDS-based heuristics like EVSIDS and ACIDS. Based on VSIDS, a new heuristic termed DLBH that considers variable decision levels was proposed to promote the efficiency of variable selection process. Then, instances showed the comparison among EVSIDS, ACIDS and DLBH. Finally, experimental results indicated that MiniSat solver with DLBH outperforms solvers MiniSat with VSIDS and Glucose.
引用
收藏
页数：5
相关论文
共 15 条
  • [1] Conflicting Rate Based Branching Heuristic for CDCL SAT Solvers
    Chen, Qingshan
    Xu, Yang
    Wu, Guanfeng
    He, Xingxing
    2017 12TH INTERNATIONAL CONFERENCE ON INTELLIGENT SYSTEMS AND KNOWLEDGE ENGINEERING (IEEE ISKE), 2017,
  • [2] A branching heuristic for SAT solvers based on complete implication graphs
    Xiao, Fan
    Li, Chu-Min
    Luo, Mao
    Manya, Felip
    Lu, Zhipeng
    Li, Yu
    SCIENCE CHINA-INFORMATION SCIENCES, 2019, 62 (07)
  • [3] A branching heuristic for SAT solvers based on complete implication graphs
    Fan Xiao
    Chu-Min Li
    Mao Luo
    Felip Manyà
    Zhipeng Lü
    Yu Li
    Science China Information Sciences, 2019, 62
  • [4] A branching heuristic for SAT solvers based on complete implication graphs
    Fan XIAO
    Chu-Min LI
    Mao LUO
    Felip MANYA
    Zhipeng Lü
    Yu LI
    Science China(Information Sciences), 2019, 62 (07) : 170 - 182
  • [5] Adding a LBD-based Rewarding Mechanism in Branching Heuristic for SAT Solvers
    Chang, Wenjing
    Wu, Guanfeng
    Xu, Yang
    2017 12TH INTERNATIONAL CONFERENCE ON INTELLIGENT SYSTEMS AND KNOWLEDGE ENGINEERING (IEEE ISKE), 2017,
  • [6] A New Rewarding Mechanism for Branching Heuristic in SAT Solvers
    Chang, Wenjing
    Xu, Yang
    Chen, Shuwei
    INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE SYSTEMS, 2019, 12 (01) : 334 - 341
  • [7] Solving SAT problem by heuristic polarity decision-making algorithm
    JING MingE1
    2 E. E. Department
    ScienceinChina(SeriesF:InformationSciences), 2007, (06) : 915 - 925
  • [8] Solving SAT problem by heuristic polarity decision-making algorithm
    MingE Jing
    Dian Zhou
    PuShan Tang
    XiaoFang Zhou
    Hua Zhang
    Science in China Series F: Information Sciences, 2007, 50 : 915 - 925
  • [9] Solving SAT problem by heuristic polarity decision-making algorithm
    Jing, Minge
    Zhou, Dian
    Tang, PuShan
    Zhou, XiaoFang
    Zhang, Hua
    SCIENCE IN CHINA SERIES F-INFORMATION SCIENCES, 2007, 50 (06): : 915 - 925
  • [10] A Branching Strategy Based on the Length of Learnt Clause
    Hu, Zhongxue
    Xu, Yang
    2018 INTERNATIONAL CONFERENCE ON BIG DATA AND ARTIFICIAL INTELLIGENCE (BDAI 2018), 2018, : 87 - 91
12