English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/155497
Share/Impact:
Statistics
logo share SHARE logo core CORE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:

Title

Exploiting subproblem optimization in SAT-based MaxSAT algorithms

AuthorsAnsotegui, Carlos; Gabas, Joel; Levy, Jordi
KeywordsSatisfiability
Maximum Satisfiability
Constraint optimization
Issue Date2016
PublisherSpringer
CitationJournal of Heuristics 22: 1- 53 (2016)
AbstractThe Maximum Satisfiability (MaxSAT) problem is an optimization variant of the Satisfiability (SAT) problem. Several combinatorial optimization problems can be translated into a MaxSAT formula. Among exact MaxSAT algorithms, SAT-based MaxSAT algorithms are the best performing approaches for real-world problems. We have extended the WPM2 algorithm by adding several improvements. In particular, we show that by solving some subproblems of the original MaxSAT instance we can dramatically increase the efficiency of WPM2. This led WPM2 to achieve the best overall results at the international MaxSAT Evaluation 2013 (MSE13) on industrial instances. Then, we present additional techniques and heuristics to further exploit the information retrieved from the resolution of the subproblems. We exhaustively analyze the impact of each improvement what contributes to our understanding of why they work. This architecture allows to convert exact algorithms into efficient incomplete algorithms. The resulting solver had the best results on industrial instances at the incomplete track of the latest international MSE. © 2015, Springer Science+Business Media New York.
URIhttp://hdl.handle.net/10261/155497
DOI10.1007/s10732-015-9300-7
Identifiersdoi: 10.1007/s10732-015-9300-7
issn: 1381-1231
Appears in Collections:(IIIA) Artículos
Files in This Item:
File Description SizeFormat 
accesoRestringido.pdf15,38 kBAdobe PDFThumbnail
View/Open
Show full item record
Review this work
 

Related articles:


WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.