Cooperative parallel SAT local search with path relinking
Loading...
Files
Accepted Version
Date
2020-04-09
Authors
Jarvis, Padraigh
Arbelaez, Alejandro
Journal Title
Journal ISSN
Volume Title
Publisher
Springer Nature Switzerland AG
Published Version
Abstract
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.
Description
Keywords
SAT , Parallel local search
Citation
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
Link to publisher’s version
Copyright
© 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