English   español  
Por favor, use este identificador para citar o enlazar a este item: http://hdl.handle.net/10261/155497
COMPARTIR / IMPACTO:
Estadísticas
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:
Título

Exploiting subproblem optimization in SAT-based MaxSAT algorithms

AutorAnsotegui, Carlos; Gabas, Joel; Levy, Jordi
Palabras claveSatisfiability
Maximum Satisfiability
Constraint optimization
Fecha de publicación2016
EditorSpringer
CitaciónJournal of Heuristics 22: 1- 53 (2016)
ResumenThe 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
Identificadoresdoi: 10.1007/s10732-015-9300-7
issn: 1381-1231
Aparece en las colecciones: (IIIA) Artículos
Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
accesoRestringido.pdf15,38 kBAdobe PDFVista previa
Visualizar/Abrir
Mostrar el registro completo
 


NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.