A Study of Parallel Continuous Local Search
📰 ArXiv cs.AI
Learn how to apply parallel Continuous Local Search to solve Boolean satisfiability problems with symmetric pseudo-Boolean constraints
Action Steps
- Formulate a Boolean satisfiability problem with symmetric pseudo-Boolean constraints
- Relax the problem to a continuous optimisation problem with a differentiable objective function
- Apply parallel Continuous Local Search to find global minimisers
- Map the global minimisers to satisfying assignments of the SAT problem
- Evaluate the performance of parallel CLS on various problem instances
Who Needs to Know This
This study benefits researchers and developers working on optimization problems and Boolean satisfiability, particularly those interested in parallel processing and continuous local search techniques.
Key Insight
💡 Parallel CLS can be used to solve Boolean satisfiability problems by relaxing them to continuous optimisation problems
Share This
💡 Parallel Continuous Local Search for Boolean satisfiability problems
Key Takeaways
Learn how to apply parallel Continuous Local Search to solve Boolean satisfiability problems with symmetric pseudo-Boolean constraints
Full Article
Title: A Study of Parallel Continuous Local Search
Abstract:
arXiv:2606.06656v1 Announce Type: new Abstract: We study parallel Continuous Local Search (CLS) as a solution approach for Boolean satisfiability problems with symmetric pseudo-Boolean (PB) constraints. Here, the $n$-variable PB-satisfiability problem is relaxed to a continuous optimisation problem with a differentiable objective function on an $n$-dimensional hypercube. For satisfiable instances, the global minimisers of this optimisation problem correspond to satisfying assignments of the SAT
Abstract:
arXiv:2606.06656v1 Announce Type: new Abstract: We study parallel Continuous Local Search (CLS) as a solution approach for Boolean satisfiability problems with symmetric pseudo-Boolean (PB) constraints. Here, the $n$-variable PB-satisfiability problem is relaxed to a continuous optimisation problem with a differentiable objective function on an $n$-dimensional hypercube. For satisfiable instances, the global minimisers of this optimisation problem correspond to satisfying assignments of the SAT
DeepCamp AI