Pasar al contenido principal

Resultados relacionados

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

Repositori Obert UdL
Publicación Contribución de congreso (ConferenceOutput)

Reducing SAT to Max2SAT

  • Ansótegui Gil, Carlos José
  • Levy, Jordi
In the literature we find reductions from 3SAT to Max2SAT. These reductions are based on the usage of a gadget, i.e., a combinatorial structure that allows translating constraints of one problem to constraints of another. Unfortunately, the generation of these gadgets lacks an intuitive or efficient method. In this paper, we provide an efficient and constructive method for Reducing SAT to Max2SAT and show empirical results of how MaxSAT solvers are more efficient than SAT solvers solving the translation of hard formulas for Resolution., Supported by projects PROOFS (PID2019-109137GB-C21) and EU-H2020-RIP LOGISTAR (No. 769142).
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

Clause Branching in MaxSAT and MinSAT

  • Argelich, Josep
  • Li, Chu Min
  • Manyà, Felip
  • Zhu, Zhu
Trabajo presentado en el 21st International Conference of the Catalan Association for Artificial Intelligence (CCIA 2018), celebrada en Roses (España) del 8 al 10 de Octubre de 2018, We describe a new exact procedure, inspired on recent works on tableaux, for simultaneously solving MaxSAT and MinSAT. The main novelty of our procedure is that it implements a clause branching rule that preserves both the minimum and the maximum number of clauses than can be unsatisfied. Moreover, we prove the correctness of the procedure, and provide a review of the different types of branchings which are available for MaxSAT and MinSAT. We also give some preliminary experimental results that show that the new branching rule, when implemented into an existing branch-and-bound MaxSAT solver, produces substantial gains on industrial instances of the MaxSAT Evaluation., This work was supported by Project LOGISTAR from the EU H2020 Research and Innovation Programme under Grant Agreement No. 769142, and MINECO-FEDER projects RASO (TIN2015-71799-C2-1-P/2-P)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

Phase Transition in Realistic Random SAT Models

  • Ansotegui, Carlos
  • Bonet, María Luisa
  • Levy, Jordi
Phase-transition in random SAT formulas is one of the properties best studied by theoretical SAT researchers. There exists a constant rk depending on k such that, if we choose randomly a k-SAT formula over n variables and m clauses, it will be satisfiable with high probability, if m/n < r, and unsatisfiable, otherwise. However, this criterion is useless in practice, because real-world or industrial instances have some properties not shown in random formulas. In the last years, several models of realistic random formulas have been proposed. Here we discuss about the phase transition in these models, and about the size of unsatisfiability proofs. We observe that in these models, like in real-world formulas, there is not a sharp phase transition, the transition occurs for smaller values of r, and the proofs on unsatisfiable formulas are smaller than in the classical random model. We also discuss about the strategies used by modern SAT solvers to exploit these properties., Research partially supported by the EU H2020 Research and Innovation Program under the LOGISTAR project (Grant Agreement No. 769142) and the MINECO-FEDER projects RASO (TIN2015-71799-C2-1-P) and TASSAT 3 (TIN2016-76573-C2-2-P).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Reducing SAT to Max2SAT

  • Ansótegui Gil, Carlos José
  • Levy, Jordi
In the literature we find reductions from 3SAT to Max2SAT. These reductions are based on the usage of a gadget, i.e., a combinatorial structure that allows translating constraints of one problem to constraints of another. Unfortunately, the generation of these gadgets lacks an intuitive or efficient method. In this paper, we provide an efficient and constructive method for Reducing SAT to Max2SAT and show empirical results of how MaxSAT solvers are more efficient than SAT solvers solving the translation of hard formulas for Resolution., Supported by projects PROOFS (PID2019-109137GB-C21) and EU-H2020-RIP LOGISTAR (No. 769142).