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

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


Improving WPM2 for (Weighted) Partial MaxSAT

AuthorsAnsotegui, Carlos; Bonet, Maria Luisa; Gabas, Joel; Levy, Jordi CSIC ORCID
Issue Date16-Sep-2013
CitationLecture Notes in Computer Science 8124. Principles and Practice of Constraint Programming, 19th International Conference, CP 2013, Uppsala, Sweden, September 16-20, 2013. Proceedings. pp 117-132.
AbstractWeighted Partial MaxSAT (WPMS) is an optimization variant of the Satisfiability (SAT) problem. Several combinatorial optimization problems can be translated into WPMS. In this paper we extend the state-of-the-art WPM2 algorithm by adding several improvements, and implement it on top of an SMT solver. In particular, we show that by focusing search on solving to optimality subformulas of the original WPMS instance we increase the efficiency of WPM2. From the experimental evaluation we conducted on the PMS and WPMS instances at the 2012 MaxSAT Evaluation, we can conclude that the new approach is both the best performing for industrial instances, and for the union of industrial and crafted instances.
Identifiersdoi: 10.1007/978-3-642-40627-0_12
isbn: 978-3-642-40626-3
Appears in Collections:(IIIA) Comunicaciones congresos
Files in This Item:
File Description SizeFormat 
LNCS8124_117-32.pdf222,57 kBUnknownView/Open
Show full item record
Review this work

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