logo

SCIENCE CHINA Information Sciences, Volume 62, Issue 11: 219106(2019) https://doi.org/10.1007/s11432-018-9786-2

A Kernighan-Lin inspired algorithm for MAX-SAT

More info
  • ReceivedMay 6, 2018
  • AcceptedOct 15, 2018
  • PublishedSep 24, 2019

Abstract

There is no abstract available for this article.


References

[1] Kernighan B W, Lin S. An Efficient Heuristic Procedure for Partitioning Graphs. Bell Syst Technical J, 1970, 49: 291-307 CrossRef Google Scholar

[2] Smyth K, Hoos H H, St$\ddot{u}$tzle T. Iterated robust tabu search for MAX-SAT. In: Proceedings of the 16th Canadian Society for Computational Studies of Intelligence Conference on Advances in Artificial Intelligence, Halifax, 2003. 129--144. Google Scholar

[3] Tompkins A D, Hoos H H. UBCSAT: an implementation and experimentation environment for SLS algorithms for SAT and MAX-SAT. In: Proceedings of the 7th International Conference on Theory and Applications of Satisfiability Testing, Vancouver, 2004. 306--320. Google Scholar

  • Table 1   Performance comparisons
    Inst KL IRoTS
    $Q$ $T$ $Q$ $T$
    Real difp-19-0 7 89.5 21 66.5
    difp-19-1 5 60.1 19 47.8
    difp19-3 7 105.1 23 68.1
    difp-19-99 16 112.8 26 52.7
    difp20-0 7 109.5 18 41.1
    difp20-1 8 103.1 26 73.2
    difp20-2 20 98.1 26 62.1
    difp20-3 6 117.3 34 60.3
    difp20-99 18 114.7 26 52.8
    difp-21-0 8 102.7 31 48.2
    difp21-1 9 85.1 34 42.7
    difp21-2 20 117 33 78.3
    difp21-3 22 119.4 34 69.3
    difp21-99 8 79.2 33 60.3
    Unweighted v100c1200 865 2.31 865 0.13
    v100c1300 933 6.76 933 0.16
    v100c1400 1018 6.31 1018 0.15
    v100c1500 1186 3.36 1186 0.19
    v120c1400 959 4.06 959 0.16
    v120c1500 1119 7.25 1119 0.14
    v120c1600 1150 0.85 1150 0.16
    v140c1500 1073 0.86 1073 0.17
    v140c1600 1143 12.14 1143 0.17
    Weighted v70c700 110 1.60 110 0.16
    v70c800 132 2.54 132 0.16
    v70c900 157 2.76 157 0.15
    v70c1000 214 6.51 214 0.18

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1