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): 13
Encontrada(s) 1 página(s)

Repositori Obert UdL
Publicación 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
Publicación 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
Publicación 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.
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación 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
Publicación 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
Publicación 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
Publicación 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
Publicación 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
Publicación 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
Publicación 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
Publicación 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
Publicación 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
Publicación 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).