Local search for Boolean satisfiability with configuration checking and subscore

DOI10.1016/j.artint.2013.09.001zbMath1334.68200OpenAlexW2097153130MaRDI QIDQ490437

Shaowei Cai, Kaile Su

Publication date: 27 August 2015

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2013.09.001

zbMATH Keywords

subscorelocal searchSATconfiguration checking

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (17)

Solving the set packing problem via a maximum weighted independent set heuristic ⋮ CCAnr: A Configuration Checking Based Local Search Solver for Non-random Satisfiability ⋮ New local search methods for partial MaxSAT ⋮ An efficient local search algorithm for solving maximum edge weight clique problem in large graphs ⋮ Local Search For Satisfiability Modulo Integer Arithmetic Theories ⋮ Go-MOCE: greedy order method of conditional expectations for Max Sat ⋮ Timescales of Boolean satisfiability solver using continuous-time dynamical system ⋮ An iterative path-breaking approach with mutation and restart strategies for the MAX-SAT problem ⋮ CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability ⋮ Improving configuration checking for satisfiable random \(k\)-SAT instances ⋮ An efficient local search framework for the minimum weighted vertex cover problem ⋮ Local search for diversified top-\(k\) clique search problem ⋮ SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem ⋮ CCASat ⋮ Efficient Local Search based on Dynamic Connectivity Maintenance for Minimum Connected Dominating Set ⋮ Using the method of conditional expectations to supply an improved starting point for CCLS ⋮ XOR local search for Boolean Brent equations

Uses Software

• MiniSat
• SATzilla
• NuMVC
• ppfolio
• pfolioUZK
• Sparrow2011

Cites Work

• Unnamed Item
• Unnamed Item
• Local search with edge weighting and configuration checking heuristics for minimum vertex cover
• Theoretical aspects of local search.
• Local search algorithms for SAT: an empirical evaluation
• Choosing Probability Distributions for Stochastic Local Search and the Role of Make versus Break
• Captain Jack: New Variable Selection Heuristics in Local Search for SAT
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• An improved exponential-time algorithm for k -SAT
• Tabu Search—Part I
• Tabu Search—Part II
• NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover
• Improving Stochastic Local Search for SAT with a New Probability Distribution
• Dynamic Scoring Functions with Variable Expressions: New SLS Methods for Solving SAT
• An Empirical Study of Optimal Noise and Runtime Distributions in Local Search
• Survey propagation: An algorithm for satisfiability
• Threshold values of random K‐SAT from the cavity method
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• Reactive local search for the maximum clique problem
• Defining tabu list size and aspiration criterion within tabu search methods

This page was built for publication: Local search for Boolean satisfiability with configuration checking and subscore