Computer Science ›› 2018, Vol. 45 ›› Issue (11A): 117-120.

• Intelligent Computing • Previous Articles     Next Articles

Branching Heuristic Method Based on Added Weight Average Value

HU Zhong-xue, XU Yang, HU Rong   

  1. School of Mathematics,Southwest Jiaotong University,Chengdu 610031,China
  • Online:2019-02-26 Published:2019-02-26

Abstract: The effective branching strategy was proposed in the satisfiability (SAT) problem algorithm,which can improve the efficiency of the solver.In consideration of the conflict,according to whether the variables join in conflict and conflict times,a branching heuristic method based on added weight average value was proposed.Firstly,a sequence is used to record whether the variables are involved in the conflict.Secondly,a weighted average function is given,the function value is calculated through variable sequences and decision levels.Finally,variable with the largest value is assigned,example analysis and comparisonare conducted.The new method is an improved method according to the control encoding method,so in the example analysis,the comparison and analysis ways were used,and SUM (Sum in experiment) strategy and ACIDS(Average Conflict-index Decision Score) strategy were compared with the new method at the same time.Through analysis of examples in SATLIB (SAT little information bank),the results show that more clauses are satisfied or the latest conflict clause can get the priority by the new method.

Key words: Branching heuristic, Decision layer, Sequence, Times of conflict, Weighted average

CLC Number: 

  • TP181
[1]田奕,刘涛.求解可满足性问题的一种高效遗传算法[J].模式识别与人工智能,1996,9(3):209-212.
[2]WU G F,XU Y,CHANG W,et al.Parallel Genetic Algorithm for SAT Problem Based on the Coarse-grained Model [C]∥Proceedings of the 12th International FLINS Conference on Uncertainty Modelling in Knowledge Engineering and Decision Ma-king.City Council of Roubaix:World Scientific Publishing Co.Pte Ltd,2016:489-495.
[3]陈稳.基于DPLL的SAT算法的研究及应用[D].成都:电子科技大学,2011.
[4]JIANG C,ZHANG T.Partial Backtracking in CDCL Solvers[C]∥ Proceedings of the 19th International Conference on Logic for Programming,Artificial Intelligence,and Reasoning.Berlin Heidelberg:Springer Verlag,2013:490-502.
[5]MARQUESSILVA J P,SAKALLAH K A.GRASP:A Search Algorithm for Propositional Satisfiability[J].IEEE Transactions on Computers,1999,48(5):506-521.
[6]MARQUES SILVA J P,SAKALLAH K A.GRASP—A New Search Algorithm for Satisfiability[C]∥Proceedings of the 1996 IEEE/ACM International Conference on Computer-Aided Design.Digest of Technical Papers:IEEE Press,2003:73-89.
[7]MOSKEWICZ M W,MADIAN C F,ZHAO Y,et al.Chaff:Engineering an Efficient SAT Solver[C]∥Proceedings of the 38th Design Automation Conference.United States:IEEE Press,2005:530-535.
[8]LIANG J H,GANESH V,ZULKOSKI E,et al.Understanding VSIDS Branching Heuristics in Conflict-Driven Clause-Learning SAT Solvers[C]∥Proceedings of the 11th International Haifa Verification Conference on Verification and Testing of Hardware and Software.Haifa(Israel):Springer International Publishing,2015:225-241.
[9]DERSHOWITZ N,HANNA Z,NADEL A.A Clause-based Heuristic for SAT Solvers[C]∥Proceedings of the 8th International Conference on Theory and Applications of Satisfiability Testing.Intel Corporation:Springer-Verlag,2005:46-60.
[10]BIERE A,FROHLICH A.Evaluating CDCL Variable Scoring Schemes[C]∥Proceedings of the 18th International Conference on Theory and Applications of Satisfiability Testing.Bioinformatics:Springer International Publishing,2015:405-422.
[11]CHEN J.A Dynamic Phase Selection Strategy for Satisfiability Solvers [J].Computer Science,2012,13(5):208-213.
[12]CHEN J.Phase Selection Heuristics for Satisfiability Solvers[J].Computer Science,2011,36(6):312-320.
[13]CHEN J.A Bit-Encoding Phase Selection Strategy for Satisfia-bility Solvers[C]∥Proceedings of the 11th Annual Conference on Theory and Applications of Models of Computation.New York:Springer Verlag,2014:158-167.
[14]PIPATSRISAWAT K,DARWICHE A.A Lightweight Comp-onent Caching Scheme for Satisfiability Solvers[C]∥Procee-dings of the 10th International Conference on Theory and Applications of Satisfiability Testing.Lisbon Portugal:Springer Verlag,2007:294-299.
[15]刘志明,吴明芬,许勇.一种基于遗传算法的权重的确定方法 [J].五邑大学学报(自然科学版),2006,20(3):45-48.
[16]LIANG J H,GANESH V,POUPART P,et al.Exponential Recency Weighted Average Branching Heuristic for SAT Solvers[C]∥Proceedings of the 30th AAAI Conference on Artificial Intelligence.Infosys:AAAI Press,2016:3434-3440.
[17]SILVA J,MARQUES O P.The Impact of Branching Heuristics in Propositional Satisfiability Algorithms[C]∥Proceedings of the 9th Portuguese Conference on Artificial Intelligence.Berlin Heidelberg:Springer Verlag,1999:62-74.
[18]LIU Y,WANG J,XU C,et al.An Effective Branching Strategy Based on Structural Relationship among Multiple Forbidden Induced Subgraphs [J].Journal of Combinatorial Optimization,2015,29(1):257-275.
[1] ZHOU Le-yuan, ZHANG Jian-hua, YUAN Tian-tian, CHEN Sheng-yong. Sequence-to-Sequence Chinese Continuous Sign Language Recognition and Translation with Multi- layer Attention Mechanism Fusion [J]. Computer Science, 2022, 49(9): 155-161.
[2] SUN Fu-quan, LIANG Ying. Identification of 6mA Sites in Rice Genome Based on XGBoost Algorithm [J]. Computer Science, 2022, 49(6A): 309-313.
[3] CHEN Hui-pin, WANG Kun, YANG Heng, ZHENG Zhi-jie. Visual Analysis of Multiple Probability Features of Bluetongue Virus Genome Sequence [J]. Computer Science, 2022, 49(6A): 27-31.
[4] ZHAO Geng, WANG Chao, MA Ying-jie. Study on PAPR Reduction Based on Correlation of Chaotic Sequences [J]. Computer Science, 2022, 49(5): 250-255.
[5] ZHAO Geng, LI Wen-jian, MA Ying-jie. Chaotic Sequence Cipher Algorithm Based on Discrete Anti-control [J]. Computer Science, 2022, 49(4): 376-384.
[6] CHEN Wei, LI Hang, LI Wei-hua. Ensemble Learning Method for Nucleosome Localization Prediction [J]. Computer Science, 2022, 49(2): 285-291.
[7] CHENG Si-wei, GE Wei-yi, WANG Yu, XU Jian. BGCN:Trigger Detection Based on BERT and Graph Convolution Network [J]. Computer Science, 2021, 48(7): 292-298.
[8] YANG Ping, SHU Hui, KANG Fei, BU Wen-juan, HUANG Yu-yao. Generating Malicious Code Attack Graph Using Semantic Analysis [J]. Computer Science, 2021, 48(6A): 448-458.
[9] DENG Li, WU Jin-da, LI Ke-xue, LU Ya-kang. SpaRC Algorithm Hyperparameter Optimization Methodology Based on TPE [J]. Computer Science, 2021, 48(2): 70-75.
[10] YU Shi-yuan, GUO Shu-ming, HUANG Rui-yang, ZHANG Jian-peng, SU Ke. Overview of Nested Named Entity Recognition [J]. Computer Science, 2021, 48(11A): 1-10.
[11] YOU Lan, HAN Xue-wei, HE Zheng-wei, XIAO Si-yu, HE Du, PAN Xiao-meng. Improved Sequence-to-Sequence Model for Short-term Vessel Trajectory Prediction Using AIS Data Streams [J]. Computer Science, 2020, 47(9): 169-174.
[12] CHEN Qing-chao, WANG Tao, FENG Wen-bo, YIN Shi-zhuang, LIU Li-jun. Unknown Binary Protocol Format Inference Method Based on Longest Continuous Interval [J]. Computer Science, 2020, 47(8): 313-318.
[13] XU Xu-dong, ZHANG Zhi-xiang and ZHANG Xian. Format Mining Method of Variable-length Domain in Private Binary Protocol [J]. Computer Science, 2020, 47(6A): 556-560.
[14] NI Hai-qing, LIU Dan, SHI Meng-yu. Chinese Short Text Summarization Generation Model Based on Semantic-aware [J]. Computer Science, 2020, 47(6): 74-78.
[15] HU Yu-jia, GAN Wei, ZHU Min. Enhancer-Promoter Interaction Prediction Based on Multi-feature Fusion [J]. Computer Science, 2020, 47(5): 64-71.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!