Options
noSAT-MaxSATv2
Citation Link: https://doi.org/10.15480/882.9031
Publikationstyp
Conference Paper
Publikationsdatum
2023
Sprache
English
Start Page
27
End Page
28
Citation
MaxSAT Evaluation (2023)
Contribution to Conference
Publisher
Department of Computer Science, University of Helsinki
Peer Reviewed
false
Using a SAT solver to solve MaxSAT is a well-established and efficient method. However, in resource-constrained computing environments, e.g., embedded systems, such algorithm designs can be hard to realize. With noSAT-MaxSAT, we explore alternatives that do not rely on an external, dedicated SAT solver, by executing an anytime local-search MaxSAT solving algorithm only on the hard clauses of the formula instead. In many real-world problems a significant portion of the hard clauses feature not more than two literals. Therefore, in noSAT-MaxSATv2 we integrated a linear-time algorithm for 2-SAT as a preprocessing step to find a good initial assignment before proceeding to solve the remaining hard clauses with local search. Additionally, compared to the previous version of noSAT-MaxSAT, we updated the local-search algorithm from SATLike to NuWLS, the algorithm which won all incomplete tracks of the MaxSAT Evaluation 2022.
DDC Class
004: Computer Sciences
Publication version
publishedVersion
Loading...
Name
noSAT-MaxSAT.pdf
Type
main article
Size
105.68 KB
Format
Adobe PDF