4
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      A Probability Distribution Strategy with Efficient Clause Selection for Hard Max-SAT Formulas

      Preprint
      , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Many real-world problems involving constraints can be regarded as instances of the Max-SAT problem, which is the optimization variant of the classic satisfiability problem. In this paper, we propose a novel probabilistic approach for Max-SAT called ProMS. Our algorithm relies on a stochastic local search strategy using a novel probability distribution function with two strategies for picking variables, one based on available information and another purely random one. Moreover, while most previous algorithms based on WalkSAT choose unsatisfied clauses randomly, we introduce a novel clause selection strategy to improve our algorithm. Experimental results illustrate that ProMS outperforms many state-of-the-art stochastic local search solvers on hard unweighted random Max-SAT benchmarks.

          Related collections

          Author and article information

          Journal
          2016-10-03
          Article
          1610.00442
          8486928a-57fd-4723-b19a-bf07ac7915cf

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          11 pages, 3 tables
          cs.AI

          Artificial intelligence
          Artificial intelligence

          Comments

          Comment on this article