A novel local search based on variable-focusing for random K-SAT
We introduce a new local search algorithm for satisfiability problems. Usual approaches focus uniformly on unsatisfied clauses. The new method works by picking uniformly random variables in unsatisfied clauses. A Variable-based Focused Metropolis Search (V-FMS) is then applied to random 3-SAT. We show that it is quite comparable in performance to the clause-based FMS. Consequences for algorithmic design are discussed.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Variable Search Stepsize for Randomized Local Search in Multi-Objective Combinatorial Optimization
Over the past two decades, research in evolutionary multi-objective optimization has predominantly focused on continuous domains, with comparatively limited attention given to multi-objective combinatorial optimization p…
Unweighted Stochastic Local Search can be Effective for Random CSP Benchmarks
We present ULSA, a novel stochastic local search algorithm for random binary constraint satisfaction problems (CSP). ULSA is many times faster than the prior state of the art on a widely-studied suite of random CSP bench…
Improving probability selecting based weights for Satisfiability Problem
The Boolean Satisfiability problem (SAT) is important on artificial intelligence community and the impact of its solving on complex problems. Recently, great breakthroughs have been made respectively on stochastic local …
Variable SelectionA Primer on Causal Analysis
We provide a conceptual map to navigate causal analysis problems. Focusing on the case of discrete random variables, we consider the case of causal effect estimation from observational data. The presented approaches appl…
NavigateConcentration Inequalities for the Stochastic Optimization of Unbounded Objectives with Application to Denoising Score Matching
We derive novel concentration inequalities that bound the statistical error for a large class of stochastic optimization problems, focusing on the case of unbounded objective functions. Our derivations utilize the follow…
DenoisingStochastic Optimization