Parallel Execution of State Space Explorations using Different Kinds of Dynamics

M. Nagamatu and K. Zhang (Japan)


State space exploration, neural network, local search,satisfiability problem, Lagrangian method.


For the satisfiability problem (SAT), the technique of parallel execution of solvers of different algorithms to explore the state space has been proposed. In this paper we propose a generalized technique called “heterogeneous parallel execution”, and prove a theorem which states an advantage of this technique, i.e., the parallel execution of plural algorithms is more efficient than the parallel execution of single algorithm. We also give a simple guideline to use this technique. The results of experiments of solving the SAT support these considerations.

Important Links:

Go Back