The Experts below are selected from a list of 765 Experts worldwide ranked by ideXlab platform
Chu Min Li - One of the best experts on this subject based on the ideXlab platform.
-
clause vivification by Unit Propagation in cdcl sat solvers
Artificial Intelligence, 2020Co-Authors: Chu Min Li, Felip Manya, Fan Xiao, Zhipeng Lu, Yu LiAbstract:Abstract Original and learnt clauses in Conflict-Driven Clause Learning (CDCL) SAT solvers often contain redundant literals. This may have a negative impact on solver performance, because redundant literals may deteriorate both the effectiveness of Boolean constraint Propagation and the quality of subsequent learnt clauses. To overcome this drawback, we propose a clause vivification approach that eliminates redundant literals by applying Unit Propagation. The proposed clause vivification is activated before the SAT solver triggers some selected restarts, and only affects a subset of original and learnt clauses, which are considered to be more relevant according to metrics like the literal block distance (LBD). Moreover, we conducted an empirical investigation with instances coming from the hard combinatorial and application categories of recent SAT competitions. The results show that a significant number of additional instances are solved when the proposed approach is incorporated into five of the best performing CDCL SAT solvers (Glucose, TC_Glucose, COMiniSatPS, MapleCOMSPS and MapleCOMSPS_LRB). More importantly, the empirical investigation includes an in-depth analysis of the effectiveness of clause vivification. It is worth mentioning that one of the SAT solvers described here was ranked first in the main track of SAT Competition 2017 thanks to the incorporation of the proposed clause vivification. That solver was further improved in this paper and won the bronze medal in the main track of SAT Competition 2018.
-
clause vivification by Unit Propagation in cdcl sat solvers
arXiv: Artificial Intelligence, 2018Co-Authors: Chu Min Li, Felip Manya, Fan Xiao, Zhipeng Lu, Yu LiAbstract:Original and learnt clauses in Conflict-Driven Clause Learning (CDCL) SAT solvers often contain redundant literals. This may have a negative impact on performance because redundant literals may deteriorate both the effectiveness of Boolean constraint Propagation and the quality of subsequent learnt clauses. To overcome this drawback, we propose a clause vivification approach that eliminates redundant literals by applying Unit Propagation. The proposed clause vivification is activated before the SAT solver triggers some selected restarts, and only affects a subset of original and learnt clauses, which are considered to be more relevant according to metrics like the literal block distance (LBD). Moreover, we conducted an empirical investigation with instances coming from the hard combinatorial and application categories of recent SAT competitions. The results show that a remarkable number of additional instances are solved when the proposed approach is incorporated into five of the best performing CDCL SAT solvers (Glucose, TC_Glucose, COMiniSatPS, MapleCOMSPS and MapleCOMSPS_LRB). More importantly, the empirical investigation includes an in-depth analysis of the effectiveness of clause vivification. It is worth mentioning that one of the SAT solvers described here was ranked first in the main track of SAT Competition 2017 thanks to the incorporation of the proposed clause vivification. That solver was further improved in this paper and won the bronze medal in the main track of SAT Competition 2018.
-
CP - Transforming Inconsistent Subformulas in MaxSAT Lower Bound Computation
Lecture Notes in Computer Science, 2008Co-Authors: Chu Min Li, Felip Manya, Nouredine Ould Mohamedou, Jordi PlanesAbstract:We define a new heuristic that guides the application of cycle resolution (CR) in MaxSAT, and show that it produces better lower bounds than those obtained by applying CR exhaustively as in Max-DPLL, and by applying CR in a limited way when Unit Propagation detects a contradiction as in MaxSatz.
-
CP - On inconsistent clause-subsets for Max-SAT solving
Principles and Practice of Constraint Programming – CP 2007, 2007Co-Authors: Sylvain Darras, Gilles Dequen, Laure Devendeville, Chu Min LiAbstract:Recent research has focused on using the power of look-ahead to speed up the resolution of the Max-SAT problem. Indeed, look-ahead techniques such as Unit Propagation (UP) allow to find conflicts and to quickly reach the upper bound in a Branch-and-Bound algorithm, reducing the search-space of the resolution. In previous works, the Max-SAT solvers maxsatz9 and maxsatz14 use Unit Propagation to compute, at each node of the branch and bound search-tree, disjoint inconsistent subsets of clauses in the current subformula to estimate the minimum number of clauses that cannot be satisfied by any assignment extended from the current node. The same subsets may still be present in the subtrees, that is why we present in this paper a new method to memorize them and then spare their recomputation time. Furthermore, we propose a heuristic so that the memorized subsets of clauses induce an ordering among Unit clauses to detect more inconsistent subsets of clauses. We show that this new approach improves maxsatz9 and maxsatz14 and suggest that the approach can also be used to improve other state-of-the-art Max-SAT solvers.
-
exploiting Unit Propagation to compute lower bounds in branch and bound max sat solvers
Principles and Practice of Constraint Programming, 2005Co-Authors: Chu Min Li, Felip Manya, Jordi PlanesAbstract:One of the main differences between complete SAT solvers and exact Max-SAT solvers is that the former make an intensive use of Unit Propagation at each node of the proof tree while the latter, in order to ensure optimality, can only apply Unit Propagation to a restricted number of nodes. In this paper, we describe a branch and bound Max-SAT solver that applies Unit Propagation at each node of the proof tree to compute the lower bound instead of applying Unit Propagation to simplify the formula. The new lower bound captures the lower bound based on inconsistency counts that apply most of the state-of-the-art Max-SAT solvers as well as other improvements, like the start rule, that have been defined to get a lower bound of better quality. Moreover, our solver incorporates the Jeroslow-Wang variable selection heuristic, the pure literal and dominating Unit clause rules, and novel preprocessing techniques. The experimental investigation we conducted to compare our solver with the most modern Max-SAT solvers provides experimental evidence that our solver is very competitive. Research partially supported by projects TIN2004-07933-C03-03 and TIC2003-00950 funded by the Ministerio de Educacion y Ciencia. The second author is supported by a grant Ramon y Cajal.
Akira Nagoya - One of the best experts on this subject based on the ideXlab platform.
-
solving satisfiability problems on fpgas using experimental Unit Propagation
Principles and Practice of Constraint Programming, 1999Co-Authors: Takayuki Suyama, Makoto Yokoo, Akira NagoyaAbstract:This paper presents new results on an innovative approach for solving satisfiability problems (SAT), that is, creating a logic circuit that is specialized to solve each problem instance on Field Programmable Gate Arrays (FPGAs). This approach has become feasible due to recent advances in Reconfigurable Computing, and has opened up an exciting new research field in algorithm design.
-
IPPS/SPDP Workshops - Solving Satisfiability Problems on FPGAs using Experimental Unit Propagation Heuristic
Lecture Notes in Computer Science, 1999Co-Authors: Takayuki Suyama, Makoto Yokoo, Akira NagoyaAbstract:This paper presents new results on an approach for solving satisfiability problems (SAT), that is, creating a logic circuit that is specialized to solve each problem instance on Field Programmable Gate Arrays (FPGAs). This approach has become feasible due to recent advances in Reconfigurable Computing.
-
solving satisfiability problems on fpgas using experimental Unit Propagation heuristic
International Parallel Processing Symposium, 1999Co-Authors: Takayuki Suyama, Makoto Yokoo, Akira NagoyaAbstract:This paper presents new results on an approach for solving satisfiability problems (SAT), that is, creating a logic circuit that is specialized to solve each problem instance on Field Programmable Gate Arrays (FPGAs). This approach has become feasible due to recent advances in Reconfigurable Computing.
Anbulagan Anbulagan - One of the best experts on this subject based on the ideXlab platform.
-
extending Unit Propagation look ahead of dpll procedure
Pacific Rim International Conference on Artificial Intelligence, 2004Co-Authors: Anbulagan AnbulaganAbstract:The DPLL (Davis-Putnam-Logemann-Loveland) procedure is one of the most effective methods for solving SAT problems. It is well known that its efficiency depends on the choice of the branching rule. Different branching rules are proposed in the literature. Unit Propagation look-ahead (UPLA) branching rule was one of the main improvements in the DPLL procedure (e.g.,[10]). The UPLA branching rule integrated in satz SAT solver [10] performs a series of variable filtering process at each node as a static variable filtering agency. In this paper we introduce and experiment with dynamic variable filtering (DVF) based branching rule which extends the UPLA heuristic process for doing more filtering and choosing a best branching variable from an irreducible sub-formula. To enhance the performance of DVF branching rule, we integrate neighborhood variable ordering heuristic (NVO) for exploring only the neighborhood variables of the current assigned variable. Experimental results of DVF+NVO branching rule on a number of real-world benchmark instances and quasigroup problems prove our approaches to be useful in many circumstances.
-
PRICAI - Extending Unit Propagation look-ahead of DPLL procedure
PRICAI 2004: Trends in Artificial Intelligence, 2004Co-Authors: Anbulagan AnbulaganAbstract:The DPLL (Davis-Putnam-Logemann-Loveland) procedure is one of the most effective methods for solving SAT problems. It is well known that its efficiency depends on the choice of the branching rule. Different branching rules are proposed in the literature. Unit Propagation look-ahead (UPLA) branching rule was one of the main improvements in the DPLL procedure (e.g.,[10]). The UPLA branching rule integrated in satz SAT solver [10] performs a series of variable filtering process at each node as a static variable filtering agency. In this paper we introduce and experiment with dynamic variable filtering (DVF) based branching rule which extends the UPLA heuristic process for doing more filtering and choosing a best branching variable from an irreducible sub-formula. To enhance the performance of DVF branching rule, we integrate neighborhood variable ordering heuristic (NVO) for exploring only the neighborhood variables of the current assigned variable. Experimental results of DVF+NVO branching rule on a number of real-world benchmark instances and quasigroup problems prove our approaches to be useful in many circumstances.
-
heuristics based on Unit Propagation for satisfiability problems
International Joint Conference on Artificial Intelligence, 1997Co-Authors: Chu Min Li, Anbulagan AnbulaganAbstract:The paper studies new Unit Propagation based heuristics for Davis-Putnam-Loveland (DPL) procedure. These are the novel combinations of Unit Propagation and the usual "Maximum Occurrences in clauses of Minimum Size" heuristics. Based on the experimental evaluations of different alternatives a new simple Unit Propagation based heuristic is put forward. This compares favorably with the heuristics employed in the current state-of-the-art DPL implementations (C-SAT, Tableau, POSIT).
-
IJCAI (1) - Heuristics based on Unit Propagation for satisfiability problems
1997Co-Authors: Chu Min Li, Anbulagan AnbulaganAbstract:The paper studies new Unit Propagation based heuristics for Davis-Putnam-Loveland (DPL) procedure. These are the novel combinations of Unit Propagation and the usual "Maximum Occurrences in clauses of Minimum Size" heuristics. Based on the experimental evaluations of different alternatives a new simple Unit Propagation based heuristic is put forward. This compares favorably with the heuristics employed in the current state-of-the-art DPL implementations (C-SAT, Tableau, POSIT).
K.a. Sakallah - One of the best experts on this subject based on the ideXlab platform.
-
IWLS - ZBDD-Based Backtrack Search SAT Solver.
2020Co-Authors: F.a. Aloul, M.n. Mneimneh, K.a. SakallahAbstract:We introduce a new approach to Boolean satisfiability that combines backtrack search techniques and zero-suppressed binary decision diagrams (ZBDDs). This approach implicitly represents satisfiability instances using ZBDDs, and performs search using an efficient implementation of Unit Propagation on the ZBDD structure. We describe how to perform backtrack search using ZBDDs as the underlying structure for clause representation. This methodology, which adapts backtrack search algorithms to such implicit representations, allows for a potential exponential increase in the size of the problems that can be handled. Our experimental results show consistent speedups over conventional approaches.
-
Search-based SAT using zero-suppressed BDDs
Proceedings 2002 Design Automation and Test in Europe Conference and Exhibition, 2002Co-Authors: F.a. Aloul, M.n. Mneimneh, K.a. SakallahAbstract:We introduce a new approach to Boolean satisfiability (SAT) that combines backtrack search techniques and zero-suppressed binary decision diagrams (ZBDDs). This approach implicitly represents SAT instances using ZBDDs, and performs search using an efficient implementation of Unit Propagation on the ZBDD structure. The adaptation of backtrack search algorithms to such an implicit representation allows for a potential exponential increase in the size of problems that can be handled.
-
DATE - Search-Based SAT Using Zero-Suppressed BDDs
Proceedings 2002 Design Automation and Test in Europe Conference and Exhibition, 2002Co-Authors: F.a. Aloul, M.n. Mneimneh, K.a. SakallahAbstract:We introduce a new approach to Boolean satisfiability (SAT) that combines backtrack search techniques and zero-suppressed binary decision diagrams (ZBDDs). This approach implicitly represents SAT instances using ZBDDs, and performs search using an efficient implementation of Unit Propagation on the ZBDD structure. The adaptation of backtrack search algorithms to such an implicit representation allows for a potential exponential increase in the size of problems that can be handled.
Takayuki Suyama - One of the best experts on this subject based on the ideXlab platform.
-
solving satisfiability problems on fpgas using experimental Unit Propagation
Principles and Practice of Constraint Programming, 1999Co-Authors: Takayuki Suyama, Makoto Yokoo, Akira NagoyaAbstract:This paper presents new results on an innovative approach for solving satisfiability problems (SAT), that is, creating a logic circuit that is specialized to solve each problem instance on Field Programmable Gate Arrays (FPGAs). This approach has become feasible due to recent advances in Reconfigurable Computing, and has opened up an exciting new research field in algorithm design.
-
IPPS/SPDP Workshops - Solving Satisfiability Problems on FPGAs using Experimental Unit Propagation Heuristic
Lecture Notes in Computer Science, 1999Co-Authors: Takayuki Suyama, Makoto Yokoo, Akira NagoyaAbstract:This paper presents new results on an approach for solving satisfiability problems (SAT), that is, creating a logic circuit that is specialized to solve each problem instance on Field Programmable Gate Arrays (FPGAs). This approach has become feasible due to recent advances in Reconfigurable Computing.
-
solving satisfiability problems on fpgas using experimental Unit Propagation heuristic
International Parallel Processing Symposium, 1999Co-Authors: Takayuki Suyama, Makoto Yokoo, Akira NagoyaAbstract:This paper presents new results on an approach for solving satisfiability problems (SAT), that is, creating a logic circuit that is specialized to solve each problem instance on Field Programmable Gate Arrays (FPGAs). This approach has become feasible due to recent advances in Reconfigurable Computing.
