University of Limerick Institutional Repository

An empirical study of encodings for group MaxSAT ⋆

DSpace Repository

Show simple item record

dc.contributor.author Heras, Federico
dc.contributor.author Morgado, Antonio
dc.contributor.author Marques-Silva, Joao
dc.date.accessioned 2013-01-02T14:25:28Z
dc.date.available 2013-01-02T14:25:28Z
dc.date.issued 2012
dc.identifier.uri http://hdl.handle.net/10344/2769
dc.description peer-reviewed en_US
dc.description.abstract Weighted Partial MaxSAT (WPMS) is a well-known optimization variant of Boolean Satisfiability (SAT) that finds a wide range of practical applications.WPMS divides the formula in two sets of clauses: The hard clauses that must be satisfied and the soft clauses that can be unsatisfied with a penalty given by their associated weight. However, some applications may require each constraint to be modeled as a set or group of clauses. The resulting formalism is referred to as Group MaxSAT. This paper overviews Group MaxSAT, and shows how several optimization problems can be modeled as Group MaxSAT. Several en- codings from Group MaxSAT to standard MaxSAT are formalized and refined. A comprehensive empirical study compares the performance of several MaxSAT solvers with the proposed encodings. The results indicate that, depending on the underlying MaxSAT solver and problem domain, the solver may perform better with a given encoding than with the others. en_US
dc.language.iso eng en_US
dc.publisher Springer en_US
dc.relation.ispartofseries The 25th Canadian Conference on Artificial Intelligence (AI2012). Lecture Notes in Computer Science;7310, pp. 85-96
dc.relation.uri http://dx.doi.org/10.1007/978-3-642-30353-1_8
dc.rights The original publication is available at www.springerlink.com en_US
dc.subject artificial intelligence en_US
dc.subject WPMS en_US
dc.subject software engineering en_US
dc.title An empirical study of encodings for group MaxSAT ⋆ en_US
dc.type info:eu-repo/semantics/conferenceObject en_US
dc.type.supercollection all_ul_research en_US
dc.type.supercollection ul_published_reviewed en_US
dc.contributor.sponsor SFI en_US
dc.relation.projectid BEACON 09/IN.1/I2618 en_US
dc.rights.accessrights info:eu-repo/semantics/openAccess en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search ULIR


Browse

My Account

Statistics