Pasar al contenido principal

TASSAT 2: TEORIA Y APLICACIONES EN SATISFACTIBILIDAD Y OPTIMIZACION DE RESTRICCIONES

TIN2013-48031-C4-4-P

•
Nombre agencia financiadora Ministerio de Economía y Competitividad
Acrónimo agencia financiadora MINECO
Programa Programa Estatal de Fomento de la Investigación Científica y Técnica de Excelencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D (Excelencia / Generación de Conocimiento)
Año convocatoria 2013
Plan Estatal 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Unidad de gestión Secretaría de Estado de Educación, Formación Profesional y Universidades
Centro beneficiario UNIVERSIDAD DE LLEIDA
Identificador persistente http://dx.doi.org/10.13039/501100003329

Resultados relacionados

Resultados totales (Incluyendo duplicados): 3
Encontrada(s) 1 página(s)

Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

On the Performance of MaxSAT and MinSAT Solvers on 2SAT-MaxOnes

  • Argelich Romà, Josep
  • Béjar Torres, Ramón
  • Fernàndez Camon, César
  • Mateu Piñol, Carles
  • Planes Cid, Jordi
We analyze and compare two solvers for Boolean optimization problems: WMaxSatz, a solver for Partial MaxSAT, and MinSatz, a solver for Partial MinSAT. Both MaxSAT and MinSAT are similar, but previous results indicate that when solving optimization problems using both solvers, the performance is quite different on some cases. For getting insights about the differences in the performance of the two solvers, we analyze their behaviour when solving 2SAT-MaxOnes problem instances, given that 2SAT-MaxOnes is probably the most simple, but NP-hard, optimization problem we can solve with them. The analysis is based first on the study of the bounds computed by both algorithms on some particular 2SAT-MaxOnes instances, characterized by the presence of certain particular structures. We find that the fraction of positive literals in the clauses is an important factor regarding the quality of the bounds computed by the algorithms. Then, we also study the importance of this factor on the typical case complexity of Random-p 2SAT-MaxOnes, a variant of the problem where instances are randomly generated with a probability p of having positive literals in the clauses. For the case p=0, the performance results indicate a clear advantage of MinSatz with respect to WMaxSatz, but as we consider positive values of p WMaxSatz starts to show a better performance, although at the same time the typical complexity of Random-p 2SAT-MaxOnes decreases as p increases. We also study the typical value of the bound computed by the two algorithms on these sets of instances, showing that the behaviour is consistent with our analysis of the bounds computed on the particular instances we studied first.
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Automated theorem provers for multiple-valued logics with satisfiability modulo theory solvers

  • Ansotegui, Carlos
  • Bofill, Miquel
  • Manyà, Felip
  • Villaret, Mateu
There is a relatively large number of papers dealing with complexity and proof theory issues of multiple-valued logics. Nevertheless, little attention has been paid so far to the development of efficient and robust solvers for such logics. In this paper we investigate how the technology of Satisfiability Modulo Theories (SMT) can be effectively used to build efficient automated theorem provers for relevant finitely-valued and infinitely-valued logics, taking the logics of Łukasiewicz, Gödel and Product as case studies. Besides, we report on an experimental investigation that evaluates the performance of SMT technology when solving multiple-valued logic problems, and compares the finitely-valued solvers for Łukasiewicz and Gödel logics with their infinitely-valued solvers from a computational point of view. We also compare the performance of SMT technology and MIP technology when testing the satisfiability on a genuine family of multiple-valued clausal forms., Research partially supported by the Generalitat de Catalunya grant AGAUR 2014-SGR-118, and the Ministerio de Economía y Competitividad projects CO-PRIVACY TIN2011-27076-C03-03, TA S S AT- 2 TIN2013-48031-C4-4-P and HeLo TIN2012-33042. The third author was supported by Mobility Grant PRX14/00195 of the Ministerio de Educación, Cultura y Deporte, Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the Performance of MaxSAT and MinSAT Solvers on 2SAT-MaxOnes

  • Argelich Romà, Josep
  • Béjar Torres, Ramón
  • Fernàndez Camon, César
  • Mateu Piñol, Carles
  • Planes Cid, Jordi
We analyze and compare two solvers for Boolean optimization problems: WMaxSatz, a solver for Partial MaxSAT, and MinSatz, a solver for Partial MinSAT. Both MaxSAT and MinSAT are similar, but previous results indicate that when solving optimization problems using both solvers, the performance is quite different on some cases. For getting insights about the differences in the performance of the two solvers, we analyze their behaviour when solving 2SAT-MaxOnes problem instances, given that 2SAT-MaxOnes is probably the most simple, but NP-hard, optimization problem we can solve with them. The analysis is based first on the study of the bounds computed by both algorithms on some particular 2SAT-MaxOnes instances, characterized by the presence of certain particular structures. We find that the fraction of positive literals in the clauses is an important factor regarding the quality of the bounds computed by the algorithms. Then, we also study the importance of this factor on the typical case complexity of Random-p 2SAT-MaxOnes, a variant of the problem where instances are randomly generated with a probability p of having positive literals in the clauses. For the case p=0, the performance results indicate a clear advantage of MinSatz with respect to WMaxSatz, but as we consider positive values of p WMaxSatz starts to show a better performance, although at the same time the typical complexity of Random-p 2SAT-MaxOnes decreases as p increases. We also study the typical value of the bound computed by the two algorithms on these sets of instances, showing that the behaviour is consistent with our analysis of the bounds computed on the particular instances we studied first.