Exploiting subproblem optimization in SAT-based MaxSAT algorithms
Carlos Ansótegui (),
Joel Gabàs () and
Jordi Levy ()
Additional contact information
Carlos Ansótegui: Universitat de Lleida
Joel Gabàs: Universitat de Lleida
Jordi Levy: IIIA-CSIC
Journal of Heuristics, 2016, vol. 22, issue 1, No 1, 53 pages
Abstract:
Abstract 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.
Keywords: Constraint optimization; Satisfiability; Maximum Satisfiability (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)
Downloads: (external link)
http://link.springer.com/10.1007/s10732-015-9300-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:22:y:2016:i:1:d:10.1007_s10732-015-9300-7
Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732
DOI: 10.1007/s10732-015-9300-7
Access Statistics for this article
Journal of Heuristics is currently edited by Manuel Laguna
More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().