Pasar al contenido principal

SISTEMAS DE DEMOSTRACION PRACTICOS MAS ALLA DE RESOLUCION

PID2019-109137GB-C21

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2019
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSIDAD DE LLEIDA

Resultados relacionados

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

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

On the Density of States of Boolean Formulas

  • Ansótegui Gil, Carlos José
  • Bonet, Maria Luisa
  • Levy, Jordi
Given a CNF formula with m clauses, and an integer k, where 0 ≤ k ≤ m, a density of states procedure will count the number of truth assignments that falsify exactly k clauses of the formula. We present the first approach to compute the density of states of Boolean formulas exactly. This is the first non-trivial result on this known hard problem. There are previous approaches for computing approximately the density of states of Boolean Formulas [1,2], where the authors point out they are not aware of any complete solver that is able to compute the exact density of states. The present work is the first step to fill this gap. The idea is, given a formula φ and a parameter c, construct a formula φc such that, the number of models of φc is the number of assignments that falsify exactly c clauses of φ. Then, a #SAT solver is used as a black box to count the models of φc. This approach can be also used to compute approximately the density of states by using an approximate #SAT solver. Finally, the method can be extended trivially to deal with Weighted Boolean formulas., This research is part of the projects PROOFS (PID2019-109137GB-C21) and PROOFS BEYOND (PID2022-138506NB-C21) funded by the AEI and MCIN
Repositori Obert UdL
Publicación Contribución de congreso (ConferenceOutput)

OptiLog: A Framework for SAT-based Systems

  • Ansótegui Gil, Carlos José
  • Ojeda Contreras, Jesús
  • Pacheco, Antonio
  • Pon, Josep
  • Salvia Hornos, Josep M.
  • Torres, Eduard
We present OptiLog, a new Python framework for rapid prototyping of SAT-based systems. OptiLog allows to use and integrate SAT solvers currently developed in C/C++ just by implementing the iSAT C++ interface. It also provides a Python binding to the PBLib C++ toolkit for encoding Pseudo Boolean and Cardinality constraints. Finally, it leverages the power of automatic con gurators by allowing to easily create con guration scenarios including multiple solvers and encoders., Supported by MINECO-FEDER TASSAT3 (TIN2016-76573-C2-2-P), MICINNs PROOFS (PID2019-109137GB-C21) and FPU fellowship (FPU18/02929).
Repositori Obert UdL
Publicación Contribución de congreso (ConferenceOutput)

OptiLog V2: Model, Solve, Tune and Run

  • Alòs Pascual, Josep
  • Ansótegui Gil, Carlos José
  • Salvia Hornos, Josep M.
  • Torres, Eduard
We present an extension of the OptiLog Python framework. We fully redesign the solvers module to support the dynamic loading of incremental SAT solvers with support for external libraries. We introduce new modules for modelling problems into Non-CNF format with support for Pseudo Boolean constraints, for evaluating and parsing the results of applications, and we add support for constrained execution of blackbox programs and SAT-heritage integration. All these enhancements allow OptiLog to become a swiss knife for SAT-based applications in academic and industrial environments., Supported by Grant PID2019-109137GB-C21 funded by MCIN/AEI/10.13039/501100011033, PANDEMIES 2020 by Agencia de Gestio d’Ajuts Universitaris i de Recerca (AGAUR), Departament d’Empresa i Coneixement de la Generalitat de Catalunya, FONDO SUPERA COVID-19 funded by Crue-CSIC-SANTANDER, and the MICNN FPU fellowship (FPU18/02929).
Repositori Obert UdL
Publicación Contribución de congreso (ConferenceOutput)

Building High Strength Mixed Covering Arrays with Constraints

  • Ansótegui Gil, Carlos José
  • Ojeda Contreras, Jesús
  • Torres, Eduard
Covering arrays have become a key piece in Combinatorial Testing. In particular, we focus on the efficient construction of Covering Arrays with Constraints of high strength. SAT solving technology has been proven to be well suited when solving Covering Arrays with Constraints. However, the size of the SAT reformulations rapidly grows up with higher strengths. To this end, we present a new incomplete algorithm that mitigates substantially memory blow-ups. The experimental results confirm the goodness of the approach, opening avenues for new practical applications., Supported by MICINNs PROOFS (PID2019-109137GB-C21) and FPU fellowship (FPU18/ 02929)
Repositori Obert UdL
Publicación Contribución de congreso (ConferenceOutput)

Exploiting Configurations of MaxSAT Solvers

  • Alòs Pascual, Josep
  • Ansótegui Gil, Carlos José
  • Salvia Hornos, Josep M.
  • Torres, Eduard
In this paper, we describe how we can effectively exploit alternative parameter configurations to a MaxSAT solver. We describe how these configurations can be computed in the context of MaxSAT. In particular, we experimentally show how to easily combine configurations of a non-competitive solver to obtain a better solving approach., This work was supported by MCIN/AEI/10.13039/501100011033 (Grant: PID2019- 109137GB-C21), Agencia de Gestio d’Ajuts Universitaris i de Recerca (AGAUR), Departament d’Empresa i Coneixement de la Generalitat de Catalunya (Grant: 2022 FI_B 00010)
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).
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

On vanishing sums of roots of unity in polynomial calculus and sum-of-squares

  • Bonacina, Ilario|||0000-0002-5697-8070
  • Galesi, Nicola
  • Lauria, Massimo
Vanishing sums of roots of unity can be seen as a natural generalization of knapsack from Boolean variables to variables taking values over the roots of unity. We show that these sums are hard to prove for polynomial calculus and for sum-of-squares, both in terms of degree and size., The first author was supported by the MICIN grants PID2019-109137GB-C22 and IJC2018-035334-I, and partially by the grant PID2019-109137GB-C21., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Exploiting Configurations of MaxSAT Solvers

  • Alòs Pascual, Josep
  • Ansótegui Gil, Carlos José
  • Salvia Hornos, Josep M.
  • Torres, Eduard
In this paper, we describe how we can effectively exploit alternative parameter configurations to a MaxSAT solver. We describe how these configurations can be computed in the context of MaxSAT. In particular, we experimentally show how to easily combine configurations of a non-competitive solver to obtain a better solving approach., This work was supported by MCIN/AEI/10.13039/501100011033 (Grant: PID2019- 109137GB-C21), Agencia de Gestio d’Ajuts Universitaris i de Recerca (AGAUR), Departament d’Empresa i Coneixement de la Generalitat de Catalunya (Grant: 2022 FI_B 00010)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Building High Strength Mixed Covering Arrays with Constraints

  • Ansótegui Gil, Carlos José
  • Ojeda Contreras, Jesús
  • Torres, Eduard
Covering arrays have become a key piece in Combinatorial Testing. In particular, we focus on the efficient construction of Covering Arrays with Constraints of high strength. SAT solving technology has been proven to be well suited when solving Covering Arrays with Constraints. However, the size of the SAT reformulations rapidly grows up with higher strengths. To this end, we present a new incomplete algorithm that mitigates substantially memory blow-ups. The experimental results confirm the goodness of the approach, opening avenues for new practical applications., Supported by MICINNs PROOFS (PID2019-109137GB-C21) and FPU fellowship (FPU18/ 02929)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

OptiLog: A Framework for SAT-based Systems

  • Ansótegui Gil, Carlos José
  • Ojeda Contreras, Jesús
  • Pacheco, Antonio
  • Pon, Josep
  • Salvia Hornos, Josep M.
  • Torres, Eduard
We present OptiLog, a new Python framework for rapid prototyping of SAT-based systems. OptiLog allows to use and integrate SAT solvers currently developed in C/C++ just by implementing the iSAT C++ interface. It also provides a Python binding to the PBLib C++ toolkit for encoding Pseudo Boolean and Cardinality constraints. Finally, it leverages the power of automatic con gurators by allowing to easily create con guration scenarios including multiple solvers and encoders., Supported by MINECO-FEDER TASSAT3 (TIN2016-76573-C2-2-P), MICINNs PROOFS (PID2019-109137GB-C21) and FPU fellowship (FPU18/02929).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

OptiLog V2: Model, Solve, Tune and Run

  • Alòs Pascual, Josep
  • Ansótegui Gil, Carlos José
  • Salvia Hornos, Josep M.
  • Torres, Eduard
We present an extension of the OptiLog Python framework. We fully redesign the solvers module to support the dynamic loading of incremental SAT solvers with support for external libraries. We introduce new modules for modelling problems into Non-CNF format with support for Pseudo Boolean constraints, for evaluating and parsing the results of applications, and we add support for constrained execution of blackbox programs and SAT-heritage integration. All these enhancements allow OptiLog to become a swiss knife for SAT-based applications in academic and industrial environments., Supported by Grant PID2019-109137GB-C21 funded by MCIN/AEI/10.13039/501100011033, PANDEMIES 2020 by Agencia de Gestio d’Ajuts Universitaris i de Recerca (AGAUR), Departament d’Empresa i Coneixement de la Generalitat de Catalunya, FONDO SUPERA COVID-19 funded by Crue-CSIC-SANTANDER, and the MICNN FPU fellowship (FPU18/02929).
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).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

On vanishing sums of roots of unity in polynomial calculus and sum-of-squares

  • Bonacina, Ilario
  • Galesi, Nicola
  • Lauria, Massimo
Vanishing sums of roots of unity can be seen as a natural generalization of knapsack from Boolean variables to variables taking values over the roots of unity. We show that these sums are hard to prove for polynomial calculus and for sum-of-squares, both in terms of degree and size., The first author was supported by the MICIN grants PID2019-109137GB-C22 and IJC2018-035334-I, and partially by the grant PID2019-109137GB-C21., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

On the Density of States of Boolean Formulas

  • Ansótegui Gil, Carlos José
  • Bonet, Maria Luisa
  • Levy, Jordi
Given a CNF formula with m clauses, and an integer k, where 0 ≤ k ≤ m, a density of states procedure will count the number of truth assignments that falsify exactly k clauses of the formula. We present the first approach to compute the density of states of Boolean formulas exactly. This is the first non-trivial result on this known hard problem. There are previous approaches for computing approximately the density of states of Boolean Formulas [1,2], where the authors point out they are not aware of any complete solver that is able to compute the exact density of states. The present work is the first step to fill this gap. The idea is, given a formula φ and a parameter c, construct a formula φc such that, the number of models of φc is the number of assignments that falsify exactly c clauses of φ. Then, a #SAT solver is used as a black box to count the models of φc. This approach can be also used to compute approximately the density of states by using an approximate #SAT solver. Finally, the method can be extended trivially to deal with Weighted Boolean formulas., This research is part of the projects PROOFS (PID2019-109137GB-C21) and PROOFS BEYOND (PID2022-138506NB-C21) funded by the AEI and MCIN