Options
noSAT-MaxSATv2
Citation Link: https://doi.org/10.15480/882.9031
Publikationstyp
Conference Paper
Date Issued
2023
Sprache
English
TORE-DOI
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