English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/133779
Share/Impact:
Statistics
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 | DATACITE
Exportar a otros formatos:

Title

SAT-based MaxSAT algorithms

AuthorsAnsotegui, Carlos; Bonet, Maria Luisa; Levy, Jordi CSIC ORCID
KeywordsBoolean optimization
MaxSAT
SAT
Issue Date2013
PublisherElsevier
CitationArtificial Intelligence 196: 77- 105 (2013)
AbstractMany industrial optimization problems can be translated to MaxSAT. Although the general problem is NP hard, like SAT, many practical problems may be solved using modern MaxSAT solvers. In this paper we present several algorithms specially designed to deal with industrial or real problems. All of them are based on the idea of solving MaxSAT through successive calls to a SAT solver. We show that this SAT-based technique is efficient in solving industrial problems. In fact, all state-of-the-art MaxSAT solvers that perform well in industrial instances are based on this technique. In particular, our solvers won the 2009 partial MaxSAT and the 2011 weighted partial MaxSAT industrial categories of the MaxSAT evaluation. We prove the correctness of all our algorithms. We also present a complete experimental study comparing the performance of our algorithms with latest MaxSAT solvers. © 2013 Elsevier B.V.
URIhttp://hdl.handle.net/10261/133779
DOIhttp://dx.doi.org/10.1016/j.artint.2013.01.002
Identifiersdoi: 10.1016/j.artint.2013.01.002
issn: 0004-3702
Appears in Collections:(IIIA) Artículos
Files in This Item:
File Description SizeFormat 
accesoRestringido.pdf15,38 kBAdobe PDFThumbnail
View/Open
Show full item record
Review this work
 

Related articles:


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