Cooperative parallel SAT local search with path relinking
| dc.contributor.author | Jarvis, Padraigh | |
| dc.contributor.author | Arbelaez, Alejandro | |
| dc.date.accessioned | 2020-07-29T08:24:53Z | |
| dc.date.available | 2020-07-29T08:24:53Z | |
| dc.date.issued | 2020-04-09 | |
| dc.date.updated | 2020-07-28T12:22:42Z | |
| dc.description.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. | en |
| dc.description.status | Peer reviewed | en |
| dc.description.version | Accepted Version | en |
| dc.format.mimetype | application/pdf | en |
| dc.identifier.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 | en |
| dc.identifier.doi | 10.1007/978-3-030-43680-3_6 | en |
| dc.identifier.endpage | 98 | en |
| dc.identifier.isbn | 978-3-030-43679-7 | |
| dc.identifier.isbn | 978-3-030-43680-3 | |
| dc.identifier.journaltitle | Lecture Notes in Computer Science | en |
| dc.identifier.startpage | 83 | en |
| dc.identifier.uri | https://hdl.handle.net/10468/10322 | |
| dc.identifier.volume | 12102 | en |
| dc.language.iso | en | en |
| dc.publisher | Springer Nature Switzerland AG | en |
| dc.rights | © 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 | en |
| dc.subject | SAT | en |
| dc.subject | Parallel local search | en |
| dc.title | Cooperative parallel SAT local search with path relinking | en |
| dc.type | Conference item | en |
