Skip to main content

SISTEMAS DE DEMOSTRACION PRACTICOS MAS ALLA DE RESOLUCION

PID2019-109137GB-C21

•
Funding agency name Agencia Estatal de Investigación
Funding agency acronym AEI
Program Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Call Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Call year 2019
State Plan 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Beneficiary centre UNIVERSIDAD DE LLEIDA

Resultados relacionados

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

Repositori Obert UdL
Publication 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
Publication Artículo científico (JournalArticle)

Interpretable decision trees through MaxSAT

  • Alòs Pascual, Josep
  • Ansótegui Gil, Carlos José
  • Torres, Eduard
We present an approach to improve the accuracy-interpretability trade-off of Machine Learning (ML) Decision Trees (DTs). In particular, we apply Maximum Satisfiability technology to compute Minimum Pure DTs (MPDTs). We improve the runtime of previous approaches and, show that these MPDTs can outperform the accuracy of DTs generated with the ML framework sklearn., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. 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: PANDEMIES 2020); Crue-CSIC-SANTANDER (Grant: FONDO SUPERA COVID-19); Agencia de Gestio d’Ajuts Universitaris i de Recerca (AGAUR), Departament d’Empresa i Coneixement de la Generalitat de Catalunya (“Ajuts Joan Oró per a la contractació de personal investigador predoctoral en formació”, grant: 2022 FI_B 00010).
Repositori Obert UdL
Publication 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
Publication 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
Publication 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
Publication Artículo científico (JournalArticle)

Incomplete MaxSAT approaches for combinatorial testing

  • Ansótegui Gil, Carlos José
  • Manyà Serres, Felip
  • Ojeda Contreras, Jesús
  • Salvia Hornos, Josep M.
  • Torres, Eduard
We present a Satisfiability (SAT)-based approach for building Mixed Covering Arrays with Constraints of minimum length, referred to as the Covering Array Number problem. This problem is central in Combinatorial Testing for the detection of system failures. In particular, we show how to apply Maximum Satisfiability (MaxSAT) technology by describing efficient encodings for different classes of complete and incomplete MaxSAT solvers to compute optimal and suboptimal solutions, respectively. Similarly, we show how to solve through MaxSAT technology a closely related problem, the Tuple Number problem, which we extend to incorporate constraints. For this problem, we additionally provide a new MaxSAT-based incomplete algorithm. The extensive experimental evaluation we carry out on the available Mixed Covering Arrays with Constraints benchmarks and the comparison with state-of-the-art tools confirm the good performance of our approaches., We would like to thank specially Akihisa Yamada for the access to several benchmarks for our experiments and for solving some questions about his previous work on Combinatorial Testing with Constraints. This work was partially 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, ISINC (PID2019-111544GB-C21), and the MICNN FPU fellowship (FPU18/02929).
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

Scale-Free Random SAT Instances

  • Ansótegui Gil, Carlos José
  • Bonet, Maria Luisa
  • Levy, Jordi
We focus on the random generation of SAT instances that have properties similar to real-world instances. It is known that many industrial instances, even with a great number of variables, can be solved by a clever solver in a reasonable amount of time. This is not possible, in general, with classical randomly generated instances. We provide a different generation model of SAT instances, called scale-free random SAT instances. This is based on the use of a non-uniform probability distribution 𝑃(𝑖)∼𝑖−𝛽 to select variable i, where 𝛽 is a parameter of the model. This results in formulas where the number of occurrences k of variables follows a power-law distribution 𝑃(𝑘)∼𝑘−𝛿 , where 𝛿=1+1/𝛽 . This property has been observed in most real-world SAT instances. For 𝛽=0 , our model extends classical random SAT instances. We prove the existence of a SAT–UNSAT phase transition phenomenon for scale-free random 2-SAT instances with 𝛽<1/2 when the clause/variable ratio is 𝑚/𝑛=1−2𝛽(1−𝛽)2 . We also prove that scale-free random k-SAT instances are unsatisfiable with a high probability when the number of clauses exceeds 𝜔(𝑛(1−𝛽)𝑘) . The proof of this result suggests that, when 𝛽>1−1/𝑘 , the unsatisfiability of most formulas may be due to small cores of clauses. Finally, we show how this model will allow us to generate random instances similar to industrial instances, of interest for testing purposes., This research was supported by the project PROOFS, Grant PID2019-109137GB-C21 funded by MCIN/AEI/10.13039/501100011033.
Repositori Obert UdL
Publication 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
Publication 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
Publication Artículo científico (JournalArticle)

Polynomial calculus for optimization

  • Bonacina, Ilario
  • Bonet, María Luisa
  • Levy, Jordi
MaxSAT is the problem of finding an assignment satisfying the maximum number of clauses in a CNF formula. We consider a natural generalization of this problem to generic sets of polynomials and propose a weighted version of Polynomial Calculus to address this problem. Weighted Polynomial Calculus is a natural generalization of the systems MaxSAT-Resolution and weighted Resolution. Unlike such systems, weighted Polynomial Calculus manipulates polynomials with coefficients in a finite field and either weights in N or Z. We show the soundness and completeness of weighted Polynomial Calculus via an algorithmic procedure. Weighted Polynomial Calculus, with weights in N and coefficients in F2, is able to prove efficiently that Tseitin formulas on a connected graph are minimally unsatisfiable. Using weights in Z, it also proves efficiently that the Pigeonhole Principle is minimally unsatisfiable., This work was supported by the grant numbers PID2019-109137GB-C21, PID2019-109137GB-C22, IJC2018-035334-I, PID2022-138506NB-C21, and PID2022-138506NB-C22 funded by AEI., Peer reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

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

  • Bonacina, Ilario|||0000-0002-5697-8070
  • Galesi, Nicola
  • Lauria, Massimo
We introduce a novel take on sum-of-squares that is able to reason with complex numbers and still make use of polynomial inequalities. This proof system might be of independent interest since it allows to represent multivalued domains both with Boolean and Fourier encoding. We show degree and size lower bounds in this system for a natural generalization of knapsack: the vanishing sums of roots of unity. These lower bounds naturally apply to polynomial calculus as-well., The first author was supported by the Ministerio de Ciencia e Innovación MCIN/AEI/10.13039/501100011033, Spain [grant numbers PID2019-109137GB-C21, PID2019-109137GB-C22, and IJC2018-035334-I]., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication 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
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Scale-free random SAT instances

  • Ansótegui Gil, Carlos
  • Bonet Carbonell, M. Luisa|||0000-0003-1646-7177
  • Levy Díaz, Jordi
We focus on the random generation of SAT instances that have properties similar to real-world instances. It is known that many industrial instances, even with a great number of variables, can be solved by a clever solver in a reasonable amount of time. This is not possible, in general, with classical randomly generated instances. We provide a different generation model of SAT instances, called scale-free random SAT instances. This is based on the use of a non-uniform probability distribution P(i)∼i−β to select variable i, where β is a parameter of the model. This results in formulas where the number of occurrences k of variables follows a power-law distribution P(k)∼k−δ, where δ=1+1/β. This property has been observed in most real-world SAT instances. For β=0, our model extends classical random SAT instances. We prove the existence of a SAT–UNSAT phase transition phenomenon for scale-free random 2-SAT instances with β<1/2 when the clause/variable ratio is m/n=1−2β(1−β)2. We also prove that scale-free random k-SAT instances are unsatisfiable with a high probability when the number of clauses exceeds ω(n(1−β)k). The proof of this result suggests that, when β>1−1/k, the unsatisfiability of most formulas may be due to small cores of clauses. Finally, we show how this model will allow us to generate random instances similar to industrial instances, of interest for testing purposes., This research was supported by the project PROOFS, Grant PID2019-109137GB-C21 funded by MCIN/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Strength and limitations of Sherali-Adams and Nullstellensatz proof systems

  • Bonacina, Ilario|||0000-0002-5697-8070
  • Bonet Carbonell, M. Luisa|||0000-0003-1646-7177
We compare the strength of the algebraic proof systems Sherali-Adams (SA) and Nullstellensatz (NS) with Frege-style proof systems. Unlike bounded-depth Frege, SA has polynomial-size proofs of the pigeonhole principle (PHP). A natural question is whether adding PHP to bounded-depth Frege is enough to simulate SA. We show that SA, with unary integer coefficients, lies strictly between tree-like depth-1 Frege + PHP and tree-like Resolution. We introduce a levelled version of PHP (L PHP) and we show that SA with integer coefficients lies strictly between tree-like depth-1 Frege + L PHP and Resolution. Analogous results are shown for NS using the bijective (i.e. onto and functional) pigeonhole principle and a leveled version of it., This work was supported by the Ministerio de Ciencia e Innovación/Agencia Estatal de Investigación MCIN/AEI/10.13039/501100011033, Spain [grant numbers PID2019-109137GB-C21, PID2019-109137GB-C22, IJC2018-035334-I]., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication Artículo científico (JournalArticle)

Scale-free random SAT instances

  • Ansótegui Gil, Carlos
  • Bonet Carbonell, M. Luisa
  • Levy Díaz, Jordi
We focus on the random generation of SAT instances that have properties similar to real-world instances. It is known that many industrial instances, even with a great number of variables, can be solved by a clever solver in a reasonable amount of time. This is not possible, in general, with classical randomly generated instances. We provide a different generation model of SAT instances, called scale-free random SAT instances. This is based on the use of a non-uniform probability distribution P(i)∼i−β to select variable i, where β is a parameter of the model. This results in formulas where the number of occurrences k of variables follows a power-law distribution P(k)∼k−δ, where δ=1+1/β. This property has been observed in most real-world SAT instances. For β=0, our model extends classical random SAT instances. We prove the existence of a SAT–UNSAT phase transition phenomenon for scale-free random 2-SAT instances with β<1/2 when the clause/variable ratio is m/n=1−2β(1−β)2. We also prove that scale-free random k-SAT instances are unsatisfiable with a high probability when the number of clauses exceeds ω(n(1−β)k). The proof of this result suggests that, when β>1−1/k, the unsatisfiability of most formulas may be due to small cores of clauses. Finally, we show how this model will allow us to generate random instances similar to industrial instances, of interest for testing purposes., This research was supported by the project PROOFS, Grant PID2019-109137GB-C21 funded by MCIN/AEI/10.13039/501100011033., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication Artículo científico (JournalArticle)

Incomplete MaxSAT approaches for combinatorial testing

  • Ansótegui Gil, Carlos José
  • Manyà Serres, Felip
  • Ojeda Contreras, Jesús
  • Salvia Hornos, Josep M.
  • Torres, Eduard
We present a Satisfiability (SAT)-based approach for building Mixed Covering Arrays with Constraints of minimum length, referred to as the Covering Array Number problem. This problem is central in Combinatorial Testing for the detection of system failures. In particular, we show how to apply Maximum Satisfiability (MaxSAT) technology by describing efficient encodings for different classes of complete and incomplete MaxSAT solvers to compute optimal and suboptimal solutions, respectively. Similarly, we show how to solve through MaxSAT technology a closely related problem, the Tuple Number problem, which we extend to incorporate constraints. For this problem, we additionally provide a new MaxSAT-based incomplete algorithm. The extensive experimental evaluation we carry out on the available Mixed Covering Arrays with Constraints benchmarks and the comparison with state-of-the-art tools confirm the good performance of our approaches., We would like to thank specially Akihisa Yamada for the access to several benchmarks for our experiments and for solving some questions about his previous work on Combinatorial Testing with Constraints. This work was partially 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, ISINC (PID2019-111544GB-C21), and the MICNN FPU fellowship (FPU18/02929).
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Scale-Free Random SAT Instances

  • Ansótegui Gil, Carlos José
  • Bonet, Maria Luisa
  • Levy, Jordi
We focus on the random generation of SAT instances that have properties similar to real-world instances. It is known that many industrial instances, even with a great number of variables, can be solved by a clever solver in a reasonable amount of time. This is not possible, in general, with classical randomly generated instances. We provide a different generation model of SAT instances, called scale-free random SAT instances. This is based on the use of a non-uniform probability distribution 𝑃(𝑖)∼𝑖−𝛽 to select variable i, where 𝛽 is a parameter of the model. This results in formulas where the number of occurrences k of variables follows a power-law distribution 𝑃(𝑘)∼𝑘−𝛿 , where 𝛿=1+1/𝛽 . This property has been observed in most real-world SAT instances. For 𝛽=0 , our model extends classical random SAT instances. We prove the existence of a SAT–UNSAT phase transition phenomenon for scale-free random 2-SAT instances with 𝛽<1/2 when the clause/variable ratio is 𝑚/𝑛=1−2𝛽(1−𝛽)2 . We also prove that scale-free random k-SAT instances are unsatisfiable with a high probability when the number of clauses exceeds 𝜔(𝑛(1−𝛽)𝑘) . The proof of this result suggests that, when 𝛽>1−1/𝑘 , the unsatisfiability of most formulas may be due to small cores of clauses. Finally, we show how this model will allow us to generate random instances similar to industrial instances, of interest for testing purposes., This research was supported by the project PROOFS, Grant PID2019-109137GB-C21 funded by MCIN/AEI/10.13039/501100011033.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

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

  • Bonacina, Ilario
  • Galesi, Nicola
  • Lauria, Massimo
We introduce a novel take on sum-of-squares that is able to reason with complex numbers and still make use of polynomial inequalities. This proof system might be of independent interest since it allows to represent multivalued domains both with Boolean and Fourier encoding. We show degree and size lower bounds in this system for a natural generalization of knapsack: the vanishing sums of roots of unity. These lower bounds naturally apply to polynomial calculus as-well., The first author was supported by the Ministerio de Ciencia e Innovación MCIN/AEI/10.13039/501100011033, Spain [grant numbers PID2019-109137GB-C21, PID2019-109137GB-C22, and IJC2018-035334-I]., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication Artículo científico (JournalArticle)

Strength and limitations of Sherali-Adams and Nullstellensatz proof systems

  • Bonacina, Ilario
  • Bonet Carbonell, M. Luisa
We compare the strength of the algebraic proof systems Sherali-Adams (SA) and Nullstellensatz (NS) with Frege-style proof systems. Unlike bounded-depth Frege, SA has polynomial-size proofs of the pigeonhole principle (PHP). A natural question is whether adding PHP to bounded-depth Frege is enough to simulate SA. We show that SA, with unary integer coefficients, lies strictly between tree-like depth-1 Frege + PHP and tree-like Resolution. We introduce a levelled version of PHP (L PHP) and we show that SA with integer coefficients lies strictly between tree-like depth-1 Frege + L PHP and Resolution. Analogous results are shown for NS using the bijective (i.e. onto and functional) pigeonhole principle and a leveled version of it., This work was supported by the Ministerio de Ciencia e Innovación/Agencia Estatal de Investigación MCIN/AEI/10.13039/501100011033, Spain [grant numbers PID2019-109137GB-C21, PID2019-109137GB-C22, IJC2018-035334-I]., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication Artículo científico (JournalArticle)

Interpretable decision trees through MaxSAT

  • Alòs Pascual, Josep
  • Ansótegui Gil, Carlos José
  • Torres, Eduard
We present an approach to improve the accuracy-interpretability trade-off of Machine Learning (ML) Decision Trees (DTs). In particular, we apply Maximum Satisfiability technology to compute Minimum Pure DTs (MPDTs). We improve the runtime of previous approaches and, show that these MPDTs can outperform the accuracy of DTs generated with the ML framework sklearn., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. 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: PANDEMIES 2020); Crue-CSIC-SANTANDER (Grant: FONDO SUPERA COVID-19); Agencia de Gestio d’Ajuts Universitaris i de Recerca (AGAUR), Departament d’Empresa i Coneixement de la Generalitat de Catalunya (“Ajuts Joan Oró per a la contractació de personal investigador predoctoral en formació”, grant: 2022 FI_B 00010).
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication 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
Publication 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