Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/10459.1/57214
Título:
|
SAT-based MaxSAT algorithms
|
Autor/a:
|
Ansótegui Gil, Carlos José; Bonet, Maria Luisa; Levy, Jordi
|
Notas:
|
Many 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.
Research partially supported by the Ministerio de Economía y Competividad research projects ARINF TIN2009-14704-C03-01, TASSAT TIN2010-20967- C04-01/03/04. |
Materia(s):
|
-MaxSAT -SAT -Boolean optimization |
Derechos:
|
(c) Elsevier, 2013
info:eu-repo/semantics/restrictedAccess |
Tipo de documento:
|
article publishedVersion |
Editor:
|
Elsevier
|
Compartir:
|
|
Documentos con el texto completo de este documento
Mostrar el registro completo del ítem