The Experts below are selected from a list of 24 Experts worldwide ranked by ideXlab platform
Wanxia Wei - One of the best experts on this subject based on the ideXlab platform.
-
Exploiting historical relationships of Clauses and variables in local search for satisfiability
Theory and Applications of Satisfiability Testing – SAT 2012, 2012Co-Authors: Wanxia WeiAbstract:Variable properties such as score and age are used to select a variable to flip. The score of a variable x refers to the decrease in the number of Unsatisfied Clauses if x is flipped. The age of x refers to the number of steps done since the last time when x was flipped. If the best variable according to scores in a randomly chosen Unsatisfied Clause c is not the youngest in c, Novelty [4] flips this variable. Otherwise, with probability p (noise p), Novelty flips the second best variable, and with probability 1-p, Novelty flips the best variable. Novelty+ [1] randomly flips a variable in c with probability wp and does as Novelty with probability 1-wp. Novelty++ [3] flips the least recently flipped variable (oldest) in c with probability dp, and does as Novelty with probability 1-dp.
-
SAT - Exploiting Historical Relationships of Clauses and Variables in Local Search for Satisfiability (Poster Presentation)
2012Co-Authors: Wanxia WeiAbstract:Variable properties such as score and age are used to select a variable to flip. The score of a variable x refers to the decrease in the number of Unsatisfied Clauses if x is flipped. The age ofx refers to the number of steps done since the last time whenx was flipped. If the best variable according to scores in a randomly chosen Unsatisfied Clause c is not the youngest in c, Novelty [4] flips this variable. Otherwise, with probability p (noise p), Novelty flips the second best variable, and with probability 1-p, Novelty flips the best variable. Novelty+ [1] randomly flips a variable in c with probability wp and does as Novelty with probability 1-wp. Novelty++ [3] flips the least recently flipped variable (oldest) in c with probability dp, and does as Novelty with probability 1-dp. The above approaches just use the current properties of variables to select a variable to flip. These approaches are effective for the problems that do not present uneven distribution of variable and/or Clause weights during the search. In other words, problems can be solved using these approaches when there are no Clauses or variables whose weight is several times larger than the average during the search [6]. However, when solving hard random or structured SAT problems using these approaches, variable or Clause weight distribution is often uneven. In this case, the falsification history of Clauses and/or the flipping history of variables during the search should be exploited to select a variable to flip for the problems to be solved. In this paper, we present a noise mechanism that exploits the history information to determine noise p. For a falsified Clause c ,l etvar fals[c] denote the variable that most recently falsifies c and let num fals[c] denote the number of the most recent consecutive falsifications of c due to the flipping of this variable. If the best variable in c is not var fals[c], this variable is flipped. Otherwise, the second best variable is flipped with probability p ,w herep is determined as a function of k=num fals[c]: {20,50,65,72,78,86,90,95,98,100} ,i .e.,p=0.2 if k=1, p=0.5 if k=2, ..., p=1 if k ≥ 10. This probability vector was empirically turned using a subset of instances. Another adaptive noise mechanism was introduced in [2] to automatically adjust noise during the search. We refer to this mechanism as Hoos’s noise mechanism. SLS solvers TNM and adaptG 2 WSAT2011 , described in Fig. 1, are both based on Novelty, but use noise p determined by our noise mechanism at each uneven step, and use noise p1 adjusted by Hoos noise mechanism at each even step, to flip the second best variable in the randomly selected Unsatisfied Clause c when the best variable in c is the youngest in c .I nTNM , a step is even if the variable weight distribution currently is even (e.g., all variable weights are smaller than 10 × the average variable weight). In adaptG 2 WSAT2011 , a step is even if c currently has small weight (e.g., smaller than
Chuan Luo - One of the best experts on this subject based on the ideXlab platform.
-
SAT - CCAnr: A Configuration Checking Based Local Search Solver for Non-random Satisfiability
Lecture Notes in Computer Science, 2015Co-Authors: Shaowei Cai, Chuan LuoAbstract:This paper presents a stochastic local search (SLS) solver for SAT named CCAnr, which is based on the configuration checking strategy and has good performance on non-random SAT instances. CCAnr switches between two modes: it flips a variable according to the CCA (configuration checking with aspiration) heuristic if any; otherwise, it flips a variable in a random Unsatisfied Clause (which we refer to as the focused local search mode). The main novelty of CCAnr lies on the greedy heuristic in the focused local search mode, which contributes significantly to its good performance on structured instances. Previous two-mode SLS algorithms usually utilize diversifying heuristics such as age or randomized strategies to pick a variable from the Unsatisfied Clause. Our experiments on combinatorial and application benchmarks from SAT Competition 2014 show that CCAnr has better performance than other state-of-the-art SLS solvers on structured instances, and its performance can be further improved by using a preprocessor CP3. Our results suggest that a greedy heuristic in the focused local search mode might be helpful to improve SLS solvers for solving structured SAT instances.
Shaowei Cai - One of the best experts on this subject based on the ideXlab platform.
-
SAT - CCAnr: A Configuration Checking Based Local Search Solver for Non-random Satisfiability
Lecture Notes in Computer Science, 2015Co-Authors: Shaowei Cai, Chuan LuoAbstract:This paper presents a stochastic local search (SLS) solver for SAT named CCAnr, which is based on the configuration checking strategy and has good performance on non-random SAT instances. CCAnr switches between two modes: it flips a variable according to the CCA (configuration checking with aspiration) heuristic if any; otherwise, it flips a variable in a random Unsatisfied Clause (which we refer to as the focused local search mode). The main novelty of CCAnr lies on the greedy heuristic in the focused local search mode, which contributes significantly to its good performance on structured instances. Previous two-mode SLS algorithms usually utilize diversifying heuristics such as age or randomized strategies to pick a variable from the Unsatisfied Clause. Our experiments on combinatorial and application benchmarks from SAT Competition 2014 show that CCAnr has better performance than other state-of-the-art SLS solvers on structured instances, and its performance can be further improved by using a preprocessor CP3. Our results suggest that a greedy heuristic in the focused local search mode might be helpful to improve SLS solvers for solving structured SAT instances.
Thach-thao Duong - One of the best experts on this subject based on the ideXlab platform.
-
IJCAI - Weight-enhanced diversification in stochastic local search for satisfiability
2013Co-Authors: Thach-thao Duong, Duc Nghia Pham, Abdul Sattar, M. A. Hakim NewtonAbstract:Intensification and diversification are the key factors that control the performance of stochastic local search in satisfiability (SAT). Recently, Novelty Walk has become a popular method for improving diversification of the search and so has been integrated in many well-known SAT solvers such as TNM and gNovelty+. In this paper, we introduce new heuristics to improve the effectiveness of Novelty Walk in terms of reducing search stagnation. In particular, we use weights (based on statistical information collected during the search) to focus the diversification phase onto specific areas of interest. With a given probability, we select the most frequently Unsatisfied Clause instead of a totally random one as Novelty Walk does. Amongst all the variables appearing in the selected Clause, we then select the least flipped variable for the next move. Our experimental results show that the new weight-enhanced diversification method significantly improves the performance of gNovelty+ and thus outperforms other local search SAT solvers on a wide range of structured and random satisfiability benchmarks.
-
SCAI - Trap escape for local search by backtracking and conflict reverse
2013Co-Authors: Huu-phuoc Duong, Thach-thao Duong, Duc Nghia Pham, Abdul Sattar, Anh Duc DuongAbstract:This paper presents an efficient trap escape strategy in stochastic local search for Satisfiability. The proposed method aims to enhance local search by pro- viding an alternative local minima escaping strategy. Our variable selection scheme provides a novel local minima escaping mechanism to explore new solution areas. Conflict variables are hypothesized as variables recently selected near local min- ima. Hence, a list of backtracked conflict variables is retrieved from local min- ima. The new strategy selects variables in the backtracked variable list based on the Clause-weight scoring function and stagnation weights and variable weights as tiebreak criteria. This method is an alternative to the conventional method of se- lecting variables in a randomized Unsatisfied Clause. The proposed tiebreak method favors high stagnation weights and low variable weights during trap escape phases. The new strategies are examined on verification benchmark and SAT Competi- tion 2011 and 2012 application and crafted instances. Our experiments show that proposed strategy has comparable performance with state-of-the-art local search solvers for SAT.
Alexander Nadel - One of the best experts on this subject based on the ideXlab platform.
-
Understanding and Improving a Modern SAT Solver
2009Co-Authors: Alexander NadelAbstract:Propositional satisfiability (SAT) is an NP-complete problem, holding a central place in computer science and engineering. SAT has numerous applications in formal verification, artificial intelligence and other areas. Modern SAT solvers, using an enhanced version of the backtrack search DavisLogemann-Loveland (DLL) algorithm, are able to successfully cope with instances comprising millions of variables. This work is an attempt to shed new light on the functionality of a modern SAT solver. We also propose a number of enhancements that are empirically useful, especially in the formal verification domain. We propose a framework for presenting and analyzing a modern DLLbased SAT solver. We provide a basic backtracking algorithm that explicitly shows the process of resolution refutation construction. Our approach is based on the notion of a parent resolution derivation – a resolution proof for validness of a flip operation. We show how to derive the algorithm of a modern SAT solver from basic backtracking step-by-step. This resolution-based approach allows us to define new criteria for measuring the practical impact of different schemes for conflict-driven learning by making the notion of search pruning more formal. We show that the 1UIP scheme, enhanced by conflict Clause minimization, is better than other known schemes in terms of pruning. This explains its empirical advantage over other schemes. We propose an enhancement to the minimized 1UIP scheme, called local conflict Clause recording. This technique improves the performance of a modern SAT solver by recording additional conflict Clauses. Local conflict Clause recording makes the learning less dependent on the variable polarity selection heuristic. Assignment stack shrinking is a technique whose goal is to shrink the size of the assignment stack and conflict Clauses. We demonstrate the empirical usefulness of assignment stack shrinking and analyze its impact on the performance of a modern SAT solver, comparing it to the impact of conflict Clause minimization and rapid restarts. Furthermore, a new decision heuristic for SAT, called the Clause-based heuristic, is introduced. This heuristic is designed to increase the likelihood that interrelated variables will be chosen in proximity. It maintains a Clause list containing both the initial and conflict Clauses. The next decision literal is picked from the first Unsatisfied Clause. We propose various methods for initially organizing the Clause list and for moving Clauses within it. Our approach results in a significant performance boost over existing heuristics tested on hard real-world industrial benchmarks. Finally, we present an algorithm for minimal unsatisfiable core extraction that is able to find a minimal unsatisfiable core for large real-world formulas. Benchmark families, arising in formal verification of hardware, are of particular interest to us. Modern SAT solvers are able to produce a resolution refutation of a given unsatisfiable formula, whose sources are the input Clauses and whose sink is the empty Clause. Our method’s basic version removes the input Clauses connected to the empty Clause one by one from the resolution refutation, preserving the validity of the refutation by adding other Clauses and resolution relations until no more input Clauses can be removed. In the end, all the input Clauses, connected to the empty Clause, comprise the minimal unsatisfiable core.
