CACarlos Ansótegui

Carlos Ansótegui

*This is an algorithmically generated author record based on publicly available information.

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


Carlos Ansótegui has a total of 41 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Revisiting SAT-based Solvers: MaxSAT Rules and Core Sequences

    by Josep Alòs, Carlos Ansótegui, Eduard Torres

    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

    SAT, gadgets, Max2XOR, and quantum annealers

    by Carlos Ansótegui, Jordi Levy

    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.


  • Implementing 3-SAT Gadgets for Quantum Annealers with Random Instances

    by Pol Rodríguez-Farrés, Rocco Ballester, Carlos Ansótegui, Jordi Levy, Jesus Cerquides


  • Open Access

    On the Density of States of Boolean Formulas1

    by Carlos Ansótegui, María Luisa Bonet, Jordi Levy

    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

    Scale-Free Random SAT Instances

    by Carlos Ansótegui, Maria Luisa Bonet, Jordi Levy

    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.


  • Open Access

    The Self-Similarity of Industrial SAT Instances

    by Carlos Ansótegui, Maria Luisa Bonet, Jesús Giráldez-Cru, Jordi Levy

    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

    Community Structure in Industrial SAT Instances

    by Carlos Ansótegui, Maria Luisa Bonet, Jesús Giráldez-Cru, Jordi Levy, Laurent Simon

    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

    by Carlos Ansótegui, Maria Luisa Bonet, Jordi Levy

    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.

  • On Solving MaxSAT Through SAT

    by Carlos Ansótegui, María Luisa Bonet, Jordi Levy

    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.