Branching Heuristic Strategy Based on Variable Mixing Features
CSTR:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    Advanced SAT solvers solve large application instances with efficient branching heuristics. At present, the VSIDS strategy is the most representative branching strategy based on conflict analysis. It is widely used because of its robustness. However, in each conflict analysis, the incremental method of determining the variable activity is too single. To solve this problem, this study proposes a branch heuristic algorithm based on variable mixing features. The purpose is to fully utilize the different information features carried in the variables involved in conflict analysis to distinguish variables, and further guide the variable activity growth. The proposed branching strategy algorithm is embedded into Glucose4.1 to form the solver Glucose4.1+MFBS. Through experimental comparison and analysis, the experimental results show that the improved branching algorithm has certain advantages over the original VSIDS strategy, and the number of solutions increases obviously.

    Reference
    Related
    Cited by
Get Citation

艾森阳,宋振明,沈雪.基于变量混合特征的分支启发式策略.计算机系统应用,2020,29(3):200-205

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 16,2019
  • Revised:August 22,2019
  • Adopted:
  • Online: March 02,2020
  • Published: March 15,2020
Article QR Code
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-3
Address:4# South Fourth Street, Zhongguancun,Haidian, Beijing,Postal Code:100190
Phone:010-62661041 Fax: Email:csa (a) iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063