Por favor, use este identificador para citar o enlazar a este item:
http://hdl.handle.net/10261/155497
COMPARTIR / EXPORTAR:
SHARE CORE BASE | |
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL | DATACITE | |
Título: | Exploiting subproblem optimization in SAT-based MaxSAT algorithms |
Autor: | Ansotegui, Carlos; Gabas, Joel; Levy, Jordi CSIC ORCID | Palabras clave: | Satisfiability Maximum satisfiability Constraint optimization |
Fecha de publicación: | 2016 | Editor: | Springer Nature | Citación: | Journal of Heuristics 22: 1- 53 (2016) | Resumen: | The 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. | URI: | http://hdl.handle.net/10261/155497 | DOI: | 10.1007/s10732-015-9300-7 | Identificadores: | doi: 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.pdf | 15,38 kB | Adobe PDF | Visualizar/Abrir |
CORE Recommender
SCOPUSTM
Citations
18
checked on 21-mar-2024
WEB OF SCIENCETM
Citations
14
checked on 26-feb-2024
Page view(s)
218
checked on 27-mar-2024
Download(s)
86
checked on 27-mar-2024
Google ScholarTM
Check
Altmetric
Altmetric
NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.