Carlos Ansótegui
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Carlos Ansótegui has a total of 41 co-authors. Here are the top co-authors by number of shared publications:
- Jordi Levy
IIIA, CSIC, Barcelona, Spain
25 shared publications - Maria Luisa Bonet
Universitat Politècnica de Catalunya (UPC)
17 shared publications - Felip Manyà
IIIA-CSIC, Bellaterra, Spain
14 shared publications - Ramón Béjar
GREiA Research Group, Universitat de Lleida, Pere de Cabrera 3, 25001 Lleida, Spain
7 shared publications - Cèsar Fernández
Universitat de Lleida
6 shared publications - Jesús Giráldez-Cru
DaSCI, DECSAI, Universidad de Granada, Granada, Spain
6 shared publications
Latest Publications
- 20 February 2026
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 85
Revisiting SAT-based Solvers: MaxSAT Rules and Core Sequences
In this paper, we revisit the state-of-the-art of MaxSAT solving. We focus on SAT-based MaxSAT solving algorithms, mainly on Core-guided MaxSAT solvers. We show how to describe Core-guided solvers with Non-CNF MaxSAT rules plus the Extension rule. Equipped with these rules, we show how to apply them alternatively to obtain new Core-guided MaxSAT solvers. Since Core-guided solvers essentially solve a sequence of SAT instances, we also discuss how Core-guided MaxSAT solvers traverse the search space of possible sequences of SAT instances, the existence of exponentially harder sequences, and how to avoid them. The experimental investigation shows comparable and complementary performance to state-of-the-art solvers.
- 20 February 2026
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 85
Revisiting SAT-based Solvers: MaxSAT Rules and Core Sequences
In this paper, we revisit the state-of-the-art of MaxSAT solving. We focus on SAT-based MaxSAT solving algorithms, mainly on Core-guided MaxSAT solvers. We show how to describe Core-guided solvers with Non-CNF MaxSAT rules plus the Extension rule. Equipped with these rules, we show how to apply them alternatively to obtain new Core-guided MaxSAT solvers. Since Core-guided solvers essentially solve a sequence of SAT instances, we also discuss how Core-guided MaxSAT solvers traverse the search space of possible sequences of SAT instances, the existence of exponentially harder sequences, and how to avoid them. The experimental investigation shows comparable and complementary performance to state-of-the-art solvers.
- Open Access
- 15 October 2025
- Published by Springer Nature in Quantum Information Processing
- Vol. 24 (10) , 1-20
SAT, gadgets, Max2XOR, and quantum annealers
Quantum annealers are presented as quantum computers that can, with a high probability, optimize certain quadratic functions on Boolean variables in constant time. These functions are basically the Hamiltonian of Ising models that reach the ground energy state with a high probability after an annealing process. In some preliminary works, they have been proposed as a way to solve SAT. These Hamiltonians can be seen as Max2XOR problems, i.e., as the problem of finding an assignment that maximizes the number of XOR clauses of at most two variables that are satisfied. In this paper, we focus on introducing several gadgets to reduce SAT to Max2XOR. We show how they can be used to translate SAT instances to initial configurations of a quantum annealer.
- 15 October 2025
- Published by Springer Nature in Quantum Information Processing
- Vol. 24 (10) , 1-20
Open AccessSAT, gadgets, Max2XOR, and quantum annealers
Quantum annealers are presented as quantum computers that can, with a high probability, optimize certain quadratic functions on Boolean variables in constant time. These functions are basically the Hamiltonian of Ising models that reach the ground energy state with a high probability after an annealing process. In some preliminary works, they have been proposed as a way to solve SAT. These Hamiltonians can be seen as Max2XOR problems, i.e., as the problem of finding an assignment that maximizes the number of XOR clauses of at most two variables that are satisfied. In this paper, we focus on introducing several gadgets to reduce SAT to Max2XOR. We show how they can be used to translate SAT instances to initial configurations of a quantum annealer.
- 30 June 2024
- Published by Springer Nature
- p. 277-291
Implementing 3-SAT Gadgets for Quantum Annealers with Random Instances
- 30 June 2024
- Published by Springer Nature
- p. 277-291
Implementing 3-SAT Gadgets for Quantum Annealers with Random Instances
- Open Access
- 19 October 2023
- Published by IOS Press
- p. 369-382
On the Density of States of Boolean Formulas1
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.
- 19 October 2023
- Published by IOS Press
- p. 369-382
Open AccessOn the Density of States of Boolean Formulas1
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.
- Open Access
- 20 June 2022
- Published by MDPI AG in Algorithms
- Vol. 15 (6) , 219
Scale-Free Random SAT Instances
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 . This property has been observed in most real-world SAT instances. For , 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 when the clause/variable ratio is . We also prove that scale-free random k-SAT instances are unsatisfiable with a high probability when the number of clauses exceeds . The proof of this result suggests that, when , 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.- 20 June 2022
- Published by MDPI AG in Algorithms
- Vol. 15 (6) , 219
Open AccessScale-Free Random SAT Instances
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 . This property has been observed in most real-world SAT instances. For , 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 when the clause/variable ratio is . We also prove that scale-free random k-SAT instances are unsatisfiable with a high probability when the number of clauses exceeds . The proof of this result suggests that, when , 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. - 4 May 2021
- Published by Springer Nature in Annals of Mathematics and Artificial Intelligence
- Vol. 90 (7-9) , 715-734
Boosting evolutionary algorithm configuration
- 4 May 2021
- Published by Springer Nature in Annals of Mathematics and Artificial Intelligence
- Vol. 90 (7-9) , 715-734
Boosting evolutionary algorithm configuration
- Open Access
- 27 October 2020
- Published by MDPI AG in Preprints.org
The Self-Similarity of Industrial SAT Instances
In the last years, we have witnessed a remarkable progress of algorithms solving Boolean satisfiability (SAT). The success of these algorithms has been especially relevant in a large number of industrial or real-world applications, for which these SAT solvers are nowadays an essential core part of their solving processes. Interestingly enough, these applications include a very diverse and heterogeneous range of domains, such as hardware verification, planning, and cryptography, among others. Unfortunately, the reasons of the good performance of these solvers on this variety of industrial benchmarks are not completely understood yet. Since SAT solvers’ efficiency is fundamental in various domains, obtaining a better understanding of these algorithms and the reasons of their good performance is crucial. In order to shed light on this question, SAT solvers are often viewed as complex systems with many interconnected components (e.g., conflict analysis and learning mechanism, database management, search restarts) interacting in many unpredictable ways. There is the common belief that the resulting emergent behavior of these complex systems takes advantage of a certain underlying structure of the SAT formula, which is shared by the majority of these industrial problems regardless the domain they come from. Recently, there have been some attempts of characterizing this structure under the lens of complex networks, with the purpose of better understanding the success of the solvers, and potentially improving them. In this paper, we analyze the structure of industrial SAT instances under the lens of self-similarity, and study how the execution of SAT solvers affect that structure. Many real-world graphs exhibit self-similar structure (with small fractal dimension), which means that after rescaling (replacing groups of nodes by a single node), the same kind of structure can be observed. In our analysis, in which we represent SAT instances as graphs, we observe that many industrial SAT formulas exhibit the same kind of structure. Moreover, we analyze how this structure evolves by effects of learning new clauses during the search. In particular, we observe that learned clauses usually contain variables that are close in the graph representation of the formula. This is, the learning mechanism tends to work locally. On the contrary, this learning mechanism on random SAT formulas –which do not exhibit any structure at all– is unable to generate these local clauses. This difference contributes to explain the success of modern SAT solvers on industrial problems.
- 27 October 2020
- Published by MDPI AG in Preprints.org
Open AccessThe Self-Similarity of Industrial SAT Instances
In the last years, we have witnessed a remarkable progress of algorithms solving Boolean satisfiability (SAT). The success of these algorithms has been especially relevant in a large number of industrial or real-world applications, for which these SAT solvers are nowadays an essential core part of their solving processes. Interestingly enough, these applications include a very diverse and heterogeneous range of domains, such as hardware verification, planning, and cryptography, among others. Unfortunately, the reasons of the good performance of these solvers on this variety of industrial benchmarks are not completely understood yet. Since SAT solvers’ efficiency is fundamental in various domains, obtaining a better understanding of these algorithms and the reasons of their good performance is crucial. In order to shed light on this question, SAT solvers are often viewed as complex systems with many interconnected components (e.g., conflict analysis and learning mechanism, database management, search restarts) interacting in many unpredictable ways. There is the common belief that the resulting emergent behavior of these complex systems takes advantage of a certain underlying structure of the SAT formula, which is shared by the majority of these industrial problems regardless the domain they come from. Recently, there have been some attempts of characterizing this structure under the lens of complex networks, with the purpose of better understanding the success of the solvers, and potentially improving them. In this paper, we analyze the structure of industrial SAT instances under the lens of self-similarity, and study how the execution of SAT solvers affect that structure. Many real-world graphs exhibit self-similar structure (with small fractal dimension), which means that after rescaling (replacing groups of nodes by a single node), the same kind of structure can be observed. In our analysis, in which we represent SAT instances as graphs, we observe that many industrial SAT formulas exhibit the same kind of structure. Moreover, we analyze how this structure evolves by effects of learning new clauses during the search. In particular, we observe that learned clauses usually contain variables that are close in the graph representation of the formula. This is, the learning mechanism tends to work locally. On the contrary, this learning mechanism on random SAT formulas –which do not exhibit any structure at all– is unable to generate these local clauses. This difference contributes to explain the success of modern SAT solvers on industrial problems.
- Open Access
- 10 October 2019
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 66, 443-472
Community Structure in Industrial SAT Instances
Modern SAT solvers have experienced a remarkable progress on solving industrial instances. It is believed that most of these successful techniques exploit the underlying structure of industrial instances. Recently, there have been some attempts to analyze the structure of industrial SAT instances in terms of complex networks, with the aim of explaining the success of SAT solving techniques, and possibly improving them. In this paper, we study the community structure, or modularity, of industrial SAT instances. In a graph with clear community structure, or high modularity, we can find a partition of its nodes into communities such that most edges connect variables of the same community. Representing SAT instances as graphs, we show that most application benchmarks are characterized by a high modularity. On the contrary, random SAT instances are closer to the classical Erdös-Rényi random graph model, where no structure can be observed. We also analyze how this structure evolves by the effects of the execution of a CDCL SAT solver, and observe that new clauses learned by the solver during the search contribute to destroy the original structure of the formula. Motivated by this observation, we finally present an application that exploits the community structure to detect relevant learned clauses, and we show that detecting these clauses results in an improvement on the performance of the SAT solver. Empirically, we observe that this improves the performance of several SAT solvers on industrial SAT formulas, especially on satisfiable instances.
- 10 October 2019
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 66, 443-472
Open AccessCommunity Structure in Industrial SAT Instances
Modern SAT solvers have experienced a remarkable progress on solving industrial instances. It is believed that most of these successful techniques exploit the underlying structure of industrial instances. Recently, there have been some attempts to analyze the structure of industrial SAT instances in terms of complex networks, with the aim of explaining the success of SAT solving techniques, and possibly improving them. In this paper, we study the community structure, or modularity, of industrial SAT instances. In a graph with clear community structure, or high modularity, we can find a partition of its nodes into communities such that most edges connect variables of the same community. Representing SAT instances as graphs, we show that most application benchmarks are characterized by a high modularity. On the contrary, random SAT instances are closer to the classical Erdös-Rényi random graph model, where no structure can be observed. We also analyze how this structure evolves by the effects of the execution of a CDCL SAT solver, and observe that new clauses learned by the solver during the search contribute to destroy the original structure of the formula. Motivated by this observation, we finally present an application that exploits the community structure to detect relevant learned clauses, and we show that detecting these clauses results in an improvement on the performance of the SAT solver. Empirically, we observe that this improves the performance of several SAT solvers on industrial SAT formulas, especially on satisfiable instances.
- Open Access
Scale-Free Random SAT Instances
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 \emph{scale-free random SAT instances}. It is based on the use of a non-uniform probability distribution $P(i)\sim i^{-\beta}$ to select variable $i$, where $\beta$ is a parameter of the model. This results into formulas where the number of occurrences $k$ of variables follows a power-law distribution $P(k)\sim k^{-\delta}$ where $\delta = 1 + 1/\beta$. This property has been observed in most real-world SAT instances. For $\beta=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 $\beta1-1/k$, and formulas are unsatisfiable due to a small core of clauses. The proof of this result suggests that, when $\beta>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.Open AccessScale-Free Random SAT Instances
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 \emph{scale-free random SAT instances}. It is based on the use of a non-uniform probability distribution $P(i)\sim i^{-\beta}$ to select variable $i$, where $\beta$ is a parameter of the model. This results into formulas where the number of occurrences $k$ of variables follows a power-law distribution $P(k)\sim k^{-\delta}$ where $\delta = 1 + 1/\beta$. This property has been observed in most real-world SAT instances. For $\beta=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 $\beta1-1/k$, and formulas are unsatisfiable due to a small core of clauses. The proof of this result suggests that, when $\beta>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. - 23 January 2018
- Published by EasyChair
On Solving MaxSAT Through SAT
In this paper we present a Partial MaxSAT solver based on successive calls to a SAT solver. At the kth iteration the SAT solver tries to certify that there exist an assignment that satisfies all but k clauses. The key idea is to add an additional variable to each soft clause and to introduce, at each iteration, at-least and at-most cardinality constraints restricting the possible values of these variables. We prove the correctness of our algorithm and compare it with other (Partial) MaxSAT solvers.
- 23 January 2018
- Published by EasyChair
On Solving MaxSAT Through SAT
In this paper we present a Partial MaxSAT solver based on successive calls to a SAT solver. At the kth iteration the SAT solver tries to certify that there exist an assignment that satisfies all but k clauses. The key idea is to add an additional variable to each soft clause and to introduce, at each iteration, at-least and at-most cardinality constraints restricting the possible values of these variables. We prove the correctness of our algorithm and compare it with other (Partial) MaxSAT solvers.