Please use this identifier to cite or link to this item:

http://hdl.handle.net/10609/125106
Full metadata record
DC FieldValueLanguage
dc.contributor.authorHeras, Federico-
dc.contributor.authorBañeres Besora, David-
dc.contributor.otherUniversity College Dublin-
dc.contributor.otherUniversitat Oberta de Catalunya (UOC)-
dc.date.accessioned2020-12-01T13:48:52Z-
dc.date.available2020-12-01T13:48:52Z-
dc.date.issued2010-11-01-
dc.identifier.citationHeras, F. & Bañeres, D. (2010). The Impact of Max-SAT Resolution-Based Preprocessors on Local Search Solvers. Journal on Satisfiability, Boolean Modeling and Computation, 7(2-3), 89-126. doi: 10.3233/SAT190080-
dc.identifier.issn1574-0617MIAR
-
dc.identifier.urihttp://hdl.handle.net/10609/125106-
dc.description.abstractIn this paper we analyze three well-known preprocessors for Max-SAT. The first preprocessor is based on the so-called variable saturation. The second preprocessor is based on the resolution mechanism incorporated in modern branch and bound solvers. The third preprocessor is specific for the Maximum Clique problem and other problems with similar encoding in WCNF such as minimum vertex covering and combinatorial auctions. Our experimental investigation is divided in two parts. In the first part, we study the effect of the preprocessors on several problem instances using different metrics. In the second part, the effect of each preprocessor is analyzed in some of the most relevant Max-SAT local search algorithms of the literature including Gsat, Walksat, Adaptnovelty+, Irots and Saps. Results indicate that some of these algorithms find much better solutions after the preprocessor. Furthermore, some preprocessed instances can be solved to optimality with local search under very specific conditions.en
dc.format.mimetypeapplication/pdf-
dc.language.isoeng-
dc.publisherJournal on Satisfiability, Boolean Modeling and Computation-
dc.relation.ispartofJournal on Satisfiability, Boolean Modeling and Computation, 2010, 7(2-3)-
dc.relation.urihttp://doi.org/10.3233/SAT190080-
dc.rights(c) Author/s-
dc.subjectmax-SATen
dc.subjectstochastic local searchen
dc.subjectinferenceen
dc.subjectmax-SATes
dc.subjectbúsqueda local estocásticaes
dc.subjectinferenciaes
dc.subjectmax-SATca
dc.subjectrecerca local estocàsticaca
dc.subjectinferènciaca
dc.subject.lcshAlgorithmsen
dc.titleThe impact of Max-SAT resolution-based preprocessors on local search solvers-
dc.typeinfo:eu-repo/semantics/article-
dc.typeinfo:eu-repo/semantics/publishedVersion-
dc.subject.lemacAlgorismesca
dc.subject.lcshesAlgoritmoses
dc.rights.accessRightsinfo:eu-repo/semantics/openAccess-
dc.identifier.doi10.3233/SAT190080-
dc.gir.idAR/0000002930-
Appears in Collections:Articles
Articles

Files in This Item:
File SizeFormat 
Bañeres_JSAT_Impact_Max-SAT.pdf494.76 kBAdobe PDFView/Open

Items in repository are protected by copyright, with all rights reserved, unless otherwise indicated.