This paper proposes a preliminary study on the performance obtained in the enumeration of complete extensions in Abstract Argumentation, by encoding such a problem using the QUBO model and by using both a Simulated Annealer and the D-Wave Quantum Annealer to solve it. QUBO stands for Quadratic Unconstrained Binary Optimization, a mathematical model used in optimization problems where the goal is to minimize or maximize a quadratic function over binary variables. The main goal is to investigate the behavior of (quantum) annealing algorithms during the search, that is, to study which kind of complete extensions are found more frequently/easily.
Dung’s Abstract Argumentation theory [
Unlike other communities, the diversity of semantics is seen as a strength in formal Argumentation
rather than a flaw, leading to substantial research eforts to understand the specific characteristics of
the available semantics [
For example, multiple extensions allow one to capture diferent plausible outcomes when reasoning under uncertainty or incomplete information. This is useful in cases where we may not have enough information to definitively choose one outcome, but we can still enumerate all reasonable possibilities. For instance, in a debate where it is unclear which arguments are most compelling, multiple extensions reflect the fact that more than one coherent set of conclusions might exist given the current information.
The enumeration of extensions has also been one of the targets of the solvers in the 2015, 2017, and 2nd International Workshop on AI for Quantum and Quantum for AI * Corresponding author. $ marco.baioletti@unipg.it (M. Baioletti); fabio.rossi@unipg.it (F. Rossi); francesco.santini@unipg.it (F. Santini) 0000-0002-0877-7063 (M. Baioletti); 0000-0002-8445-0142 (F. Rossi); 0000-0002-3935-4696 (F. Santini) © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 2019 editions of the International Competition on Computational Models of Argumentation (ICCMA).1 In ICCMA 2021, the problem has been replaced by simply counting the number of extensions due to the computational burden of exhaustively printing a very large number of extensions. Finally, ICCMA 2023 eliminated this problem from the list of tracks available to solvers.
In [
Because of these motivations, this paper focuses on the enumeration of extensions as a core problem to
investigate. We describe how to encode this problem as a Quadratic Unconstrained Binary Optimization
(or just QUBO) problem. QUBO is a mathematical model used in optimization problems where the
goal is to minimize or maximize a quadratic function over binary variables. QUBO is widely applied in
ifelds such as Operations Research, Machine Learning, and Quantum Computing due to its versatility to
express complex problems [
The main goal of this paper is to provide a preliminary study on how the enumeration of complete extensions can be encoded and solved as a QUBO problem and what performance can be obtained in terms of how many solutions (i.e. extensions) SA and QA can find on AFs of diferent sizes (i.e., diferent number of arguments and attacks). We use two diferent graph topologies to generate random AFs: the ones based on Erdős-Rényi [8] and Kleinberg [9] models. Preliminary results suggest that SA tends to generate smaller complete extensions more frequently (i.e., with a smaller number of arguments) than larger complete extensions. Considering the tests with QA instead, when the number of arguments increases, the ratio of complete extensions found by the quantum annealer versus those that actually exist rapidly diminishes. This efect occurs considerably faster in AFs created using the Erdős-Rényi model. This phenomenon can also be explained by the significant overhead associated with the embedding, which results in using more than four qubits for each binary variable in the encoding. The immediate impact of this overhead is an increase in the fraction of chain breaks, which can lead to a notable decrease in successful reads.
The works in [10], [11], and [12] opened this line of research by describing the QUBO encodings and related performance tests for a diferent set of Argumentation-related problems, such as the existence of an extension (since the set of stable extensions may be empty, for example), the presence of a given argument in at least one of the extensions (these problems are described in Sect. 2.1 in more detail), or minimizing the number of modifications to an AF needed for a given set of arguments to satisfy a given semantics (called strict enforcement [11, 12]). As previously introduced, this paper examines the behavior of SA and QA in enumerating extensions.
The paper is organized as follows: after this introduction, presenting the problem and providing motivations (Sect. 1), we introduce the necessary background notions about Abstract Argumentation, QUBO, Simulated and Quantum Annealing. Then, Sect. 3 introduces the encoding of extensions 1International Competition on Computational Models of Argumentation: https://argumentationcompetition.org 2The Ising model is a mathematical model used in Statistical Mechanics to describe interactions between binary variables (spins) arranged on a lattice, where each variable can take one of two values: +1 (spin up) and − 1 (spin down). enumeration in QUBO, and Sect. 4 reports the experiments on the generated benchmark. Finally, Sect. 5 summarizes the literature in the field, and Sect. 6 provides conclusions and ideas on how to continue and extend this work.
This section presents the fundamental background concept necessary to understand the remainder of
this work. Section 2.1 describes Argumentation [
An Abstract Argumentation Framework (AF, for short) [
ℱ
A directed graph can straightforwardly represent an AF: an example with five arguments is given in Fig. 1: ℱ = ({, , , , }, { → , → , → , → , → }).
The collective acceptability of arguments depends on the definition of diferent semantics. Semantics determine sets of jointly acceptable arguments, i.e., sets of arguments called extensions, by mapping each ℱ = (A, →) to a set (ℱ ) ⊆ 2A, where 2A is the power-set of A, and parametrically stands for any of the considered semantics.
Four semantics were proposed by Dung in his seminal paper [
ℱ • ∈ stg(ℱ ) if is conflict-free in ℱ and there is no ′ that is conflict-free in ℱ s.t. ℱ′+ ⊃ ℱ+, • ∈ gr(ℱ ) if ∈ co(ℱ ) and there is no ′ ∈ co(ℱ ) s.t. ′ ⊂ , • ∈ id(ℱ ) if and only if is admissible, ⊆ ⋂︀ pr(ℱ ) and there is no admissible ′ ⊆ ⋂︀ pr(ℱ ) s.t. ′ ⊃ ; • ∈ eg(ℱ ) if and only if is admissible, ⊆ ⋂︀ sst(ℱ ) and there is no admissible ′ ⊆ ⋂︀ sst(ℱ ) s.t. ′ ⊃ .
For a more detailed view of these semantics, please refer to [
As an example, if we consider the framework ℱ in Fig. 1 we have for example that • cf (ℱ ) = {∅, {}, {}, {}, {}, {}, {, }, {, }, {, }, {, }, {, }, {, }, {, , }}; • ad(ℱ ) = {∅, {}, {}, {}, {, }, {, }, {, }, {, , }}; • co(ℱ ) = {{}, {, }, {, , }}; • pr(ℱ ) = {{, }, {, , }}; • sst(ℱ ) = st(ℱ ) = stg(ℱ ) = {{, }, {, , }}; • gr(ℱ ) = id(ℱ ) = eg(ℱ ) = {{}}.
We now list six well-known problems in Abstract Argumentation: • Enumeration of extensions EE- : given ℱ = (A, →), return all ∈ (ℱ ) without duplicates. • Credulous acceptance DC- : given ℱ = (A, →) and an argument ∈ A, is contained in some ∈ (ℱ )? • Skeptical acceptance DS- : given ℱ = (A, →) and an argument ∈ A, is contained in all ∈ (ℱ )? • Verification of an extension VER- : given ℱ = (A, →) and a set of arguments ⊆ A, is ∈ (ℱ )? • Existence of an extension EX- : given ℱ = (A, →), is (ℱ ) ̸= ∅? • Existence of non-empty extension NE- : given ℱ = (A, →), does there exist ̸= ∅ such that ∈ (ℱ )? • Uniqueness of the solution UN- : given ℱ = (A, →), is (ℱ ) = {}?
For example, DC-co for the AF in Fig. 1 returns “yes” for argument and “no” for argument ; DS-co returns “yes” for argument only; NE-st returns “yes”. EE-pr outputs {{, }, {, , }}.
In previous papers [10, 11, 12], some of the authors of this work proposed a QUBO approach to solve DC, EX, and NE, on some of the semantics presented in this section. More in particular, the focus was on creating an encoding for ⟨problem-semantics⟩ combinations that resulted in an NP-complete problem, for example, DS-st and NE-pr.
As this work focuses on the enumeration of extensions, we briefly describe the complexity of these
problems by referring to [
From [
QA is a procedure [17] that uses a quantum computing device to solve optimization problems formulated in terms of finding a minimum energy configuration. It is based on the Quantum Adiabatic Theorem and it employs quantum tunneling efects to produce optimal or near/optimal solutions to a discrete optimization problem.
The process starts with an initial function , for which the solution that minimizes energy is easy to ifnd, and slowly transitions to the final function , which corresponds to the function to optimize. If the transition is suficiently slow, Quantum Adiabatic Theorem [18, Ch. 17] guarantees that the solution with the minimum energy adapts to the change in the objective function.
D-Wave produces a series of quantum annealers, which are computing devices that implement the QA algorithm. In particular, the most advanced machines can handle problems with thousands of variables.
Quantum annealers can be “programmed” by describing the problems as Quadratic Unconstrained Binary Optimization (in short, QUBO) or as Ising models [19].
In this paper, we employ the QUBO formalism. It is expressive enough to encode several optimization problems formulated in various application domains [20, 21].
QUBO has been intensively investigated and is used to characterize and solve a wide range of optimization problems: for example, it encompasses SAT Problems, Constraint Satisfaction Problems, Maximum Cut Problems, Graph Coloring Problems, Maximum Clique Problems, General 0/1 Programming Problems, and many more [22]. Moreover, QUBO embeddings exist for Support Vector Machines, Clustering algorithms, and Markov Random Fields [5].
In a QUBO problem, binary variables 1, . . . , and an × upper-triangular matrix are used to formulate the task, which involves minimizing (or maximizing) the function:
() = ∑︁ , + ∑︁ ,
=1 <
The diagonal terms , are the linear coeficients, and the non-zero of-diagonal terms quadratic coeficients. This can be expressed more concisely as , are the min ∈{0,1} where denotes the transpose of the vector . The square matrix of coeficients can be organized in a symmetric way, where for all , except = , , is replaced by (, + ,)/2, or, as stated before, in an upper-diagonal form where for all , such that > , , is replaced by , + , and then all , are replaced by 0 for < .
The formulation of a discrete constrained optimization problem as QUBO requires the following steps: i) find a binary representation for the solutions, and ii) define a penalization function that penalizes unfeasible solutions (i.e., violating a constraint).
Except for the 0/1 limitations on the decision variables, QUBO is an unconstrained model in which the Q matrix contains all the problem data. Due to these features, the QUBO model presents an innovative perspective on classically limited representations and is especially appealing as a modeling framework for combinatorial optimization issues. Rather than applying constraints in the conventional sense, classical constrained models can be successfully reformulated as QUBO models by inserting quadratic penalties into the objective function. Minimization problems are improved by applying penalties to produce an augmented objective function which must be minimized. The augmented objective function becomes equivalent to the original function if the penalty terms are reduced to zero.
When optimizing a problem with constraints, choosing a too-small penalty can result in unfeasible solutions. However, selecting a large penalty value to enforce constraints can cause dificulties for the optimization algorithm in finding feasible solutions. This approach can also lead to other issues, such as sensitivity to penalty values, increased computational eforts during optimization, and instability during the iterations of the solver. For this reason, a sensitive amount of literature has been produced to ifnd good coeficients [ 23, 24], or techniques to model classical constraints into a function, for example, a logical and constraint between 1 and 2 as a multiplication 1 · 2.
The literature discussing precise approaches for QUBO using conventional computers consists of various algorithms [21], all of which share the characteristic that, if given enough time and memory, they end with a globally optimal solution. Most of these techniques use a standard branch-and-bound tree search, although alternative methods are also available. For example, in [25], a QUBO solution is based on the inherent geometric properties of the minimum circumscribed sphere that contains the ellipsoidal contour of the objective function, while in [26], the authors adopt Lagrangean decompositions.
Many research papers have been published in recent years due to the NP-hardness and potential applications of QUBO. These papers describe various heuristic approaches to quickly find high-quality solutions for medium- to large-sized problem cases. Although some of these techniques are simple enough to be called heuristics, the most efective are metaheuristic processes that use compound strategies that are more advanced than those found in basic heuristics. For example, in addition to simulated annealing [27], the work in [28] presents a guided tabu-search algorithm alternating between a basic tabu-search procedure and a variable fix/free phase. In contrast, [ 29] presents a hybrid metaheuristic approach that adopts crossover and update operators and then tabu-search to examine the solutions of the ofspring.
Simulated Annealing (SA) is a probabilistic optimization algorithm inspired by the process of annealing in metallurgy, where a material is heated and then slowly cooled to a low energy state [6]. Three main steps characterize the algorithm: i) initialization, ii) temperature initialization, and iii) iteration.
With initialization, the algorithm starts with an initial solution to the optimization problem; this solution can be generated randomly or by using some heuristic method. In temperature initialization, an initial temperature is set; determines the probability of initially accepting worse solutions. The temperature gradually decreases over time. During the iteration phase, the algorithm repeats until a stopping criterion is met (e.g., a maximum number of iterations or when the temperature drops below a certain threshold).
During iteration, the first step usually consists of perturbing the current solution to generate a neighboring solution; this perturbation can involve minor changes to the current solution. Afterward, the algorithm calculates the corresponding change ∆( Energy ) in the value of the objective function between the current solution and the neighboring solution. If ∆( Energy ) is negative (that is, the neighboring solution is better), the algorithm accepts the neighboring solution. Otherwise, the algorithm accepts the neighboring solution with a probability determined by a temperature-dependent acceptance probability function. This allows the algorithm to escape local minima and explore the solution space more efectively. In the final step of the iteration phase, the algorithm updates the current solution if the neighboring solution is accepted, and it decreases the temperature according to a cooling schedule, which controls the rate at which the temperature decreases. The cooling schedule can be linear, exponential, or follow other schemes. The algorithm stops when the stopping criterion is met, and the best solution found during the iterations is finally returned.
Simulated Annealing allows the algorithm to explore the solution space by initially accepting worse solutions with a certain probability, which gradually decreases as the temperature decreases. This property enables the algorithm to escape local optima and potentially find better solutions. The cooling schedule balances exploration and exploitation, determining how quickly the algorithm converges to an optimal solution.
The approach used in this paper is to employ the encoding described in [10, 12] which allows us to solve some problems in Argumentation as QUBO problems.
In particular, here we use the encoding for the existence of an extension for a given semantics , which is based on a set of binary variables 1, . . . , . These variables are associated with the arguments {1, . . . , } in A and represent a subset of A: ∈ if and only if = 1.
Each semantics will be associated with a quadratic penalty function such that the minimum possible value for is 0 if and only if the corresponding set = { ∈ A : = 1} is an extension valid for .
Most of the Argumentation semantics require admissible sets. Hence, we define a penalty function that enforces this property, which is the sum of 4 terms. The first term forces the set to be conflict-free : cf = ∑︁
→
The value of corresponds to the number of internal attacks in , and its value is 0 if and only if is conflict-free.
The constraints for modeling the notion of defense are more complicated and require some sets of additional variables. The first set contains the variables 1, . . . , , which denote the arguments that are attacked by : = 1 if and only if some argument of attacks .
For each argument , the penalty function forces to be 1 if and only if is attacked by , i.e., = ⋁︀→ .
The function (, , ) = + + + − 2( + ) (2) is used to express the constraint that the binary variable is the disjunction = ( or ) of the binary variables , as a quadratic function, as shown in [30].
Each penalty function requires max{ℎ − 2, 0} auxiliary variables, where ℎ is the number of attackers of . Of course, if ℎ ≤ 2, no additional variable is required. More details can be found in [10].
The variables 1, . . . , of the second set denote which arguments are defended by : = 1 if and only if is defended (from all possible attacks) by some arguments of . Hence, the penalty function forces to be 1 if and only if is defended by , i.e., = ⋀︀→ . The term is encoded using the function [30]
(, , ) = 3 + − 2( + ) which expresses the conjunction = ( and ) of binary variables , as a quadratic function.
In addition, requires max{ℎ − 2, 0} auxiliary variables. The final term
= ∑︁ (1 − ) =1 = + ∑︁ + ∑︁ +
=1 =1 forces each argument in to be defended by . Summing up, the penalty function for admissible sets is
It is easy to prove that the minimum value of is 0, and the related values for x correspond to admissible sets.
It is important to note that the total number of binary variables needed for is = 3 + 2 ∑︁ max(ℎ − 2, 0).
=1
Note that if ℎ = max(ℎ), then = (ℎ). For the complete semantics, we need to add an additional term to which forces all arguments defended by to be elements of : (1) (3) (4) (5) = + ∑︁(1 − ) =1 (6)
In this paper, we restrict our attention to enumerating complete extensions, and for this reason, we need to minimize the penalty function .
To test the QUBO encoding presented in Sect. 3, we performed two diferent rounds of experiments, one with the SA algorithm run on a local computer and the other with the DWave QA machine.
For both experiments, we have used two diferent datasets of Argumentation Frameworks. The first data set is made up of 50 directed graphs with = 9, 16, 25, 36, 49 arguments (ten AFs each), obtained using the Kleinberg model [9]. The model operates on an × grid of nodes, where each node is linked to its neighbors through undirected edges. To produce a “small world” efect, some long-distance edges are added to the network as well, with a preference towards connecting closer nodes rather than further apart.
The second dataset is composed of 50 directed graphs, with = 10, 20, 30, 40, 50 arguments, generated by Erdős-Rényi model [8] (, ) with = 0.25, which is the probability that each edge is included in the graph, independently of every other edge.
In this case, the chosen number of nodes is similar to that used with the Kleinberg model for a meaningful performance comparison between the two datasets. The first model produces AFs with a large number of complete extensions (see Tab. 1), while the second model produces AFs with a very small number of complete extensions (see Tab. 2).
In both tables, we report for each value of , the average number of attacks (avg_atts), the average number of variables used in QUBO formulation of the problem (avg_var_QUBO), the minimum (min_exts), the average (avg_exts), and the maximum number of complete extensions (max_exts), computed on all the AFs with the same . Moreover, we also computed the maximum (max_card) and average cardinality of the complete extensions (avg_card), averaging on the same groups of AFs. 3
These two datasets, having diferent features, provide two diferent scenarios to test the capability of the QUBO approach of enumerating the complete extensions. In particular, we can use the first dataset to see how many extensions are retrieved with the SA and the QA approaches. We want to compute the recall coeficient, i.e., the ratio between the number of complete extensions found by the analyzed methods and the number of existing complete extensions.
Since both methods are probabilistic (although in diferent ways), it is likely that in several reads of the SA or QA diferent complete extensions are found. The hope is that SA and QA can i) always find (almost) a complete extension in each run, and ii) the recall is close to 1, i.e., the number of diferent retrieved complete extensions is equal (or close) to the number of all complete extensions.
However, SA and QA are not exact algorithms, hence there is a chance that they find non-optimal solutions, which have non-zero values for , and which do not correspond to complete extensions. The result of each run that terminates with a non-optimal solution will be considered a failure, and the solution found will be ignored because it does not correspond to a complete extension.
The second dataset contains AFs with a limited number of complete extensions. In this case, we want to see if the proposed approach can find at least one complete extension in most of the runs.
SA tests were performed on an Ubuntu 22.04 machine with an AMD Ryzen 3 PRO 4350G processor equipped with 32GB of RAM. Since SA is not a deterministic algorithm, 20 runs of the algorithm were executed for each graph to average the results. For each run, the SA algorithm performed 1000 reads. 3The list of the complete extensions for each AF has been computed with ConArg.
avg_atts avg_var_QUBO min_exts avg_exts max_exts max_card avg_card
In Tab. 3, we show the experimental results of applying the SA algorithm to the AFs in the first dataset. This table contains, for each value of , the average fraction of successful reads (avg_succ): this value corresponds to the number of reads that terminated with 0 energy divided by the total number of reads. Moreover, we show the minimum (min_recall), the average (avg_recall) and the maximum value of the recall coeficient ( max_recall). Finally, we also report the average cardinality (in the number of arguments) of all the complete extensions existing in the AF (column ext_card_avg) and the average cardinality of all the complete extensions found by SA (column sa_ext_card_avg). These two numbers result from an average on all reads, runs, and AFs with the same value of .
As soon as increases, the size of the AF (and hence the size of the corresponding QUBO model) also increases. Therefore, we expect that the SA will find more and more dificulties in solving the problem. This is confirmed by the decrease of avg_succ, which goes from a value close to 1 to a value close to 0, and the recall factor. In particular, note that the recall is very large (on average) for ≤ 25 and is still over 50% with = 36 arguments.
A similar and even more drastic behavior can be seen in Tab. 4. Here we see that the number of successful reads quickly decreases and reaches values near 0, and the same happens with the recall factor. This is because as the number of arguments increases, complete extensions become increasingly rare, and it is quite likely that SA cannot find one.
We hypothesize that SA tends to produce smaller complete extensions more frequently (i.e., with a smaller number of arguments) than larger complete extensions. The last columns of the table (except for the case of = 9) match this hypothesis. Moreover, we also check that for all AFs, in almost all the runs for = 16 and all the runs for ≥ 25, the average cardinality of all the complete extensions found by SA is lower than the average cardinality of all the complete extensions.
This hypothesis can also be confirmed by the frequency distribution of the cardinalities of the complete extensions found in a typical run of the SA on an AF of size 25, as shown in Tab. 5. The second column contains the frequency of the cardinality of complete extensions found by SA, while the third column reports the frequency of the cardinality of the existing complete extensions. Complete extensions with cardinality less than or equal to 2 are found with a frequency larger than the expected value, while when the cardinality is greater than 2, the frequency is lower, except for the case of maximum cardinality 7.
QA experiments have been performed on quantum computers at D-Wave Company (https://www.dwavesys.com/). For each AFs we executed 20 runs and 2000 reads per run.
Due to the contingent time to use the DWave machine, we decided to restrict the QA experiments to only 20 AFs for = 9, 16, 25 (Kleinberg AFs) and for = 10, 20, 30 (Erdős-Rényi AFs).
The results, shown in Tab. 6 and Tab. 7, are organized diferently concerning the corresponding tables for SA, namely Tab. 3 and Tab. 4, because the solver provides additional diferent data.
In detail, we have reported of arguments for each number, averaged on all runs and all AFs of size : the minimum energy, the recall factor, and the average frequency of successful reads. We have also reported the average overhead the embedding gives to the machine qubits structure and the chain break fraction. As expected, as increases, the recall factor decreases rapidly, and this happens much faster on the AFs generated with the Erdös-Rényi model.
This behavior is also justified by the large overhead imposed by the embedding, which arrives, for = 30 in Tab. 7 to more than 4 qubits used for each binary variable present in the encoding. The direct efect of the overhead is a larger fraction of chain breaks, which can cause a sensitive reduction in successful reads. Note also that in both tables, the average minimum energy of the solutions found by QA becomes quite large for > 20. This is a clear symptom that the problem becomes very dificult for the solver, which is not able to find optimal solutions in a suficient number of reads (for the Kleinberg model) or even zero (for the Erdös-Rényi model).
The enumeration of solutions is clearly an important topic in search algorithms and Computer Science in general. For example, the enumeration of solutions ensures that every possible solution is considered, making the search complete: this guarantees that if a solution exists, it will be found. In addition, enumeration is essential to ensure that the optimal solution is found: exhaustive search algorithms like brute force or backtracking rely on enumeration to explore the entire solution space. In the classical view of Abstract Argumentation, there is no reason to prefer an extension over another. For this reason, the enumeration of all extensions proves to be indispensable due to the inherent uncertainty in a debate. Diferent agents may reach diferent conclusions based on the same set of arguments: multiple extensions reflect this pluralism, where diferent sets of arguments can be accepted as valid under the same criteria. Furthermore, many real-world problems, especially in areas such as law, ethics, and policy-making, do not have a single clear solution. Multiple extensions allow for the representation of several possible solutions, each of which is valid according to a given semantics. Being Abstract Argumentation based on the notion of attack, conflicts cannot be always fully resolved: diferent extensions represent diferent ways of resolving conflicts between arguments.
The enumeration problem has been extensively studied in the literature since the birth of the discipline: several algorithms have been formulated to tackle this problem.
One of the first proposals for preferred semantics can be found in [ 31]. The authors develop diferent algorithms for diferent related problems. Set-enumeration procedures are used together with some peculiar properties of preferred extensions to reduce the number of generated sets accordingly.
In [32], the authors explore the challenge of counting extensions defined by multi-status semantics in Abstract Argumentation without explicitly listing them. They refer to Dung’s traditional stable and preferred semantics and other semantics, and demonstrate that, in general, counting extensions is computationally hard (specifically, #P-complete). Furthermore, they identify non-trivial topological classes of AFs where extension counting is tractable.
In [33], the authors develop an ad hoc algorithm to enumerate preferred extensions by using argument labelings (e.g., argument acceptance in a set can be in, out, or undecidable), which is slightly diferent but still strictly correlated with extension-based argumentation.
In [34], the authors propose an algorithm for eficiently computing a given AF’s preferred extensions. The underlying technique relies on first computing the ideal extension for a given AF and then using it to prune some arguments to obtain a smaller AF. Finally, the enumeration is conducted on the pruned AF. Instead, a variant of this algorithm tailored to semi-stable semantics is presented in [35].
To our knowledge, the first performance comparisons of diferent solvers in the enumeration problem are represented by the works in [36, 36] and in [37]. In [36, 36] the authors compare the performance of ArgTools, ASPARTIX, ConArg, and Dung-O-Matic. These tools are tested on three diferent models of randomly generated graph models, corresponding to the Erdős-Rényi, Kleinberg, and the scale-free Barabasi-Albert models. The work in [37] compares two SAT solvers with ASPARTIX and one of its variants; no particular topology is used, but attacks are generated by using a uniform distribution and computing a probability score for each pair of arguments.
The work in [37] was also the spark for [38], where the performance of diferent solvers was studied for the first time to develop a portfolio of solvers considering the characteristics of the input AFs.
We have presented a first QUBO encoding to enumerate all the complete extensions for a given semantics
in Abstract Argumentation [
Our experiments suggest that SA is inclined to generate smaller complete extensions more often, meaning ones with fewer arguments, compared to larger ones. For all AFs tested, in almost all trials for = 16 and every trial for ≥ 25, the average size of the complete extensions determined by SA is less than the overall average size of all complete extensions.
Concerning the future, we plan to extend this work along diferent lines of research. First, we want to extend and test the encoding to diferent semantics, e.g., the preferred semantics. Moreover, we plan to use diferent encoding schemes, for instance, by imposing a cardinality constraint on the extensions after an iteration of the annealing algorithm. By adding such constraints, the goal is to better guide the search to find only missing extensions with greater cardinality. This could produce better enumerations in terms of higher recall and a smaller number of reads.
We would like to thank Fabrizio Fagiolo, Valentina Poggioni, Luca Tutino, Nicolò Vescera, for allowing us to use some of their machine time on DWave.
M. Baioletti was partially funded by the University of Perugia - “Fondo Ricerca di Ateneo WP4.4” 2022 - Project Quanta - Laboratorio di Calcolo Quantistico.
Francesco Santini is supported by Project 2022TXPK39 - ”Empowering Public Interest Communication with Argumentation (EPICA)”, CUP J53D23007220006, funded by Next Generation EU, MUR; Project “Fondo Ricerca di Ateneo WP4.1 - RATIONALISTS”, funded by University of Perugia. Francesco Santini is a member of the “Gruppo Nazionale Calcolo Scientifico - Istituto Nazionale di Alta Matematica (GNCS-INdAM)”. [5] S. Mücke, N. Piatkowski, K. Morik, Learning bit by bit: Extracting the essence of machine learning, in: R. Jäschke, M. Weidlich (Eds.), Proceedings of the Conference on "Lernen, Wissen, Daten, Analysen", volume 2454 of CEUR Workshop Proceedings, CEUR-WS.org, Berlin, Germany, 2019, pp. 144–155. [6] P. J. M. van Laarhoven, E. H. L. Aarts, Simulated Annealing: Theory and Applications, volume 37 of Mathematics and Its Applications, Springer, Heidelberg, Germany, 1987. [7] K. Boothby, P. Bunyk, J. Raymond, A. Roy, Next-generation topology of d-wave quantum processors, 2020. URL: https://arxiv.org/abs/2003.00133. arXiv:2003.00133. [8] P. Erdős, A. Rényi, On the evolution of random graphs, Bull. Inst. Internat. Statist 38 (1961) 343–347. [9] J. Kleinberg, The small-world phenomenon: An algorithmic perspective, in: Proceedings of the thirty-second annual ACM symposium on Theory of computing, 2000, pp. 163–170. [10] M. Baioletti, F. Santini, Abstract argumentation goes quantum: An encoding to QUBO problems, in: PRICAI (1), volume 13629 of Lecture Notes in Computer Science, Springer, 2022, pp. 46–60. [11] M. Baioletti, F. Santini, On using QUBO to enforce extensions in abstract argumentation (short paper), in: AIQxQIA@AI*IA, volume 3586 of CEUR Workshop Proceedings, CEUR-WS.org, Rome, Italy„ 2023. [12] M. Baioletti, F. Santini, An encoding of argumentation problems using quadratic unconstrained binary optimization, Quantum Mach. Intell. 6 (2024) 51. [13] M. Caminada, W. A. Carnielli, P. E. Dunne, Semi-stable semantics, J. Log. Comput. 22 (2012) 1207–1254. [14] B. Verheij, Two approaches to dialectical argumentation: admissible sets and argumentation stages, in: Proceedings of the 8th Dutch Conference on Artificial Intelligence (NAIC’96), 1996, pp. 357–368. [15] P. M. Dung, P. Mancarella, F. Toni, Computing ideal sceptical argumentation, Artificial Intelligence 171 (2007) 642–674. [16] M. Caminada, Comparing two unique extension semantics for formal argumentation: ideal and eager, in: Belgian-Dutch conference on artificial intelligence (BNAIC), 2007, pp. 81–87. [17] S. E. Venegas-Andraca, W. Cruz-Santos, C. McGeoch, M. Lanzagorta, A cross-disciplinary introduction to quantum annealing-based algorithms, Contemporary Physics 59 (2018) 174–197. [18] A. Messiah, Quantum mechanics: volume II, North-Holland Publishing Company Amsterdam, 1962. [19] A. Lucas, Ising formulations of many np problems, Frontiers in Physics 2 (2014). [20] F. W. Glover, G. A. Kochenberger, Y. Du, Quantum bridge analytics I: a tutorial on formulating and using QUBO models, 4OR 17 (2019) 335–371. [21] G. A. Kochenberger, J. Hao, F. W. Glover, M. W. Lewis, Z. Lü, H. Wang, Y. Wang, The unconstrained binary quadratic programming problem: a survey, J. Comb. Optim. 28 (2014) 58–81. [22] F. W. Glover, G. A. Kochenberger, Y. Du, Quantum bridge analytics I: a tutorial on formulating and using QUBO models, 4OR 17 (2019) 335–371. [23] A. Verma, M. W. Lewis, Penalty and partitioning techniques to improve performance of QUBO solvers, Discret. Optim. 44 (2022) 100594. [24] T. Vyskocil, H. N. Djidjev, Simple constraint embedding for quantum annealers, in: ICRC, IEEE,
McLean, VA, USA, 2018, pp. 1–11. [25] D. Li, X. Sun, C. Liu, An exact solution method for unconstrained quadratic 0-1 programming: a geometric approach, J. Glob. Optim. 52 (2012) 797–829. [26] G. R. Mauri, L. A. N. Lorena, Improving a lagrangian decomposition for the unconstrained binary quadratic programming problem, Comput. Oper. Res. 39 (2012) 1577–1581. [27] T. M. Alkhamis, M. Hasan, M. A. Ahmed, Simulated annealing for the unconstrained quadratic pseudo-boolean function, Eur. J. Oper. Res. 108 (1998) 641–652. [28] J. Wang, Y. Zhou, J. Yin, Combining tabu hopfield network and estimation of distribution for unconstrained binary quadratic programming problem, Expert Syst. Appl. 38 (2011) 14870–14881. [29] Z. Lü, F. W. Glover, J. Hao, A hybrid metaheuristic approach to solving the UBQP problem, Eur. J.
Oper. Res. 207 (2010) 1254–1262. [30] I. Rosenberg, Reduction of bivalent maximization to the quadratic case, Cahiers du Centre d’Etudes de Recherche Opérationnelle 17 (1975) 71–74. [31] S. Doutre, J. Mengin, Preferred extensions of argumentation frameworks: Query answering and computation, in: IJCAR, volume 2083 of Lecture Notes in Computer Science, Springer, 2001, pp. 272–288. [32] P. Baroni, P. E. Dunne, M. Giacomin, On extension counting problems in argumentation frameworks, in: Computational Models of Argument: Proceedings of COMMA 2010, Desenzano del Garda, Italy, September 8-10, 2010, volume 216 of Frontiers in Artificial Intelligence and Applications , IOS Press, 2010, pp. 63–74. [33] S. Nofal, P. E. Dunne, K. Atkinson, On preferred extension enumeration in abstract argumentation, in: COMMA, volume 245 of Frontiers in Artificial Intelligence and Applications , IOS Press, 2012, pp. 205–216. [34] G. Alfano, S. Greco, F. Parisi, On scaling the enumeration of the preferred extensions of abstract argumentation frameworks, in: SAC, ACM, 2019, pp. 1147–1153. [35] G. Alfano, An eficient algorithm for computing the set of semi-stable extensions, in: FQAS, volume 11529 of Lecture Notes in Computer Science, Springer, 2019, pp. 139–151. [36] S. Bistarelli, F. Rossi, F. Santini, A comparative test on the enumeration of extensions in abstract argumentation, Fundam. Informaticae 140 (2015) 263–278. [37] F. Cerutti, P. E. Dunne, M. Giacomin, M. Vallati, Computing preferred extensions in abstract argumentation: A sat-based approach, in: TAFA, volume 8306 of Lecture Notes in Computer Science, Springer, 2013, pp. 176–193. [38] F. Cerutti, M. Giacomin, M. Vallati, Algorithm selection for preferred extensions enumeration, in: COMMA, volume 266 of Frontiers in Artificial Intelligence and Applications , IOS Press, 2014, pp. 221–232.