Cooperative parallel SAT local search with path relinking
Springer Nature Switzerland AG
In this paper, we propose the use of path relinking to improve the performance of parallel portfolio-based local search solvers for the Boolean Satisfiability problem. In the portfolio-based framework several algorithms explore the search space in parallel, either independently or cooperatively with some communication between the solvers. Path relinking is a method to maintain an appropriate balance between diversification and intensification (and explore paths that aggregate elite solutions) to properly craft a new assignment for the variables to restart from. We present an empirical study that suggest that path relinking outperforms a set of well-known parallel portfolio-based local search algorithms with and without cooperation.
SAT , Parallel local search
Jarvis, P. and Arbelaez, A. (2020) 'Cooperative parallel SAT local search with path relinking', in Paquete L. and Zarges C. (eds) Evolutionary Computation in Combinatorial Optimization: EvoCOP 2020, Seville, Spain, 15-17 April, Lecture Notes in Computer Science, vol 12102, Springer, Cham, pp. 83-98. doi: 10.1007/978-3-030-43680-3_6
© 2020, Springer Nature Switzerland AG. This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science. The final authenticated version is available online at: http://dx.doi.org/10.1007/978-3-030-43680-3_6