Dung's abstract argumentation frameworks has been object of intense study not just for its relationship with logical reasoning but also for its uses within arti cial intelligence. One research branch in abstract argumentation has focused on nding new methods for computing its di erent semantics. We present a novel method, to the best of our knowledge, for computing semi-stable semantics using 0-1 integer programming, and also experimentally compare it with an answer set programming approach. Our results indicate that this new method performed well, and it has a great opportunity space for improving.
The main purpose of argumentation theory is to study the fundamental mechanism humans use in argumentation and to explore ways to implement this mechanism on computers. Currently formal argumentation research has been strongly in uenced by abstract argumentation theory of Dung [6]. This approach is mainly orientated to manage the interaction of arguments by introducing a single structure called Argumentation Framework (AF). An AF basically is a pair of sets: a set of arguments and a set of disagreements between arguments called attacks. Indeed an AF can be regarded as a directed graph in which the arguments are represented by nodes and the attack relations are represented by arcs.
In [6], four argumentation semantics were introduced: grounded, preferred, stable, and complete semantics. The central notion of Dung's semantics is the acceptability of the arguments. Even though each of these argumentation semantics represents di erent patterns of selection of arguments, all of them are based on the basic concept of admissible set. Informally speaking, an admissible set presents a coherent and defendable point of view in a con ict between arguments.
One research branch in abstract argumentation has been to nd new methods for computing its di erent semantics, i.e. the search for acceptable (w.r.t. certain criteria) sets of arguments. Charwat et al. [10] surveys the approaches that has been used so far for computing AF semantics, and divided them into reduction and direct approaches. The direct approach consists in developing new algorithms for computing AF semantics, but our interest is in the reduction approach.
The reduction approach consists in using the software that was originally developed for other formalisms [10]. Thus, a given AF has to be formalized in the targeted formalism, like: constraint-satisfaction [5], propositional logic [1], or answer-set programming [3], [13].
To the best of our knowledge, there is just a previous work [11] where authors indirectly used 0-1 integer programming for computing preferred semantics, since their approach was based on a mapping from an argumentation framework AF into a logic program with negation as failure AF to Clark's completion Comp( AF ) [12] to 0-1 integer program lc( AF ) [2], which then was solved by a mathematical programming solver.
In this work, we present a novel method, to the best of our knowledge, for directly computing semi-stable (SS) semantics using 0-1 integer programming with no mapping. Our results indicate that this new method performed well.
The paper is organized as follows. Section 2 gives some background on argumentation. Section 3 presents a procedure based on solving a series of 0-1 integer programming problems for computing SS semantics. Finally, Section 4 presents a brief description of results, some conclusions and future work. 2
For space reasons, we assume that readers are familiar with the basic notions of 0-1 integer programming and ASP. We will use some concepts of Dung's argumentation approach. An AF captures the relationships between arguments. De nition 1. [6] An AF is a pair AF := hAR; attacksi, where AR is a nite set of arguments, and attacks is a binary relation on AR, i.e. attacks AR AR.
We say that a attacks b (or b is attacked by a) if attacks(a; b) holds. Similarly, we say that a set S of arguments attacks b (or b is attacked by S) if b is attacked by an argument in S.
Dung de ned his argumentation semantics based on the basic concept of admissible set, which can be understood in terms of defense of arguments and in terms of con ict-free sets, as follows: De nition 2. [4] Let AF := hAR; attacksi be an argumentation framework, A 2 AR and S AR, then: 1. A+ as fB 2 AR j A attacks Bg and 2. S+ as fB 2 AR j A attacks B f or some A 2 Sg. 3. A as fB 2 AR j B attacks Ag and 4. S as fB 2 AR j B attacks A f or some A 2 Sg. 5. S is con ict-free i S \ S+ = ;. 6. S defends an argument A i A S+. 7. F : 2AR ! 2AR as F (S) = fA 2 AR j A is def ended by Sg.
It is possible to de ne the semantics in terms of admissible sets as follows: De nition 3. [4] Let AF := hAR; attacksi be an argumentation framework and S AR be a con ict-free set of arguments, then: 1. S is admissible i S F (S). 2. S is a complete extension i S = F (S). 3. S is a preferred extension i S is a maximal (w.r.t. set inclusion) complete extension.
The SS semantics is similar to the preferred semantics [4], but instead of maximizing S it is required to maximize S [S+, as states the following de nition: De nition 4. [4] Let AF := hAR; attacksi be an argumentation framework and S AR be a con ict-free set of arguments, then: S is called a SS extension i S is a complete extension where S [ S+ is maximal
The semi-stable semantics accepts an equivalente statements, as follows: Proposition 1. [4] Let AF := hAR; attacksi be an argumentation framework and let S AR. The following statements are equivalent: 1).- S is a complete extension such that S [ S+ is maximal (De nition No. 4), and 2).- S is an admissible set such that S [ S+ is maximal. 3
Computing SS Semantics by 0-1 Integer Programming In this section we show: the 0-1 integer programming formulation for the SS semantics problem, its encoding in FICO Xpress Mosel1 language and also explain the objective function and constraints, as well as the iterative process for computing all the SS semantics' extensions. 3.1
Semi-Stable Semantics Problem Formulation First of all, consider that it is required to have a mechanism to work with attacks more suitable than working with the adjacency matrix of a given AF, then we de ne: De nition 5. Let AF := hAR; attacksi be an argumentation framework, then: Ri = fj 2 AR : (j; i) 2 attacksg 8i 2 AR, is the set of nodes attacking node i, and R = fRi : i 2 ARg.
Considering De nitions 2, 3, and 5 we restate the admissible set de nition in order to be able to derive the linear constraint that assures admissibility. De nition 6. Let AF := hAR; attacksi be an argumentation framework, and set S AR, then S is admissible i 8i 2 S; 8j 2 Ri ; 9k 2 S; ((k; j) 2 attacks)). 1 http://www.fico.com/en/wp-content/secure_upload/
Xpress-Mosel-User-Guide.pdf
Si = (0 if i 62 S
1 if i 2 S Si+ = (0 if i 62 S+ 1 if i 2 S+ 8 i 2 AR 8 i 2 AR De nition 7. The set M = fi 2 AR : Si = 1 in the optimal solutiong, and C = fi 2 AR : Si = 0 in the optimal solutiong is M's complement.
Accordingly, we de ne the decision variable for S+, as follows:
Now consider that decision variables in a mathematical program are a set of quantities that need to be determined by the solver in order to solve the problem, i.e. when the best values of the decision variables have been identi ed in order to maximize or minimize (optimal solution) the objective function. Therefore, the rst step is to de ne the required binary decision variables.
Considering that De nition 4 and Proposition 1 state a SS extension in terms of an admissible set S such that S [ S+ is maximal, then it is required a decision variable for S and other for S+, as follows: De nition 9. The set M u = fi 2 AR : Ui = 1 in the optimal solutiong, and Cu = fi 2 AR : Ui = 0 in the optimal solutiong is Mu's complement.
If the 0-1 program formulation with a given AF has an optimal solution, then we can think of the SS semantics in terms of a serie of solutions that the model nds in each iteration, as follows: fM u1; M u2; :::; M uqg : jM u1j jM u2j ::: jM uqj which states that the M u1 has the largest possible cardinality, and that jM u1j jM u2j ::: jM uqj such that jM uqj has the smallest possible cardinality.
Thus, It is also required a decision variable for a couple of either/or constraints [9] which we will add per each iteration (see section 3.3) in order to help to assure S + S+ maximality w.r.t. set inclusion, i.e. they help us just to avoid that solution M ut+1 be di erent than solution found in iteration t; t 1; : : : ; 1 or any subset of them, as follows:
This way, the optimal solution to the 0-1 integer problem formulation for the SS semantics can be stated in terms of maximizing S [ S+.
De nition 8. The set M + = fi 2 AR : Si+ = 1 in the optimal solutiong, and C+ = fi 2 AR : Si+ = 0 in the optimal solutiong is M +' complement.
It is required to have a decision variable for the union of this sets, as follows:
Ui =
(0 if i 62 S [ S+
1 if i 2 S [ S+
8i 2 AR
(
Taking into account that a mathematical solver searches in the solution space
for one optimal solution for a given problem formulation, then if we want all the
extensions of a given AF, it is required to solve a series of binary programming
models, one for each extension. Since an AF semantics is made up of several
sets, we use M ut to denote the solution of the binary subproblem in iteration t,
and q to denote the amount of preferred extensions that a given AF has, such
that q 1 and q 2 N. The 0-1 integer problem formulation to compute the tth
semi-stable extension of a given AF is the following, including (
X (Si + Si+) i2AR Subject to:
In (
X Sk 1
Si k2Rj Si+ Si+
Sj X Sj j2Ri
1 Ui = Si + Si+ X Si i2Cr ( X i2Cur Si 2 f0; 1g S+
i 2 f0; 1g Ui 2 f0; 1g Yi 2 f0; 1g i2Mur ( X Ui) + 1
Ui) + jM urj
jARj Yr jARj (1
Yr)
8i 2 AR; 8j 2 Ri
8i 2 AR; 8j 2 Ri
8i 2 AR; 8j 2 Ri
regard to set inclusion. Subsection 3.3 explains how constraints (
Con ict-Freeness Note that the de nition of a con ict-free set in De nition 2 item 5 is not stated in terms of attacks's directions but just in terms of attacks between arguments, without considering the directions of them. In this way, such a de nition is considering an arc just as an edge, and therefore the whole AF can be regarded as an undirected graph, at least with regard to the con ict-free set problem.
Note that the expression Si + Sj 1, in constraint (
Admissibility. The intuition of De nitions 1, 2 and 3 is that an admissible set
S should defend each of its arguments, and De nition 6 just restates it in terms
of De nition 5. Note that in De nition 6 the existential quanti er suggests that
constraint (
Creation of S+. So far, we have a con ict-free and admissible set, and it is
still required to build Si+ as in De nition 2 item 2 8i 2 M +. It should be done
by decision variables (
Thus, M 1 is a con ict-free and admissible set, considering that (
Construction of U = S + S+. In order to avoid that M ut+1 be a subset of
M ut, it is required to have as decision variables the union of (
Notice that the problem formulation made up of (
We will denote this program as BIP in order to make reference to it. 3.3
Note that once the model is implemented in a mathematical programming language, the program just compute one SS extension. In order to compute an additional extension it is required to solve the model again, but adding additional constraints to avoid getting previous solutions, which will force to get another di erent extension. In this setting, it is required to iterate to nd all the extensions of a given AF until there is no a feasible solution. Thus, we have to take care of getting no subsets of M t (Case No. 1), and no proper subsets of M ut (Case No. 2).
Case No. 1. Then, in order to nd the constraint that we have to add to avoid that M t+1 M t, consider De nitions 7, and let P be the solution in iteration t + 1, and M the solution in iteration t, thus:
P
M $ 8x(x 2 P ! x 2 M ) $ 8x(x 62 P _ x 2 M ) P 6 M $ 9x(x 2 P ^ x 62 M ) $ 9x(x 2 P ^ x 2 C) (21) (22) 3 http://www. co.com/en/products/ co-xpress-optimization-suite/
The intuition of this result is that it is required that solution in iteration t + 1
has at least one element from solution's complement in iteration t. Constraint
(
Case No. 2. Additionally, we have to add other constraint to avoid that M ut+1 M ut. In order to nd such a constraint(s), consider De nition 9 and let P be the solution in iteration t + 1, and M u the solution in iteration t, thus: P P 6
M u $ 8x(x 2 P ! x 2 M u) ^ 9x(x 62 P ^ x 2 M u)
$ 8x(x 2= P _ x 2 M u) ^ 9x(x 62 P ^ x 2 M u) M u $ 9x(x 2 P ^ x 62 M u) _ 8x(x 2 P _ x 62 M u) $ 9x(x 2 P ^ x 2 Cu) _ 8x(x 2 P _ x 62 M u) (23) (24) (25) (26)
Note that the intuition of the expression in (22) should be the same as that of the rst part of the disjunction in (26). Consider also that we wanted to nd an expression that led us to a linearized constraint to avoid getting proper subsets of previous solutions. Thus, we can have a proper subset when jP j < jM uj holds, and therefore apply the expression 9x(x 2 P ^ x 2 Cu), otherwise apply the expression 8x(x 2 P _ x 62 M u), whose intuition is that the new solution P can have any element, which means that it requires no constraint. Thus, we have just to work with the rst part of the disjunction. Therefore, we have to linearize the expression [9]: if jP j < jM uj then X Ui 1 $ not (jP j < jM uj) _ X Ui 1 i2Cu $ jP j $
X i2Mur
Ui jM uj _ X Ui
i2Cu jM urj _ i2Cu
1 X i2Cur
Ui 1 which means that the model should apply either Pi2Mur Ui jM urj or Pi2Cu Ui 1, but to satisfy the simultaneousness assumption of binary integer programming, they must be transformed considering the following general format [9]: f (x1; x2; : : : ; xn)
By g(x1; x2; : : : ; xn)
B(1
y)
where B is a big number, in our case B = jARj, and y is the binary variables
de ned in (17). This transformation becomes constraints (
Now, let SSE a set of all the SS extensions of a given AF, and M C a set
of additional (
Solve BIP [ M C;
Theorem 1. Let AF be an argumentation framework, R as de ned in 5,
M; M +; and M u is a solution of BIP , and SSE is computed as described in
Algorithm No. 1, then SSE is the set of all SS extensions of AF .
Proof. Sketch: From the above discussion consider the following items:
1. By OF (
In order to measure the performance of the 0-1 integer program, it was compared with an ASP approach: the ASPARTIX 4 [8] which we will call just ASP1, and we used the solver Clingo5. Additionally, the approach based on 0-1 integer programming will be called BIP, and we used the ad-hoc Xpress6 solver. The instances that were used during all the experiments were taken from the ASPARTIX web page 7.
As a summary, BIP approach had a performance quit similar to the ASP approach for arbitrary instances8, but had problems until 60-arguments instances for 4-grid and 8-grid instances. This result shows that the BIP approach performed well and it has a great opportunity space for improving. 4 The program code is available at ASPARTIX's web page. It is worth mentioning that ASPARTIX is the de facto benchmark for argumentations systems 5 http://potassco.sourceforge.net 6 http://www. co.com/en/Products/DMTools/Pages/FICO-Xpress-Optimization
Suite.aspx 7 http://www.dbai.tuwien.ac.at/research/project/argumentation/systempage 8 There is a complete explanation of each kind of instance in [7] We have presented a novel method for computing SS semantics using binary integer programming, the performance was good although the ASP approach outperformed it.
However, it is well known that binary integer programs can be improved, in order to compute more e ciently its objective function, by using mathematical programming techniques such as relaxation or adding strong valid inequalities. It means that it is possible to improve the performance of this novel approach for computing SS semantics.
This new approach constitutes an alternative for computing AF semantics using mathematical programming, and even though we used an state of the art mathematical programming solver, there exists several libraries for java, C++ and other general purpose languages.