Rosa Figueiredo
email: rosa.figueiredo@univ-avignon.fr

Yuri Frota

Martine Labbé
email: mlabbe@ulb.ac.be

A branch-and-cut algorithm for the maximum k-balanced subgraph of a signed graph

Keywords: Signed graph, Balanced graph, Graph partition, Integer programming, Social networks

We are interested in the solution of the maximum k-balanced subgraph problem. Let G = (V, E, s) be a signed graph and k a positive scalar. A signed graph is k-balanced if V can be partitioned into at most k sets in such a way that positive edges are found only within the sets and negative edges go between sets. The maximum k-balanced subgraph problem is the problem of finding a subgraph of G that is k-balanced and maximum according to the number of vertices. This problem has applications in clustering problems appearing in collaborative vs conflicting environments. The particular case k = 2 yields the problem of finding a maximum balanced subgraph in a signed graph and its exact solution has been addressed before in the literature. In this paper, we provide a representatives formulation for the general problem and present a partial description of the associated polytope, including the introduction of strengthening families of valid inequalities. A branch-and-cut algorithm is described for finding an optimal solution to the problem. An ILS metaheuristic is implemented for providing primal bounds for this exact method and a branching rule strategy is proposed for the representatives formulation. Computational experiments, carried out over a set of random instances and on a set of instances from an application, show the effectiveness of the valid inequalities and strategies adopted in this work.

Introduction

Let G = (V, E) be an undirected graph where V = {1, 2, . . . , n} is a set of vertices and E is a set of edges connecting pairs of vertices. Consider a function s : E → {+, -} that assigns a sign to each edge in E. An undirected graph G together with a function s is called a signed graph. Let G = (V, E, s) denote a signed graph. We assume that a signed graph has no parallel edges. An edge e ∈ E is called negative if s(e) =and positive if s(e) = +. Let E -and E + denote, respectively, the sets of negative and positive edges in a signed graph. Notice that, according to the definitions above, E = E -∪E + and E -∩ E + = ∅. For a vertex set S ⊆ V , let E[S] = {(i, j) ∈ E | i, j ∈ S} denote the subset of edges induced by S. A signed graph G is balanced if its vertex set can be partitioned into sets W (possibly empty) and V \ W in such a way that

E[W ] ∪ E[V \ W ] = E + .
Let k be a given parameter satisfying k ∈ {1, . . . , n}. A signed graph G is k-balanced if its vertex set V can be partitioned into sets N 1 , N 2 , . . . , N l , with l ≤ k, in such a way that ∪ 1≤i≤l E[N i ] = E + . Such a partition is called a l-partition in what follows. A signed graph is clusterable if it is n-balanced (see Figure 1). A clusterable signed graph is called a colorable signed graph in [START_REF] Cartwright | A note on a matrix criterion for unique colorability of a signed graph[END_REF]. The problem that is studied herein can be stated as follows.

Definition 1.1 (k-MBS problem). Let G = (V, E, s) be a signed graph and k be a scalar value satisfying k ∈ {1, . . . , n}. The maximum k-balanced subgraph problem is the problem of finding an induced subgraph H = (V � , E[V � ], s)of G such that H is k-balanced and maximizes the cardinality of the vertex set V � . Let us denote this maximal value by v(G, k).

The particular case k = 2 yields the problem of finding a maximum balanced subgraph in a signed graph [START_REF] Barahona | Facets of the balanced (acyclic) induced subgraph polytope[END_REF][START_REF] Figueiredo | The maximum balanced subgraph of a signed graph: applications and solution approaches[END_REF][START_REF] Figueiredo | An exact approach to the problem of extracting an embedded network matrix[END_REF]. The k-MBS problem is closely related to a clustering problem defined over a weighted signed graph G: the correlation clustering problem [START_REF] Bansal | Correlation clustering[END_REF]. An optimal solution for the k-MBS problem defined on G is a subgraph of G that admits a correlation clustering solution with no disagreements.

Signed graphs were introduced by Heider in [START_REF] Heider | Attitudes and cognitive organization[END_REF] with the purpose of describing sentiment relations between people pertaining to the same social group and to provide a systematic statement of social balance theory. Cartwright et al. [START_REF] Cartwright | Structural balance: A generalization of heiders theory[END_REF] formalized Heider's theory, stating that a balanced signed graph could be partitioned into two mutually antagonistic subgroups of vertices each having internal solidarity. The definition of a balanced signed graph was extended to the definition of a clusterable signed graph in [START_REF] Davis | Clustering and structural balance in graphs[END_REF]. 1 We refer the reader to [START_REF] Zaslavsky | A mathematical bibliography of signed and gain graphs and allied areas[END_REF] for a bibliography of signed graphs.

In the last decades, signed graphs have shown to be a very attractive discrete structure for social network researchers. Analyzing and mining social networks can help gain a better understanding of human behavior in social groups. In [19, 20, [START_REF] Esmailian | Mesoscopic analysis of online social networks: The role of negative ties[END_REF][START_REF] Figueiredo | Mixed integer programming formulations for clustering problems related to structural balance[END_REF][START_REF] Levorato | Evaluating balancing on social networks through the efficient solution of correlation clustering problems[END_REF][START_REF] Mendonça | Relevance of negative links in graph partitioning: A case study using votes from the european parliament[END_REF] the solution of clustering problems defined on signed graphs was used as a tool for the evaluation of structural balance in a social network. Balancing on signed graphs was used in [START_REF] Inohara | A formal theory on decision making with interperception[END_REF][START_REF] Inohara | On conditions for a meeting not to reach a deadlock[END_REF][START_REF] Inohara | Characterization of clusterability of signed graph in terms of newcomb's balance of sentiments[END_REF][START_REF] Inohara | Clusterability of groups and information exchange in group decision making with approval voting system[END_REF] to discuss properties and concepts in the context of group decision making. Applications of balancing problems defined on signed graphs also appear in soft game theory [START_REF] Howard | n-person soft games[END_REF], in system biology [START_REF] Dasgupta | Algorithmic and complexity results for decompositions of biological networks into monotone subsystems[END_REF], in portfolio analysis in risk management [START_REF] Figueiredo | The maximum balanced subgraph of a signed graph: applications and solution approaches[END_REF][START_REF] Harary | Signed graphs for portfolio analysis in risk management[END_REF], in voting behavior [START_REF] Arinik | Signed graph analysis for the interpretation of voting behavior[END_REF] and in the detection of embedded matrix structures [START_REF] Figueiredo | The maximum balanced subgraph of a signed graph: applications and solution approaches[END_REF].

The k-MBS problem has applications in clustering problems appearing in collaborative vs. conflicting environments. Consider a social group (for example, a political decision group). In this context, each vertex in the signed graph represents a person in this social group while an edge represents a sentiment relation (mutual liking or disliking, friendship or enmity, cooperation or defection, interaction or avoidance) between a pair of vertices and determined by past observations. An optimal solution of the k-MBS problem provides us with an efficient way to define l ≤ k teams (groups with political allies): positive relations are allowed only within teams, negative relations link different teams while the number of elements involved is maximized. Additional restrictions can be taken into account, such as size constraints for the teams or a fixed number of teams. A weighted version of the k-MBS problem can be defined whenever weights are used to graduate positive and negative relations. Balancing on signed graphs is used in [START_REF] Harary | Signed graphs for portfolio analysis in risk management[END_REF] to define a risk-limiting strategy for portfolio design. In this context, a security is represented by a vertex in the signed graph while the correlation between securities is represented by the set of signed edges. The efficient solu-tion of the k-MBS problem defined over a signed graph representing a big set of securities gives an efficient way to define a limited-risk portfolio. We refer the reader to [START_REF] Figueiredo | The maximum balanced subgraph of a signed graph: applications and solution approaches[END_REF] for a more detailed discussion about applications of the k-MBS problem.

Solution approaches have been proposed in the literature for the 2-MBS problem. In [START_REF] Harary | A simple algorithm to detect balance in signed graphs[END_REF], Harary presented a simple linear procedure to detect whether a signed graph is 2-balanced. Descriptions of the polytope associated with the 2-MBS problem were given in [START_REF] Barahona | Facets of the balanced (acyclic) induced subgraph polytope[END_REF][START_REF] Figueiredo | An exact approach to the problem of extracting an embedded network matrix[END_REF]. A greedy heuristic approach was proposed in [START_REF] Gülpinar | Extracting pure network submatrices in linear programs using signed graphs[END_REF] for this particular case and is able to find an optimal solution whenever G is a balanced signed graph. Recently, Figueiredo et al. [START_REF] Figueiredo | The maximum balanced subgraph of a signed graph: applications and solution approaches[END_REF] contributed to the efficient solution of the 2-MBS problem by developing a pre-processing routine, an efficient GRASP metaheuristic, and improved versions of the greedy heuristic proposed in [START_REF] Gülpinar | Extracting pure network submatrices in linear programs using signed graphs[END_REF]. A branch-and-cut algorithm was proposed in [START_REF] Figueiredo | An improved branch-and-cut code for the maximum balanced subgraph of a signed graph[END_REF][START_REF] Figueiredo | An exact approach to the problem of extracting an embedded network matrix[END_REF] to the exact solution of the 2-MBS problem. Computational approaches (including optimization approaches) have been described in the literature over the past years for the solution of other balancing problems defined on signed graphs [START_REF] Abell | Structural balance: a dynamic perspective[END_REF][START_REF] Charikara | Clustering with qualitative information[END_REF][START_REF] Demaine | Correlation clustering in general weighted graphs[END_REF][START_REF] Doreian | A partitioning approach to structural balance[END_REF][START_REF] Doreian | Partitioning signed social networks[END_REF][START_REF] Drummond | Efficient solution of the correlation clustering problem: an application to structural balance[END_REF][START_REF] Figueiredo | Mixed integer programming formulations for clustering problems related to structural balance[END_REF][START_REF] Yang | Community mining from signed social networks[END_REF]. Most of them have been used to analyze and mine social networks. To the best of our knowledge, the general case of the k-MBS problem has never been treated in the literature before.

In this paper, we contribute to the efficient solution of the k-MBS problem. We provide an integer linear programming formulation to the problem strengthened by the introduction of families of valid inequalities of the associated polytope. Based on these results, a branch-and-cut algorithm is developed to the problem. A primal heuristic is implemented for feeding the exact method with primal bounds and a constraint branching rule is proposed. Preliminary results were previously reported in a four-page conference paper [START_REF] Figueiredo | Solution of the maximum kbalanced subgraph problem[END_REF].

We next give some notations and definitions to be used throughout the paper. Let G = (V, E) be an undirected graph. For a vertex set S ⊆ V , we define

N (S) = {j ∈ V | (i, j) ∈ E, i ∈ S}. A set K ⊆ V is a clique in G if each pair of vertices i, j ∈ K is joined by an edge (i, j) ∈ E. A set I ⊆ V is a stable set in G if no
pair of vertices i, j ∈ I is joined by an edge in E; i.e. (i, j) � ∈ E. Let α(G) denote the cardinality of a maximum stable set in G. We represent a cycle by its vertex set C ⊆ V . A hole is a chordless cycle of length at least four. An odd hole is a hole with an odd number of vertices. Now, consider a function s : E → {+, -} and let G = (V, E, s) denote a signed graph. Definitions and notations for an undirected graph G = (V, E) also apply to the signed graph G = (V, E, s). We define

G -= (V, E -) and G + = (V, E + ). For a vertex set S ⊆ V , we define N -(S) = {j ∈ V | (i, j) ∈ E -, i ∈ S}, N + (S) = {j ∈ V | (i, j) ∈ E + , i ∈ S} and N -(S) = V \ (N -(S) ∪ S). A set K ⊆ V is called a negative (positive) clique if each
pair of vertices in K is joined by a negative (positive) edge. A positive (negative) hole is a hole with only positive (negative) edges.

Complexity and integer formulation

Let G = (V, E, s) be a signed graph and k a positive scalar satisfying k ∈ {1, . . . , n}. The k-MBS problem is NP-hard. The particular case k = 2 is proven to be NP-hard in [START_REF] Barthold | A good submatrix is hard to find[END_REF]. Indeed, the k-MBS problem is the optimization version of an NP-complete decision problem, namely, the induced subgraph with property π (property π must hold for arbitrarily large graphs, do not hold for all graphs and be hereditary, i.e., it is valid for all induced subgraphs of G whenever it is valid for G) ( [START_REF] Garey | Computers and intractability[END_REF], pp. 195). For the k-MBS problem, property π is "H is k-balanced".

Next, we see that the optimal solution of the independent set problem defined over G -provides a lower bound for the k-MBS problem.

Proposition 2.1. α(G -) = v(G, 1) ≤ v(G, 2) ≤ . . . ≤ v(G, n).
Proof. Consider a signed graph G. The feasible solution space of the (k -1)-MBS problem is contained in the feasible solution space of the k-MBS problem. Then, v(G, k -1) ≤ v(G, k), for all, 2 ≤ k ≤ n. It is not difficult to check that each feasible solution for the 1-MBS problem defined over G is a feasible solution for the stable set problem defined over G -, and vice-versa. A feasible solution for the 1-MBS problem is by definition a 1-balanced subgraph

H = (V H , E H ) of G which implies E[V H ] = E H ⊆ E + and V H is an independent set in G -.
A feasible solution for the independent set problem defined over

G -= (V, E -) is a vertex set I ⊆ V such that for all i, j ∈ I, (i, j) � ∈ E -. That implies H = (I, E[I]) is a 1-balanced subgraph of G.
In this work, we propose a discrete linear formulation for the k-MBS problem; more precisely, we propose a representatives formulation for this problem. Integer linear formulations have already been presented for correlationclustering problems [START_REF] Demaine | Correlation clustering in general weighted graphs[END_REF][START_REF] Figueiredo | Mixed integer programming formulations for clustering problems related to structural balance[END_REF] and for the 2-MBS problem [START_REF] Figueiredo | An exact approach to the problem of extracting an embedded network matrix[END_REF]. Representatives formulations have been successfully applied to the solution of graph clustering problems [START_REF] Ales | Polyhedral combinatorics of the kpartitioning problem with representative variables[END_REF][START_REF] Bahiense | A branch-and-cut algorithm for equitable coloring based on a formulation by representatives[END_REF][START_REF] Campêlo | On the asymmetric representatives formulation for the vertex coloring problem[END_REF][START_REF] Campelo | Cliques, holes and the vertex coloring polytope[END_REF][START_REF] Catanzaro | A class representative model for pure parsimony haplotyping[END_REF][START_REF] Figueiredo | Mixed integer programming formulations for clustering problems related to structural balance[END_REF][START_REF] Frota | A branch-and-cut algorithm for partition coloring[END_REF].

We define the arc sets

A = {(i, j) | i ∈ V, j ∈ N -({i}), i < j} and A 0 = A ∪ {(i, i) | i ∈ V }.
An arc (i, j) ∈ A 0 indicates that vertex i can represent vertex j, or equivalently that vertex j can be represented by vertex i. Let D(i) = {j ∈ V | (i, j) ∈ A 0 } denote the set of all vertices that can be represented by i and let O(j) = {i ∈ V | (i, j) ∈ A 0 } denote the set of all vertices that can represent j. Additionally, let S i denote a vertex set such that: S i ⊆ D(i) and i ∈ S i . We say that i is the representative vertex of S i .

A feasible solution in our formulation defines a k-balanced subgraph of G. Let n = |V | and m = |A|. To describe this feasible set, we use binary decision variables x ∈ {0, 1} n+m that define a l-partition, l ≤ k, of a k-balanced subgraph. For each vertex i ∈ V ,

x i i =    1 if i is a representative vertex, i.e.,
a set S i belongs to the l-partition, 0 otherwise. Also, for each arc (i, j) ∈ A, we define

x i j =   
1 if vertex j is represented by vertex i, i.e., j belongs to a set S i in the l-partition, 0 otherwise.

The formulation follows.

Maximize

� (i,j)∈A 0 x i j (1)
subject to � i∈O(j)

x i j ≤ 1, ∀ j ∈ V, (2)
� i∈V x i i ≤ k, (3)
x i j ≤ x i i , ∀ (i, j) ∈ A, (4)
x p i + x p j ≤ x p p , ∀ (i, j) ∈ E -, ∀ p ∈ O(i) ∩ O(j), (5)
x p i + x q j ≤ 1, ∀ (i, j) ∈ E + , ∀ p ∈ O(i), ∀ q ∈ O(j) \ {p}, (6)
x i i ∈ {0, 1}, ∀ i ∈ V, (7)
x i j ∈ {0, 1}, ∀ (i, j) ∈ A. (8)
Constraints (2) establish that vertex j must be represented by at most one vertex, i.e., vertex j must belong to at most one cluster in the l-partition. The total number of representative vertices is limited to k by constraint (3), i.e., the total number of clusters in the l-partition is limited to k. Constraints (4) forbid vertex j to be represented by vertex i unless i is a representative vertex. Consider a negative edge (i, j) ∈ E -. Constraints [START_REF] Atamtürk | Conflict graphs in solving integer programming problems[END_REF], written for (i, j), ensure that vertices i and j cannot be represented by a same vertex, i.e., i and j cannot belong to a same cluster in the l-partition. Consider a positive edge (i, j) ∈ E + . Constraints [START_REF] Bahiense | A branch-and-cut algorithm for equitable coloring based on a formulation by representatives[END_REF], written for (i, j), ensure that vertices i and j are represented by the same vertex whenever both i and j belong to the feasible solution, i.e., in that case vertices i and j belong to the same cluster in the l-partition. Constraints [START_REF] Bansal | Correlation clustering[END_REF] and [START_REF] Barahona | Facets of the balanced (acyclic) induced subgraph polytope[END_REF] impose binary restrictions to the variables. Finally, the objective function (1) looks for a maximum subgraph. Let us refer to this formulation as IP (G, k).

Polyhedral study

In this section, we assume that G is a connected graph and that k ≥ 2. The k-MBS polytope P G,k associated with formulation IP (G, k) is defined here as

P G,k = conv{x ∈ � n+m | x satisfies (2)-(8)}.
Additional notations will be necessary before we can proceed. Consider a set of l disjoint vertex sets I = {N 1 , . . . , N l }. The incidence vector x I ∈ � n+m is defined as: for each i ∈ V , x I i i = 1 if i is the representative vertex of N t , for some 1 ≤ t ≤ l, and x I i i = 0 otherwise; for each (i, j) ∈ A, x I i j = 1 if j ∈ N t , i is the representative vertex of N t , for some 1 ≤ t ≤ l, and x I i j = 0 otherwise. Moreover, let I i = {{i}}, for i ∈ V , and let I ij = {{i, j}}, for (i, j) ∈ A.

Lemma 3.1. The polytope P G,k is full-dimensional, i.e., dim(P G,k ) = n + m.

Proof. Since P G,k contains the null vector, it is sufficient to present other n + m affinely independent solutions x ∈ � n+m in P G,k . Consider the following solutions: x Ii , for each i ∈ V , and x Iij , for each (i, j) ∈ A. Clearly, these n + m affinely independent solutions belong to P G,k .

First, we investigate necessary and sufficient conditions for some inequalities in formulation IP (G, k) to define facets of P G,k .

Lemma 3.2 (Trivial inequalities).

(a) For all (i, j) ∈ A, x i j ≥ 0 defines a facet of P G,k ;

(b) for all (i, j) ∈ A, x i j ≤ 1 does not define a facet of P G,k ;

(c) for all i ∈ V , x i i ≥ 0 defines a facet of P G,k if and only if, for each vertex j ∈ V , (i, j) � ∈ A;

(d) for all i ∈ V , x i i ≤ 1 defines a facet of P G,k if and only if (i) for each vertex j ∈ V , (j, i) / ∈ A, and (ii) for each vertex j ∈ V , (i, j) / ∈ E + .

Proof. The proof is straightforward.

The methodology that is used in the facet-defining proofs of this paper is stated in the following. Let b T x ≤ β be a valid inequality to polytope P G,k and F = {x ∈ P G,k | b T x = β} be the proper face of P G,k defined by this inequality. In order to prove that F is a facet of P G,k , we assume there is an inequality a T x ≤ α, valid for P G,k , such that F ⊆ F a = {x ∈ P G,k | a T x = α} and show that the inequality defining F a can be written as a positive scalar multiple of the inequality defining F (see Theorem 3.6 in [START_REF] Nemhauser | Integer and Combinatorial Optimization[END_REF]). Lemma 3.3. Consider a vertex p ∈ V . Inequality [START_REF] Abell | Structural balance: a dynamic perspective[END_REF] written for p, i.e., � i∈O(p)

x i p ≤ 1, defines a facet of polytope P G,k if and only if, for each i ∈ V \ {p}, (i, p) / ∈ E + .
Proof. Suppose that a p p = α and let i ∈ O(p) \ {p}. Define the set of disjoint vertex sets I 1 = {{p}, {i}}. From the incidence vectors x I1 and x Iip in a T x = α we can conclude that a i p = α. Consider an arc (p, j) ∈ A. The solutions x Ip and x Ipj lead to a p j = 0. Now, consider an arc (i, j) ∈ A such that i, j � = p and define the set of disjoint vertex sets I 2 = {{p}, {i, j}}. The incidence vectors x I1 and x I2 imply a i j = 0. Consider a vertex i ∈ V \ {p}. From the solutions x Ip and x I1 we can conclude that a i i = 0. Finally, we argue that the inequality is not facet defining if there is a vertex q such that (q, p) ∈ E + . In this case, the inequality is dominated by inequality � i∈O(p) x i p + x q q ≤ 1, if q > p, and by inequality � i∈O(p)\{q} x i p + x q q ≤ 1, if q < p.

Lemma 3.4. Consider an arc (p, q) ∈ A. Inequality (4) written for (p, q), i.e.,

x p qx p p ≤ 0, defines a facet of polytope P G,k if and only if, for each (p, j) ∈ A, (q, j) / ∈ E -.

Proof. The incidence vector x Ipq and the null vector in a T x = α lead us to a p q = -a p p . Consider a vertex i ∈ V \ {p}. We conclude that a i i = 0 from the null vector and the incidence vector x Ii . Let (i, j) ∈ A be an arc such that i � = p. From x Iij and the null vector we arrive to a i j = -a i i = 0. Now consider an arc (p, j) ∈ A, with j � = q and define the set I 2 = {{p, q, j}}. Notice that, x I2 ∈ P G,k since (q, j) / ∈ E -. From solutions x Ipq and x I2 we conclude that a p j = 0. Finally, assume that there is an arc (p, j) ∈ A such that (q, j) ∈ E -. In this case, the associated inequality is dominated by an inequality (5) written for edge (q, j) and vertex p, i.e, x p q + x p j ≤ x p p .

Constraints ( 6) can be replaced in formulation IP (G, k) by the stronger inequalities described next. Lemma 3.5 (Strengthened positive-edge inequality). Consider a positive edge (i, j) ∈ E + . Let S ⊆ O(i) be a subset of candidates to represent vertex i. The inequality � p∈S

x p i + � p∈O(j)\S x p j ≤ 1, (9)
is valid for P G,k and dominates constraints [START_REF] Bahiense | A branch-and-cut algorithm for equitable coloring based on a formulation by representatives[END_REF] in formulation IP (G, k).

Proof. Consider a vertex p ∈ S and let T = O(j) \ {p}. Adding inequalities [START_REF] Bahiense | A branch-and-cut algorithm for equitable coloring based on a formulation by representatives[END_REF] written to each combination of vertices p and q ∈ T , and dividing the result by |T | we obtain the inequality

x p i + (1/|T |) � q∈T x p j ≤ 1. Since � q∈T x p j ∈ {0, 1}
, the fractional coefficient in the left-hand side of this inequality can be rounding up giving us x p i + � q∈T x p j ≤ 1. Adding now this inequality written to each p ∈ S, dividing the result by |S| and rounding fractional coefficients in the left-hand side of the obtained inequality, we obtain inequality [START_REF] Barthold | A good submatrix is hard to find[END_REF]. Clearly constraints [START_REF] Bahiense | A branch-and-cut algorithm for equitable coloring based on a formulation by representatives[END_REF] are dominated by inequalities [START_REF] Barthold | A good submatrix is hard to find[END_REF].

Next, we introduce valid inequalities for P G,k which are related to some substructures of the signed graph. We will see that inequalities (5) and ( 9) are particular cases of clique-based families of valid inequalities.

Valid inequalities based on subgraph structures

The clique-based inequalities introduced in the next result are a generalization of negative-edge inequalities [START_REF] Atamtürk | Conflict graphs in solving integer programming problems[END_REF].

Lemma 3.6 (Negative-clique inequality). Let K -⊆ V be a negative clique in G. Consider a vertex p ∈ V such that (p, i) ∈ A for each i ∈ K -. The inequality � i∈K - x p i ≤ x p p , (10)
is valid for P G,k . This inequality defines a facet for polytope P G,k if and only if K -is a maximal negative clique in G.

Proof. We use induction on the length of negative clique K -. If |K -| = 1, the validity follows from constraints [START_REF] Atamtürk | Conflict graphs in solving integer programming problems[END_REF]. Assume that the inequality is valid whenever the negative clique K -has a given size p ≥ 1 and consider a negative clique inequality for which |K -| = p + 1. Consider any two vertices u, v ∈ K -. The following inequalities are valid: inequality [START_REF] Campêlo | On the asymmetric representatives formulation for the vertex coloring problem[END_REF] written to K -\ {u}; inequality [START_REF] Campêlo | On the asymmetric representatives formulation for the vertex coloring problem[END_REF] written to K -\ {v}; and constraints (5) written to negative edge (u, v). Adding up these three inequalities, dividing the result by two and rounding down the right-hand side of the obtained inequality we conclude the validity proof. Now we prove the facet defining conditions. Consider an arc (p, i) ∈ A with i ∈ K -. From the incidence vector x Ipi and the null vector in a T x = α we conclude that a p i = -a p p , for each i ∈ K -. Now consider a vertice i ∈ V \ {p}. From solution x Ii and the null vector we arrive to a i i = 0. Consider an arc (j, i) ∈ A with i ∈ K -and j ∈ V \ {p}. From the incidence vector x Iji and the null vector we conclude that a j j + a j i = 0. Since a j j = 0, we arrive to a j i = 0. Now let (i, j) ∈ A be an arc such that i ∈ K -and j ∈ V \ {p}. From the incidence vector x Iij and the null vector, we conclude that a i j = 0. Consider an arc (p, j) ∈ A with j ∈ V \ K -. Since K -is a maximal negative clique, there exists a vertice i ∈ K -such that (j, i) � ∈ E -. This allow us to define an incidence vector x I � with I � = {p, j, i}. The incidence vectors x I � and x Ipi in a T x = α lead us to a p j = 0. Now consider an arc (j, p) with j ∈ V \ K -. In that case, from the incidence vector x Ijp and the null vector, we conclude that a j p = 0. Let (i, j) ∈ A be an arc such that i, j ∈ V \ K -∪ {p}. From solution x Iij and the null vector, we arrive to a i j = 0. Finally, assume that there is a vertex j ∈ V \ K -∪ {p} such that (j, i) ∈ E -for each i ∈ K -. In this case, the negative-clique inequality defined by K -and p is clearly dominated by an inequality in the same family defined by K -∪ {j} and p.

Positive cliques induce a class of valid inequalities for P G,k that generalizes strongest positive-edge inequalities (9). Lemma 3.7 (Positive-clique inequality). Let K + ⊆ V be a positive clique in G. For each vertex j ∈ K + , consider a set S(j) ⊆ O(j). Additionally, assume that S(i) ∩ S(j) = ∅ for each pair i, j ∈ K + . The inequality

� j∈K + � i∈S(j) x i j ≤ 1, (11)
is valid for P G,k . This inequality defines a facet for polytope P G,k if the following conditions are satisfied.

(i) K + is a maximal positive clique in G, (ii) for each j ∈ K + , S(j) is a maximal set, i.e., O(j) \ ∪ p∈K S(p) = ∅, (iii) for each (i, j) ∈ A, with i, j � ∈ K + , there is a p ∈ K + such that (i, p) � ∈ E + and (j, p) � ∈ E + .
Proof. This proof follows the same lines of the proof in Lemma 3.6. For the validity proof, we use induction on the length of positive clique K + and the validity of constraints [START_REF] Barthold | A good submatrix is hard to find[END_REF]. For the facet-defining proof, as in the proof of the Lemma 10, we use the incidence vectors of partitions (i.e. feasible solutions belonging to the facet) enumerated in Table 1. Remember the facet-defining proof methodology stated in the beginning of this section. Each double line of Table 1 is associated with a set of components of the coefficient vector a ∈ � n+m=|A∪A 0 | . The first column indicates the set of components (or arcs) being considered. The second column exhibits two sets defining incidence vectors satisfying inequality [START_REF] Campelo | Cliques, holes and the vertex coloring polytope[END_REF] with equality, while the third column states the conclusion obtained.

The fourth column presents remarks linking the construction of the incidence vectors used in this proof with facet-defing conditions (i)-(iii). In Table 1, S(K + ) = ∪ p∈K S(p) = ∅ and, for each i ∈ S(K + ), we define p i = j ∈ K + such that i ∈ S(j).

The next valid inequality is a generalization of inequalities [START_REF] Campelo | Cliques, holes and the vertex coloring polytope[END_REF].

Lemma 3.8 (Negative-positive-clique inequality). Let K -⊆ V and K + ⊆ V be, respectively, a negative and a positive clique in G such that, for each pair of vertices i ∈ K -and j ∈ K + , (i, j) ∈ E + . Let p ∈ V be a vertex such that, for each i ∈ K -, (p, i) ∈ A. Moreover, for each vertex j ∈ K + , consider a set S(j) ⊆ O(j) \ {p}. Additionally, assume that S(i) ∩ S(j) = ∅ for each pair i, j ∈ K + . The inequality

� i∈K - x p i + � j∈K + � i∈S(j) x i j ≤ 1, ( 12
)
is valid for P G,k .

Proof. We use induction on the length of negative clique K -. If |K -| = 1, the inequality is a positive-clique inequality and the validity follows from Lemma 3.7.

Assume that the inequality is valid whenever the negative clique K -has a given size p ≥ 1. Now, consider a negative-positive-clique inequality for which

(i, j) ∈ A ∪ A 0 Partitions Conclusion Remark (i, i), i ∈ K + I i a i i = α I i � , i � ∈ K + (i, i), i ∈ S(K + ) Ip a i i = 0 ∃p ∈ K + s.t. (i, p) � ∈ E + due to (i) {{i}, {p}} (i, i), i ∈ V \ (K + ∪ S(K + )) Ip a i i = 0 ∃p ∈ K + s.t. (i, p) � ∈ E + due to (i) {{i}, {p}} (i, j), j ∈ K + , i ∈ S(j) I ij , I j a i j = α (i, j), j ∈ K + , i ∈ S(K + \ j) {{i, j, p i }} a i j = 0 I ip i (i, j), j ∈ K + , i ∈ V \ K + \ S(K + ) (i, j) do not exist due to (ii) (i, j), j ∈ S(K + ), i ∈ K + I ij , I i a i j = 0 (i, j), j ∈ S(K + ), i ∈ S(K + ) {{i, j}, {p}} a i j = 0 p exists due to (iii) Ip (i, j), j ∈ S(K + ), i ∈ V \ K + \ S(K + ) {{i, j}, {p}} a i j = 0 p exists due to (iii) Ip (i, j), i ∈ K + , j ∈ V \ K + \ S(K + ) I ij , I i a i j = 0 (i, j), i ∈ S(K + ), j ∈ V \ K + \ S(K + ) {{i, j}, {p}} a i j = 0 p exists due to (iii) Ip (i, j), i, j ∈ V \ K + \ S(K + )
{{i, j}, {p}} a i j = 0 p exists due to (iii) Ip Table 1: Sketch of feasible solutions used in the facet-defining proof of Lemma 3.7.

|K -| = p + 1. Consider a vertex u ∈ K -. The following inequalities are valid: � i∈K -\{u} x p i + � j∈K + � i∈S(j) x i j ≤ 1 from the inductive hypothesis; x p u + � j∈K + � i∈S(j)
x i j ≤ 1 from Lemma 3.7; and � i∈K -x p i ≤ 1 from Lemma 3.6. We finish this proof by adding up these inequalities, dividing the result by two and rounding down the right-hand side of the obtained inequality.

Holes in G can also give rise to a family of valid inequalities for P G,k . Lemma 3.9 (Hole inequality 1). Let H ⊆ V be a hole in G with t positive edges. Assume that |H| + t is odd. Let p ∈ V be a vertex such that, for each i ∈ H, (p, i) ∈ A. The inequality

� i∈H x p i ≤ �(|H| + t)/2� x p p , (13)
is valid for P G,k .

Proof. Let x be a feasible solution in P G,k . If xp p = 0, the validity follows from inequalities (4) written for each arc (p, i) ∈ A such that i ∈ H. Assume now that xp p = 1. Add up inequalities (5) written for each arc (i, j) ∈ E -such that i, j ∈ H, and the inequalities x p i + x p j ≤ 2x p p written for each arc (i, j) ∈ E + such that i, j ∈ H. The validity follows from dividing the obtained inequality by two and rounding down its right-hand side. Lemma 3.10 (Hole inequality 2). Let H ⊆ V be a hole in G with t negative edges. Assume that |H| + t is odd. For each vertex j ∈ H, consider a set S(j) ⊆ O(j). Additionally, assume that S(i) ∩ S(j) = ∅ for each pair i, j ∈ H such that (i, j) ∈ E. The inequality

� j∈H � i∈S(j) x i j ≤ �(|H| + t)/2� , (14)
is valid for P G,k .

Proof. This validity proof follows exactly the lines of the validity proof in Lemma 3.9: add up the valid inequalities � p∈S(i) x p i + � p∈S(j) x p j ≤ 1 written for each arc (i, j) ∈ E + such that i, j ∈ H, and the inequalities � p∈S(i) x p i + � p∈S(j) x p j ≤ 2 written for each arc (i, j) ∈ E -such that i, j ∈ H. The validity follows from dividing the obtained inequality by two and rounding down its right-hand side.

A signed graph is clusterable if and only if it does not contain a cycle with exactly one negative edge [START_REF] Davis | Clustering and structural balance in graphs[END_REF]. This property motivates the following family of valid inequalities. Lemma 3.11 (1-edge negative cycle). Let C ⊆ V be a cycle in G with exactly one negative edge. For each j ∈ C, let us denote by j -, j + ∈ C the two vertices in C adjacent to j. Let us define, for each j ∈ C, a j j = 2 if (i) (j -, j), (j, j + ) ∈ E + and (ii) j > j -, j + ; a j j = 1 otherwise. The inequality

� j∈C   a j j x j j + � i∈O(j)\{j} x i j   ≤ |C| -1, ( 15
)
is valid for P G,k .

Proof. By definition, a k-balanced signed graph is clusterable. Hence, the following inequality is clearly valid:

� j∈C   x j j + � i∈O(j)\{j} x i j   ≤ |C| -1. ( 16
)
Let p ∈ C be a vertex satisfying (i) and (ii) (see Figure 2). Next, we argue that inequality ( 16) can be strengthened by making α p p = 2 in the the following inequality:

α p p x p p + � i∈O(p)\{p} x i p + � j∈C\{p}   x j j + � i∈O(j)\{j} x i j   ≤ |C| -1. ( 17
)
The assignment x p p = 0 do not impose a limit to the value of α p p . However,

_ + p + p p _ + + + + +
α p p ≤ (|C| -1) - � i∈O(p)\{p} x i p - � j∈C\{p}   x j j + � i∈O(j)\{j} x i j   .
If p is a representative vertex (x p p = 1) and (i) and (ii) are satisfied, vertices p -, p + are forbidden from belonging to a solution. Hence, the highest value the right-hand side of the previous inequality can assume is 2 and happens whenever all |C| -3 vertices in C \ {p, p -, p + } belong to the solution. Now, if we consider the valid inequality [START_REF] Davis | Clustering and structural balance in graphs[END_REF] with α p p = 2, the same procedure can be applied iteratively on each vertex q ∈ C satisfying (i) and (ii) (one must observe that the coefficients equal to 2 in the inequality being strengthened do not invalidate the last conclusion about its right-hand side).

A star in G is a tree X l = (V X , E X ) with one internal node and l leaves. A positive star is a star such that E X ⊆ E + . Positive stars also give rise to a family of valid inequalities for P G,k . Lemma 3.12 (Positive-star inequality). Let X l = (V X , E X ) be a positive star in G with internal node p such that k ≥ l and, for each j ∈ V X \ {p}, p > j.

For each vertex j ∈ V X \ {p}, consider a set S(j) ⊆ O(j). Additionally, assume that S(i) ∩ S(j) = ∅ for each pair i, j ∈ V X \ {p}. The inequality

� j∈V X \{p}   (k -1)x j p + � i∈S(j) x i j   + kx p p ≤ k, ( 18
)
is valid for P G,k . u j ' p v + + + S(v) S(u) j'

S(j')

Figure 3: A positive star X 3 = (V X , E X ) with internal node p such that k ≥ 3. The leafs of the positive star cannot belong to the solution whenever p is a representative vertex. On the other hand, j � can represent p and in that case any other leaf of the positive star is prevented to be in the feasible solution.

Proof. Due to constraints (2),

� j∈V X \{p} x j p + x p p ≤ 1, which implies � j∈V X \{p} (k -1)x j p + kx p p ≤ k. (19)
Due to constraints (2) and since l ≤ k we have also

� j∈V X \{p} � i∈S(j) x i j ≤ k. ( 20
)
Since X l is a positive star, the left-hand side of (19) equal to k (x p p = 1) implies the left-hand side of ( 20) is equal to zero. Likewise, the left-hand side of [START_REF] Doreian | A partitioning approach to structural balance[END_REF] equal to k -1 (See Figure 3;x j � p = 1, j � ∈ V X \ {p}) implies the left-hand side of (20) less than or equal to one (being one whenever j � ∈ S(j � )).

A Branch-and-cut approach

The branch-and-cut algorithm implemented in this work is composed by four basic components: the initial formulation, the primal heuristic, the cut generation and the branching rule. Next, we describe the main ingredients of this approach, used in the computational experiments described in Section 5. The strategies described here were defined after a number of computational experiments have been performed.

The initial formulation is obtained from the formulation presented in Section 2 by replacing constraints [START_REF] Bahiense | A branch-and-cut algorithm for equitable coloring based on a formulation by representatives[END_REF] for strengthened ones: from Lemma 3.5, inequalities (6) can be replaced by inequalities [START_REF] Barthold | A good submatrix is hard to find[END_REF].

Primal heuristic: An ILS metaheuristic

Iterated Local Search (ILS) [START_REF] Lourenço | Handbook of Metaheuristics, chapter Iterated Local Search[END_REF] is a metaheuristic that aims to improve upon stochastic multi-start search by sampling in a distant neighborhood of candidate solutions, and then applying a local search technique to refine solutions to their local optima. To reach these distant neighborhoods, it explores a sequence of solutions created as perturbations of the current best solution, the result of which is refined using an embedded heuristic. In this context, we have designed and implemented an ILS similar to [START_REF] Figueiredo | The maximum balanced subgraph of a signed graph: applications and solution approaches[END_REF], that executes in sequence three phases: (i) a random/greedy heuristic in a constructive phase, (ii) a Variable Neighborhood Descent (VND) [START_REF] Mladenović | Variable neighborhood search[END_REF] in the local search phase and (iii) perturbation moves as a diversification mechanism. After each successful perturbation move, the ILS metaheuristic returns to phase (ii). In the experiments, the ILS executes 5 multi-start iterations (i.e., the number of times the sequence is re-started), with a stopping criteria of 20 perturbations (i.e., number of perturbations applied without improvement). In the remainder of this section, we describe these three phases.

The input for the metaheuristic is the signed graph G = (V, E, s). We assume that a feasible solution for the problem is defined by a family of k

disjoint sets (V 1 , . . . , V k ) such that V 1 , . . . , V k ⊆ V , � i=1,...,k E[V i ] ⊆ E + and (E[V 1 ∪ . . . ∪ V k ])\( � i=1,...,k E[V i ]) ⊆ E -.
Construction phase. The overall method attempts to find a maximal feasible solution (V 1 , . . . , V k ). The construction phase begins with V i = ∅, for each i = 1, . . . , k, and build these sets in a random/greedy way by adding one new vertex to the solution at a time. Let (V 1 , . . . , V k ) be a feasible solution. We define Cand(

V i ) = {u ∈ V \ ∪ i=1,...,k V i | (V 1 , . . . , V i ∪ {u}, . . . , V k )
is a feasible solution}, the set of vertices that are candidate to be added to set V i . At each iteration, a vertex u ∈ Cand(V i ) (for i = 1, . . . , k) is randomly selected and a new set V � i is reached by inserting vertex u into the set V i . The procedure is repeated until Cand(V i ) = ∅, for all i = 1, . . . , k.

Local search phase. Let N ∝ be an ordered set of predefined neighborhood structures. Whenever one neighborhood fails to improve the current solution, the VND picks the next neighborhood in N ∝ to continue the search. The local search phase halts when no better solution is found in the set of neighborhood structures of the current solution. The ILS is composed by the following 5 ordered neighborhoods:

Hire: inserting a vertex v ∈ (Cand(V 1 ) ∪ . . . ∪ Cand(V k )) into the corre- sponding subset (i.e., V 1 if v ∈ Cand(V 1 ), V 2 if v ∈ Cand(V 2 ), . . .). The process is repeated until (Cand(V 1 ) ∪ . . . ∪ Cand(V k )) = ∅.
Drop(i)-Hire: removing a vertex u from V i (i.e., V i = V i \{u}) and Hire.

Move(i,j)-Hire: moving a vertex u from V i to V j (i.e., V i = V i \{u} and V j = V j ∪ {u}) and Hire. Switch(i,j)-Hire: switching vertices u from V i and v from V j (i.e., V i = (V i \{u}) ∪ {v} and V j = (V j \{v}) ∪ {u}) and Hire. 2Drop(i)-Hire: removing two vertex u 1 and u 2 from V i (i.e., V i = V i \{u 1 , u 2 }) and Hire.

It is important to emphasize that only feasible movements are accomplished. Notice that the neighborhood Hire applied on a solution created by the constructive phase is empty.

Perturbation moves. We perform multiple Drop, Move and Switch movements randomly chosen in such a way that the resulting modification is sufficient to escape from local optima and analyze different regions of the search space.

The multistart ILS is executed before the beginning of the branch-and-cut method: the solution obtained is used as a first primal bound. Additionally, at each integer solution found in the branch-and-cut tree, phases (ii) and (iii) are repeated by using this integer solution as the start solution (with the same stopping criteria described here).

Cut generation

After a linear programming problem has been solved in the branch-and-cut tree, the algorithm checks if the solution is integer feasible. If this is not the case, the cut generation procedure is called and a set of separation routines is executed. A limit of 300 cuts per iteration is set (with a limite of 200 per type of cut).

The cut generation procedure is based on the inequalities described in Section 3, whose separation consists basically of finding cliques, holes, and stars in the graph which maximize a given measure. It follows the scheme and procedures suggested in the branch-and-cut algorithm proposed in [START_REF] Frota | A branch-and-cut algorithm for partition coloring[END_REF] for solving the partition coloring problem.

The separation problem associated with cuts based on clique structures ( 9), ( 10), [START_REF] Campelo | Cliques, holes and the vertex coloring polytope[END_REF] and ( 12) is an NP-Hard problem (maximum clique problem [START_REF] Garey | Computers and intractability[END_REF]). We use GRASP [START_REF] Resende | Search Methodologies[END_REF] heuristics for finding cuts based on maximal clique structures. The GRASP procedure is an iterative method composed of two phases: a construction phase and a local search phase. The construction phase finds an initial solution that may be later improved by the local search phase. Roughly speaking, this heuristic iteratively build an initial solution (clique) in a greedy random way. At each step of the construction phase, one vertex is inserted into the clique with a probability equivalent to its contribution to the cut violation, until a maximal clique is found. Later, the initial solution may be improved by a local search procedure, where the neighborhood is defined as the set of all cliques obtained by exchanging only one vertex in the current solution. Again, the criterion for the acceptance of an improved solution is the contribution to the violation of the cut being separated. For inequalities [START_REF] Campelo | Cliques, holes and the vertex coloring polytope[END_REF], sets S(j), j ∈ K + , are generated in a way that condition (ii) of Lemma 3.7 is satisfied.

Considering a value z i associated to each i ∈ V , odd-hole inequalities

� i∈H z i ≤ �(|H| + t)/2�
can be separated in polynomial time, as described in [START_REF] Padberg | Solving airline crew scheduling problems[END_REF], by solving a set of n shortest path problems in a bipartite graph with vertex sets V and V � (see Section 6.5 from [START_REF] Padberg | Solving airline crew scheduling problems[END_REF] for the graph construction). Following this procedure, inequalities (13) can be separated in polynomial time by: defining z i = x p i /x p p , whenever x p p > 0; redefining the arc set of the bipartite graph (positive edges are associated with arcs linking vertices in a same set V or V � ; negative edges with arcs linking vertices in different sets); and adding 1 to the cost of each arc in the bipartite graph associated with a positive edge in the original graph. In the same way, inequalities [START_REF] Catanzaro | A class representative model for pure parsimony haplotyping[END_REF] can also be separated in polynomial time whenever sets S(j) are fixed. As it is explained in [START_REF] Padberg | Solving airline crew scheduling problems[END_REF], this is a textbook solution that provides at most one odd hole after the solution of each shortest path problem. Then, the Hoffman and Padberg heuristic, described in [START_REF] Padberg | Solving airline crew scheduling problems[END_REF], is used here for finding odd holes ( 13) and [START_REF] Catanzaro | A class representative model for pure parsimony haplotyping[END_REF]. Basically, the method performs a breadthfirst search labeling of the vertices, starting from any root vertex r randomly chosen. A label h v is assigned to each vertex v ∈ V \{r} representing the edge distance between r and v. For any two adjacent vertices v 1 and v 2 with labels h v1 = h v2 ≥ 2, if there exist two vertex-disjoint shortest paths (from v 1 to r and from v 2 to r), then there exists an odd cycle that contains vertices v 1 , v 2 , and r, which can be inspected in order to find violated cuts.

Let us define z i = a j j x j j + � i∈O(j)\{j} x i j . The 1-edge negative cycle inequality (15) can be re-written as

� i∈C z i ≤ |C| -1,
where C is a cycle in G with exact one negative edge. The separation problem associated with this inequality is polynomially solved by finding n shortest paths in an auxiliar directed graph D a = (V a 1 ∪ V a 2 , A a ) defined next. For each i ∈ V , we create a vertice i ∈ V a 1 and a vertice i � ∈ V a 2 . For each positive edge (i, j) ∈ E + , we create four arcs (i, j), (j, i), (i � , j � ), (j � , i � ) ∈ A a while for each negative edge (i, j) ∈ E -, we create two arcs (i, j � ), (j, i � ) ∈ A a . A length d ij = 1z i is defined for each arc (i, j) ∈ A a . The separation problem of 1-edge negative cycle inequalities is solved by looking for each minimum path from i ∈ V a 1 to i' ∈ V a 2 in D a . Notice that, each path from i ∈ V a 1 to i' ∈ V a 2 defines a cycle in G with exactly one negative edge. If such a path has a length smaller than one, a violated inequality [START_REF] Charikara | Clustering with qualitative information[END_REF] has been found, otherwise each such inequality is satisfied. Again, this is a textbook solution and thus, the separation of inequalities ( 15) is incorporated in the Hoffman and Padberg heuristic described above.

The separation problem of the positive-star inequalities ( 18) is NP-Hard. Suppose that we have a fixed positive star X l = (V X , E X ) with internal vertex p. Even the problem of deciding if there exist, for each leaf j ∈ V X \ {p}, a set S(j) ⊆ O(j) that violates constraint ( 18) is an NP-complete problem: it consists in solving the maximum stable set problem [START_REF] Garey | Computers and intractability[END_REF] defined on graph H = (V H , E H ) described next. For each i ∈ S(j) and for each j ∈ V X \ {p}, create a vertex ij in V H . For each pair of vertices ij 1 , ij 2 ∈ V H create an edge (ij 1 , ij 2 ) ∈ E H . Therefore, our separation routine for inequalities [START_REF] Demaine | Correlation clustering in general weighted graphs[END_REF] consists in partially enumerating the positive stars and in using the same GRASP approach from clique cuts to find stable sets in graph H = (V H , E H ). Finally, if no violated inequality is found by all these separation routines, we construct a conflict graph [START_REF] Atamtürk | Conflict graphs in solving integer programming problems[END_REF] representing all the conflicts among variables x ij , (i, j) ∈ A 0 , and run a GRASP procedure looking for cliques in the conflict graph.

At the end of the cut generation phase, if either no violated inequality is found or a limit of (| V | /10) cut generations rounds is reached without an improvement of at least 0.01 in the cost function, the algorithm enters in the branching phase described next.

Branching rule

The standard 0-1 branching rule can be very asymmetrical when representatives formulation is used, producing unbalanced enumerative trees. Our branching rule is based on constraints [START_REF] Abell | Structural balance: a dynamic perspective[END_REF]. The intuition behind this constraint based branching is the generation of more balanced enumerative trees. In the following, let x ∈ � n+m be a fractional solution to the k-MBS problem obtained at a given node. Let p ∈ V be a vertex such that xj p is fractional for some j ∈ V \ p. First, we define a partition S 1 , S 2 for the set O(p) such that � j∈S1 x j p (and � j∈S1 xj p ) is a fractional value. Sets S 1 and S 2 are defined in a way that | � j∈S1 x j p -� j∈S2 x j p | is minimized. We create three branches on the branching tree by adding constraints defined on sets S 1 and S 2 : � j∈S1 x j p = 1, p is in the solution and is represented by a vertex in S 1 , � j∈S2 x j p = 1, p is in the solution and is represented by a vertex in S 2 , � j∈O(p) x j p = 0, p does not belong to the solution.

The branching strategy adopted in our branch-and-cut approach is the following. The standard 0-1 branching rule is used whenever there is a p ∈ V such that xp p is fractional; otherwise the constraint based branching is applied. The branch-and-cut tree is investigated with the best-bound-first strategy.

Computational experiments

In this section, we report the computational experiments carried out with the formulation and methods described in the last sections.

Test problems

In order to test the performance of our branch-and-cut approach, we considered two sets of instances:

• a set of 126 signed networks extracted with the algorithm described in [START_REF] Figueiredo | The maximum balanced subgraph of a signed graph: applications and solution approaches[END_REF] from the UNGA voting records of the separate annual sessions (from 1946 to 2008);

• a set of 180 random instances with a predefined community structure.

Random instances. We generated 180 random signed networks with a predefined community structure inspired in the algorithm used in [START_REF] Girvan | Community structure in social and biological networks[END_REF]. A random signed network is defined as SG(c, n, p -, p + , �) where parameters c, n, p -and p + are used to generate a balanced signed graph: c is the number of communities in the network, n is the number of nodes equally distributed in c communities, p -denotes the probability of negative links appearing between communities, and p + denotes that of positive links appearing within communities. Based only on these parameters, the balanced signed graph generated presents around c × n 2c ( n c -1) × p + positive links internal to the c communities and c(c-1)

2

× n 2c n c × p -negative links among the c communities, with each vertice having around ( n c -1) × p + + ( n c -1) × p + neighbors. The last parameter is used to introduce a deviation from the balanced state: each generated signed link goes through a sign shift with a probability �. The parameters c, n and � take values in the following sets: c ∈ {2, 3, 4, 5}, n ∈ {60, 70, 80} and � ∈ {0.5, 0.1, 0.2}. The parameters p -and p + are fixed, respectively, as 0.3 and 0.05 giving us signed graphs such that each vertice has between 6 and 11 neighbors. A number of five instances is generated for each combination of these parameters.

UNGA instances. The class UNGA is composed of instances derived from the community structure of networks representing voting on resolutions in the United Nations General Assembly, for 63 different sessions. The algorithm proposed in [START_REF] Figueiredo | The maximum balanced subgraph of a signed graph: applications and solution approaches[END_REF] uses two parameters, α and β, to control the decision about the addition of negative and positive edges in the network representing a vote session. Two sets of 63 instances were extracted by setting α = 0.3, β = 0.5 for a first set (Set 3.5), and α = 0.1, β = 0.8 for a second set (Set 1.8). See [START_REF] Figueiredo | The maximum balanced subgraph of a signed graph: applications and solution approaches[END_REF] for details about the extraction of these signed networks. Contrary to our supposition in Section 1, UNGA signed networks have a few parallel edges. However, all the methods and results developed in this paper can be applied to the solution of the k-mbs problem on networks with parallel edges.

Table 4 describes the main characteristics of both sets of UNGA instances. Columns of this table give us the following information: the instance name indexed by the number of the vote session, the number of vertices "n", and, according to the set of instances, the number of positive edges "m + ", the positive density d + = 2m + /n(n -1) of the network, the number of negative edges "m -" and the negative density d -= 2m -/n(n -1) of the network. Given a vote session, the signed network extracted by setting α = 0.3, β = 0.5 is a subgraph of the network extracted by setting α = 0.1, β = 0.8. According to Table 4, a network in set 1.8 has, in average, 23% more positive edges and 80% more negative edges, than the equivalent network in set 3.5.

Methods and computational environment

We implemented and compared three exact methods based on the ILP formulation introduced in this work:

• BC: Branch-and-cut algorithm as described in Section 4.

• BB+01: Branch-and-bound algorithm with formulation described in Section 2, standard 0-1 branching rule and primal bounds given by the ILS metaheuristic described in Section 4.1.

• BB+S1S2: Branch-and-bound algorithm with the formulation described in Section 2, constraint branching rule described in Section 4.3 and primal bounds given by the ILS metaheuristic described in Section 4.1.

All these methods were coded in ANSI C++ by using Xpress-MP Optimizer libraries version 27.01 running on a Intel, 3.6 GHz, equipped with 32 GByte RAM and a Linux operating system. In order to obtain the primal bound α(G -) established in Proposition (2.1), we have used the same GRASP approach implemented for the separation of positive-star inequalities. The CPU time limit is set to 1h for each solution method.

For the sake of space, we do not exhibit in this text all the results obtained in our experiments. Nevertheless, all the instances used and all the results (including additional plots and tables) mentioned here are available in http: //www.ic.uff.br/ ~yuri/files/kmbs.zip.

Numerical Results

Next, we present and discuss the results obtained on Random instances (Section 5.3.1) and on UNGA instances (Section 5.3.2). Besides evaluating the branch-and-cut algorithm described in Section 4, we also investigate the efficiency of the constraint branching rule described in Section 4.3 for the representatives formulation. For that purpose, we try to solve the instances in our test sets by using algorithms BB+01, BB+S1S2 and the branch-and-cut algorithm BC for k ∈ {2, 3, 4, |V |}.

Random instances

BB methods vs BC. Figures 4 and5 present plots comparing the performance obtained by the three exact approaches on the set of 180 random instances, for different values of k and ε. In these profile plots, the performance of each method is described by a curve. For a given value in axis x, the corresponding value in axis y informs the proportion of instances for which the time spent by the exact method was not x-times worst than the time spent by the faster approach. From 4, we can see that the performance of BB+01 method remains the same as k increases while the performance of BB+S1S2 method deteriorates, practically equating to BB+01 method when k = n. From 5, we arrive to the same conclusion as ε increases. Clearly, the BC method obtained the best performance among the three methods. We can also observe that, the performance of BB+01 and BB+S1S2 are closer to the performance of BC method as parameter ε increases, i.e., as the deviation from a balance state increases.

Tables 2 and3 summarize the results obtained with the three exact approaches on the set of random instances. These tables display, respectively, the total number of instances solved to optimality and the average gaps on unsolved instances (i.e. instances not solved to optimality in the time limit). The first multicolumn on these tables gives the value of k and the method executed; the next three multicolumns exhibit the information on instances grouped according to the value of n, C and �. From these tables, we conclude that BB+S1S2 has slightly better performance than BB+01 with respect to the 3 criteria used in the comparison. However, BC has much better performance than both versions of BB (i.e. BB+01 and BB+S1S2) with respect to the 3 criteria used in the comparison: more instances solved in less time and presenting small gaps for unsolved instances. BC was able to solve {115, 97, 109, 100} instances when k ∈ {2, 3, 4, n} against only {19, 1, 0, 2} and {70, 18, 9, 3} from, respectively, BB+01 and BB+S1S2. Moreover, the performance of BC with respect to the number of instances solved to optimality as well as the time spent with these instances is less sensitive to parameters n, � and k, than BB+01 and BB+S1S2.

BC method. Figures 6 and7 explore the results obtained by BC. The graphics in Figure 6 display, for k = 2 and for k = 3: the values of the linear relaxations of the first model ("Init Form LR") and at the root of the search tree ("Root LR"), the value of the upper ("UB") and lower bound ("LB") at the end of the execution, and also the value of the lower bound provided by Proposition 2.1 ("Stable(G-)"). The quality of the results obtained for k ∈ {4, |V |} are very similar to the ones obtained for k = 3. We can verify that the linear relaxation of the representatives formulation is very poor and deteriorates for k ≥ 3. Most part of the improvement in the upper bound (due to the inclusion of valid and facet defining inequalities) is achieved in the root of the search tree.

The box-plot graphics in Figure 7 display, for each value of k, the percentage of time spent by the cut generation phase ("%TimeSep"), the percentage of cuts based on maximal clique structures ("%Cliques), on odd holes and odd anti-holes ("%Hole"), on cycles ("%Cycle"), on stars ("%Star") and on clique inequalities found by the conflict graph separation procedure ("%Conflict"). We can see that the time spent by the separation procedure is never more than 21% of the execution time. Most part of the cuts generated are clique inequalities with percentage values usually superior than 90% with almost all clique cuts generated by the GRASP procedure; the additional conflict graph separation procedure is almost never needed. Motivated by these results, we run the BC method only using the GRASP procedure for separation of clique inequalities in the cut generation phase. These additional results 2 show the performance of the BC deteriorated drastically: around less 60% of instances solved to optimality with worst average gaps for unsolved instances. We also run additional experiments in order to study the relevance of star and clique inequalities, the less found in the separation phase. These additional results 2 show star inequalities (only 1616 cuts on 59/720 problems solved) can make a difference in the time spent to solve some instances but, in average, they do not change neither the gap for unsolved instances nor the number of instances solved. When conflict inequalities are not used, the number of instances not solved to optimality increases. Also, the average gaps and the average dual bounds on the root node slightly deteriorates for k = n. ILS metaheuristic. Even if the goal of this work is not in the development of efficient heuristic approaches, one could ask about the performance of the ILS metaheuristic implemented. Four plots were included in the additional material 2 , comparing ILS results on the set of random instances with lower bounds provide by the BC method. We can conclude that the ILS metaheuristic performs well matching, for many instances, the same primal bound of BC. However, this performance deteriorates as the value of k increases and as the number of vertices decreases: for k = n and n = 60 they are always different except for 5/60 instances.

UNGA instances

BB+01 vs BB+S1S2. Table 5 displays results obtained with BB+01 and BB+S1S2 on UNGA instances. The first multicolumn on this table provides the value of k and the method executed. The next multicolumns exhibit the results obtained on instances 1.8 and 3.5: "P rimal best " presents the average value of the best integer solution found in the search tree; "Gap %" presents the average final percentage gap (between the best solution found and the upper bound) whenever the time limit is reached, "Time" presents the average time (in seconds) spent with the instances solved to optimality, "Nodes" presents the average number of nodes explored in the branch-and-bound tree, while "#Solved" presents the total number of instances solved to optimality by each method. We can see that the new branching rule allows us to solve more instances to optimality and, on average, is less time consuming and explores less nodes in the branch-and-bound tree. The quality of the average gap has been maintained when k ∈ {2, 3, 4} and has been deteriorated when k = n. However, as we will see in the following, this deterioration is explained by the fact that the primal heuristic used does not provide good lower bounds when k = n. Moreover, when k = n, the branchand-bound methods halt with out of memory error for five instances (S57 to S62). BC method. Now, we discuss the performance of the branch-and-cut algorithm BC over the test sets. Tables 6 and7, report, respectively, the results obtained with instances in sets 3.5 and 1.8. In Tables 6 and7, each multicolumn is indexed by k ∈ {2, 3, 4, n} and displays the following information: column "ILS" gives the lower bound obtained with the ILS metaheuristic; column "P rimal best " presents the value of the best integer solution found in the search tree; column "(Gap)/Time" presents either the time (in seconds) spent to solve an instance to optimality or the final percentage gap (in brackets; between the best solution found and the upper bound) whenever the time limit is reached. The second column in these tables displays the primal bound α(G -) obtained. The last line in these tables informs us average values for the information at each column; for column "(Gap)/Time" the average gap is calculated on the set of non-solved instances while the average time is calculated on the set of instances solved to optimality.

The algorithm BC is able to solve more instances to optimality than BB+01 and BB+S1S2; many of them in the root of the branch-and-cut tree. For both sets of instances and for each value of k, except for set 3.5 when k = n, the average gap of the non-solved instances is very small (less than 0.1). One can notice that, the average time to solve instances to optimality increases with k for both set of instances. Results on these tables indicate that the k-MBS problem becomes numerically more difficult as k increases and that instances in set 1.8 are slightly easier to be solved. Regarding the lower bounds at these tables, the quality of the lower bound provided by the ILS metaheuristic is slightly better than the one provided by α(G -) for k ∈ {2, 3, 4}. However, the lower bound provided by the ILS deteriorates as k increases and, for k = n, it becomes worse when compared with α(G -).

Additional tables2 exhibit information about the cut generation phase in the branch-and-cut method. We conclude that inequalities associated with cliques and 1-edge inequalities were fundamental for the solution of UNGA instances. Inequalities associated with holes and positive stars play a secondary role in the method but they are important for the solution of some instances. No inequality associated with holes was generated for instances in set 1.8 and this is explained by the fact that these instances presents higher density than instances 3.5. The average time spent in the separation phase is approximately 40% of the total time for instances 3.5 and varies, with k, from 51% to 70% for instances 1.8.

Finally, Table 8 displays a comparison of the three exact approaches implemented. On these tables, each multicolumn is indexed by ∈ {2, 3, 4, n} and by the type of method, "BB" or "BC" with the set of columns displaying the following information: "R r " is the value of the linear relaxation at the root of the search tree; "#01" is the number of instances solved to optimality by BB+01; "#S1S2" is the number of instances solved to optimality by BB+S1S2; "#BC" is the number of instances solved to optimality by BC. Each line of this table displays these information for a set of UNGA instances grouped according to the number of vertices, i.e., countries in the vote section. The last line of Table 8 exhibits either the average (for R r ) or the sum (for "#01", "#S1S2", "#BC") of the information displayed at each column. Clearly, the performance of BC algorithm attests to the efficiency of the cuts and strategies proposed in Sections 3 and 4: not only the value of the linear relaxation at the root of the search three is better, but also more instances are solved to optimality.

Interpretation for the 55 th and 59 th Sessions. Coming back to Tables 6 and7, we verify that for the majority of instances (UN sessions), v(G, 3) = v(G, k), for each 4 ≤ k ≤ n. We also notice a small distance from v(G, 2) and v(G, 3) except for instances 3.5 associated with sessions from the 55 th Session (2000-2001) to the 59 th Session (2004-2005). We do not present a complete interpretation of these results. Such a task would imply considerations out of the scope of the paper, e.g. parameters and methods used for the extraction of the vote network, the analyses of networks associated with subjects discussed and voted in a given session (See [START_REF] Mendonça | Relevance of negative links in graph partitioning: A case study using votes from the european parliament[END_REF]). However a brief analysis of the results obtained with the instance 3.5 associated with the 55 th Session, highlight the relevance of solving the k-MBS problem for different values of k. When comparing the optimal solution obtained when k = 2 (170 countries) with the one obtained when k = 3 (176 countries) (see Figure 8), we see that a set of countries leave the solution to give place to other ones:

• Leaving countries: Yugoslavia, St. Vincent and the Grenadines, Suriname and Gambia.

• Entering countries: Guinea-Bissau, Niger, Liberia, Central African Republic, Seychelles, Iraq, Jamaica, Sierra Leona, Togo and Angola.

Six countries, Guinea-Bissau, Niger, Liberia, Central African Republic, Seychelles, and Iraq, together with Mauritania compose the new group in the solution with k = 3 while the other ones (among them Sierra Leona, Togo and Angola) joins the huge group of countries. The complete list of resolutions discussed in the 55 th Session can be found in [START_REF]Resolutions and Decisions from the 55 th Session[END_REF] which includes 12 resolutions related with Africa subjects. The list [START_REF]The Notable General Assembly Resolutions[END_REF] of the notable general assembly resolutions points Resolution A/RES/55/56 [START_REF]United Nations General Assembly Session 55 Resolution 56[END_REF] from the 55 th Session as a notable one. This resolution introduces the Kimberley Process Certification Scheme [START_REF]Kimberley Process Certification Scheme[END_REF], a process to certify the origin of rough diamonds from sources that are conflict-free. The solution obtained when k = 3 reflects the conflict around some resolutions which cannot be detected in the solution obtained with k = 2.

Conclusion

Signed graphs appear as an ideal discrete structure to represent relationships in collaborative vs. conflicting environments. Once the context of the application is defined, an optimal solution of the k-MBS problem can help us to gain a better understanding of the dynamics of this environment. To the best of our knowledge, the k-MBS problem has never been efficiently solved in the literature before. In this work, we introduced a representatives formulation for the k-MBS problem. With the purpose to develop an exact approach to its solution, we investigated some classes of valid inequalities for the associated polytope P (G, k). We have also proposed to use a constraint branching strategy based on a set of inequalities of the formulation. Extensive computational experiments were carried out over a set of random instances (with community structure) as well as over a set of instances representing voting on resolutions in the United Nations General Assembly on 63 sessions. The numerical results reported in Section 5, show the strength of some families of inequalities introduced and attests the efficiency of the branching strategy proposed. This later can be extended to other exact methods based on representatives formulation. Our current research focus on the evaluation of the optimal solution of the k-MBS problem as a criteria to measure the structural balance on real-world signed networks. In order to Table 4: Description of UNGA instances extracted with the algorithm described in [START_REF] Figueiredo | The maximum balanced subgraph of a signed graph: applications and solution approaches[END_REF] by setting α = 0.3, β = 0.5 and α = 0.1, β = 0.8.

Figure 1 :

 1 Figure 1: (a) A balanced signed graph: W = {1, 2, 6} and V \ W = {3, 4, 5}. (b) A k-balanced signed graph for any k ∈ {3, 4, 5, 6}. Sets N 1 = {1, 2}, N 2 = {3, 4, 5} and N 3 = {6} define a 3-partition of this graph. (c) A non-clusterable signed graph.

Figure 2 :

 2 Figure 2: A cycle C with exactly one negative edge: at most |C| -1 vertices can be simultaneously in a feasible solution. If vertex p is a representative one, vertices p -and p + are prevented to be in the solution.

Figure 4 :

 4 Figure 4: Performance profile plots comparing the three methods on random instances, for each k ∈ {2, 3, n}.

Figure 5 :

 5 Figure 5: Performance profile plots comparing the three methods on random instances, for each ε ∈ {5, 10, 20}.

Figure 6 :

 6 Figure 6: Linear relaxations and bounds obtained by BC on random instances when k ∈ {2, 3}.

Figure 7 :

 7 Figure 7: Percentage time and percentage of cuts per family obtained by BC on random instances when k ∈ {2, 3, 4, |V |}.

Figure 8 :

 8 Figure 8: Optimal solutions obtained for instance 3.5 associated with the 55 th Session when k = 2 (left) and k = 3 (right).

Table 2 :

 2 Number of random instances solved to optimality by each solution method.

				n			C				ε
	k	Method	60	70	80	2	3	4	5	5	10	20
	2	BB+01	18	1	0	6	4	5	4	16	3	0
		BB+S1S2	44	21	5	22	17	16	15	40	24	6
		BC	60	45	10	29	26	30	30	47	38	30
	3	BB+01	1	0	0	1	0	0	0	1	0	0
		BB+S1S2	16	2	0	6	6	3	3	17	1	0
		BC	49	36	12	16	24	27	30	47	32	18
	4	BB+01	0	0	0	0	0	0	0	0	0	0
		BB+S1S2	7	2	0	3	4	2	1	10	0	0
		BC	50	39	20	16	24	32	37	55	35	19
	n	BB+01	2	0	0	2	0	0	0	2	0	0
		BB+S1S2	3	0	0	3	0	0	0	3	0	0
		BC	47	32	21	20	22	26	32	58	32	10

Table 3 :

 3 Average gaps on random instances not solved to optimality by each solution method.

				n			C				ε
	k	Method	60	70	80	2	3	4	5	5	10	20
	2	BB+01	0.12	0.21	0.33	0.29	0.25	0.21	0.17	0.16	0.21	0.31
		BB+S1S2	0.06	0.13	0.24	0.21	0.18	0.17	0.15	0.11	0.15	0.21
		BC	-	0.08	0.09	0.11	0.09	0.09	0.07	0.07	0.06	0.13
	3	BB+01	0.21	0.30	0.40	0.42	0.31	0.27	0.23	0.18	0.29	0.45
		BB+S1S2	0.15	0.21	0.33	0.31	0.25	0.21	0.18	0.13	0.20	0.35
		BC	0.07	0.10	0.18	0.17	0.18	0.11	0.05	0.03	0.09	0.20
	4	BB+01	0.22	0.30	0.38	0.43	0.32	0.25	0.22	0.16	0.29	0.46
		BB+S1S2	0.19	0.26	0.34	0.35	0.29	0.24	0.20	0.13	0.24	0.40
		BC	0.09	0.11	0.19	0.17	0.18	0.13	0.04	0.04	0.10	0.20
	n	BB+01	0.36	0.52	0.74	0.79	0.62	0.43	0.33	0.44	0.54	0.64
		BB+S1S2	0.41	0.51	0.74	0.84	0.61	0.44	0.35	0.42	0.59	0.66
		BC	0.09	0.23	0.44	0.49	0.34	0.18	0.11	0.33	0.32	0.31
	be able to treat larger signed networks, efficient heuristic methods for the k-
	MBS problem must be developped. The ILS heuristic presented in this work
	performed quite well but for a subset of instances. Studying problem structures
	for which heuristic solutions are far from optimal solutions can drive us in the
	developpement of better heuristic strategies.

Table 5 :

 5 Branch-and-bound results on UNGA instances.

	1.8	3.5

Table 6 :

 6 Branch-and-cut results for instances 3.5

		(Gap %)/Time	222.33	(0.02)	(0.18)	(0.09)	(0.67)	2399.80	786.05	(0.46)	(2.42)	(1.08)	(1.62)	(1.92)	596.96	242.03	(3.46)	1528.74	(0.50)	3065.55	485.86	644.23	1247.82	(3.16)	582.12	1460.32	1760.66	617.65	3186.73	618.80	376.22	1182.57	730.84	1020.79	1219.35	2448.80	1035.23	1234.35	(0.49)	1500.57	(2.27)	1526.39	1913.65	(2.47)	1815.05	2058.14	1056.92	1281.66	2724.05	3034.64	(2.52)	1709.56	(0.37)/1059.15
	k=n	P rimal best		51	65	68	48	93	106	67	31	51	42	38		130	28	126	82	122	134	139	135	32	146	138	142	141	128	152	157	150	156	154	159	169	176	175	116	179	49	169	171	51	181	183	187	187	182	182	52	186	106.90
		ILS	47	51	65	68	48	92	69	67	31	51	42	38		26	28	58	82	7	132	63	79	32	50	80	109	98	61	131	138	133	123	119	111	42	70	112	116	166	49	89	39	51	57	69	60	54	38	22	52	180	67.80
		(Gap %)/Time	12.87	(0.16)	587.40	(0.09)	(0.04)	3357.31	534.64	(0.43)	(0.23)	(0.09)	(0.10)	(0.07)		126.46	(0.02)	971.99	(0.01)	1746.33	331.81	455.68	789.71	(0.01)	358.68	1903.58	1237.79	556.62	3060.66	273.88	117.20	1187.99	127.84	213.87	724.02	1401.89	1222.97	2294.01	(0.02)	551.21	(0.03)	822.37	1509.61	1878.74	1109.64	1840.63	273.83	259.09	743.23	1561.95	3463.93	418.25	(0.02)/815.77
	k=4	P rimal best	47	45	76	68	77	93	106	69	86	99	102	105		130	125	126		122	134	139	135	132	146	138	142	141	128	152	157	150	156	154	159	169	176	175	170	179	158	169	171	177	181	183	187	187	182	182	183	186	121.80
		ILS	47	45	76	68	77	92	106	69	86	99	102	105		130	125	126		122	134	139	135	132	146	121	142	127	117	152	157	133	156	154	159	169	173	175	170	179	158	169	171	176	181	183	187	187	182	182	183	186	120.70
		(Gap %)/Time	17.55	(0.04)	1982.77	(0.11)	(0.04)	1892.31	432.85	(0.09)	(0.23)	(0.16)	(0.30)	(0.06)	1740.94	79.10	3284.03	882.87		2420.78	314.30	545.66	950.92	(0.02)	508.52	1462.41	670.84	591.24	2839.25	293.31	129.25	1351.98	117.77	116.91	377.01	1199.07	1005.71	2801.90	(0.03)	653.50	(0.01)	438.83	827.02	1720.09	1406.62	1176.36	373.89	293.17	956.36	1508.12	684.31	349.01	(0.01)/832.64
	k=3	P rimal best	47	50	76	66	77	93	106	89	86	93	86	105	122	130	125	126		122	134	139	135	132	146	138	142	141	128	152	157	150	156	154	159	169	176	175	167	179	158	169	171	176	181	183	187	187	182	182	183	186	121.74
		ILS	47	50	70	66	77	93	71	89	86	93	86	105	122	130	125	126		122	134	139	135	132	129	138	142	127	128	152	157	133	156	154	159	169	173	174	167	179	158	169	171	174	181	65	187	187	73	182	82	186	114.85
		(Gap %)/Time	19.53	(0.02)	784.33	(0.12)	(0.05)	1007.61	169.41	2804.21	(0.22)	(0.04)	(0.29)	(0.01)	456.03	76.16	535.52	332.23		893.07	251.62	213.68	418.84	934.63	126.01	812.95	564.52	180.12	3188.80	156.23	60.81	351.38	100.36	99.10	188.29	317.52	258.88	147.22	1081.21	123.24	2798.31	277.15	230.90	1082.71	236.36	320.46	274.42	181.74	247.19	504.81	520.88	127.82	(0.01)/449.13
	k=2	P rimal best	46	51	76	68	76	93	106	95	85	98	82	103	121	130	124	126		122	133	139	135	132	146	138	141	141	128	152	157	150	156	154	159	169	176	175	170	179	157	167	170	170	178	180	184	184	181	181	182	185	121.35
		ILS	46	51	76	68	76	93	65	94	85	98	82	103	121	130	124	126		122	133	40	135	132	146	138	141	141	115	152	157	150	156	154	159	169	171	175	167	179	157	167	170	168	178	180	64	184	181	181	182	185	116.74
	α(G -)		40	51	75	64	72	92	100	91	89	93	95	98	117	129	120	124	118	120	131	135	133	131	142	136	136	136	127	149	156	149	153	149	158	158	162	160	152	166	155	165	159	159	151	167	174	180	171	177	179	177	116.62
	Name		S01	S14	S15	S16	S17	S18	S20	S21	S22	S23	S24	S25	S26	S27	S28	S29	S30	S31	S32	S33	S34	S35	S36	S37	S38	S39	S40	S41	S42	S43	S44	S45	S46	S47	S48	S49	S50	S51	S52	S53	S54	S55	S56	S57	S58	S59	S60	S61	S62	S63	Avg.

Table 7 :

 7 Branch-and-cut results for instances 1.8

		(Gap %)/Time	76.91	65.00	64.51	76.59	72.81	159.89	136.08	134.62		803.52	1606.58	1693.82	1193.85	1417.15	400.65	376.45	325.67	1149.25	792.55	3102.09	2745.67	1546.58	2026.43	986.10	3185.62	2620.97	2129.75	1959.83	2511.84	3193.99	3382.21	2536.97	3232.25	2474.71	2474.71	(1.24)	1879.87	(0.04)/1235.12
	k=n	P rimal best	35	38	38	31	40	31	38	39		124	122	125	129	120	144	147	144	144	146	138	146	158	164	154	161	142	151	154	163	162	158	165	160	163	166	69	173	103.16
		ILS	35	38	38	31	40	30	33	34	38	124	68	125	96	115	144	147	144	138	142	122	37	95	45	154	73	105	115	16	88	56	117	131	41	155	105	69	171	77.62
		(Gap %)/Time	10.11	13.40	18.58	17.35	26.54	33.63	17.01	15.19	14.50	1393.92	964.55	1581.64	636.44	822.33	202.87	188.07	514.97	443.30	415.06	2476.26	1940.18	775.90	1596.74	1290.59	1751.55	1236.85	1498.61	1187.51	1301.74	1096.91	2456.40	1559.18	2235.95	2411.39	1422.29	(0.01)	415.27	(0.00)/860.97
	k=4	P rimal best	35	38	38	31	40	31	38	39	38	124	122	125	129	120	144	147	144	144	146	138	146	158	164	154	161	142	151	154	163	162	158	165	160	163	166	153	173	105.41
		ILS	35	38	38	31	40	31	38	39	38	124	122	125	129	120	144	147	144	144	146	138	146	158	163	154	161	142	151	154	163	162	158	131	133	163	166	153	173	103.98
		(Gap %)/Time	12.65	10.04	12.73	14.79	12.43	40.42	18.10	12.17	11.39	1124.11	1185.10	1659.06	979.17	535.27	281.54	182.38	382.44	636.19	307.03	2914.64	2080.97	600.37	1232.74	1336.27	2027.71	1551.90	1414.39	1182.66	602.38	1277.85	3130.77	862.89	2101.60	1831.65	970.84	(0.01)	660.92	(0.00)/821.55
	k=3	P rimal best	35	38	38	31	40	31	38	39	38	124	122	125	129	120	144	147	144	144	146	138	146	158	164	154	161	142	151	154	163	162	158	165	160	163	166	154	173	105.41
		ILS	35	38	38	31	40	31	38	39	38	124	122	125	129	120	144	147	144	144	146	138	146	158	163	154	161	142	151	154	163	162	155	165	160	163	166	154	173	105.20
		(Gap %)/Time	7.18	3.20	18.78	12.39	16.29	32.91	17.08	8.34	7.59	641.88	802.43	989.66	310.00	637.04	361.26	167.68	382.48	357.76	269.73	2026.44	1376.79	404.40	547.51	527.80	1004.81	1321.96	1176.38	679.77	693.50	522.46	2140.23	1101.29	2248.27	1746.40	1143.07	(0.01)	269.71	(0.00)/672.22
	k=2	P rimal best	34	37	38	31	40	30	38	39	38	124	122	125	129	120	144	147	144	144	146	138	146	158	164	154	161	142	151	154	157	162	157	165	160	163	165	153	172	105.09
		ILS	34	37	38	31	40	30	38	39	38	124	122	125	129	120	144	147	144	144	146	138	146	158	163	154	161	142	151	143	157	162	157	132	160	163	165	153	172	103.75
	α(G -)		31	34	34	31	36	29	38	38	38	122	121	123	126	120	143	146	142	143	141	137	137	148	150	138	150	139	149	144	149	137	147	157	158	155	162	150	165	101.5
	Name		S01	S02	S03	S04	S05	S06	S07	S08	S09	S36	S37	S38	S39	S40	S41	S42	S43	S44	S45	S46	S47	S48	S49	S50	S51	S52	S53	S54	S55	S56	S57	S58	S59	S60	S61	S62	S63	Avg.

Table 8 :

 8 Comparison of results obtained on UNGA instances by each solution method.

Notice that, in[START_REF] Davis | Clustering and structural balance in graphs[END_REF][START_REF] Doreian | A partitioning approach to structural balance[END_REF], the definition of a k-balanced signed graph is slightly different since k is not considered to be a fixed parameter.

Available in http://www.ic.uff.br/ ~yuri/files/kmbs.zip.

Acknowledgements

This research benefited from the support of the "FMJH Program Gaspard Monge in optimization and operation research" (Project 2015-2842H), and from the support to this program from EDF. The authors would like to thank the anonymous reviewers for their valuable comments and suggestions to improve the quality of the paper.


Anne-Lyse Minard

Christian Raymond

Vincent Claveau

IRISA at SMM4H 2018: Neural Network and Bagging for Tweet Classification

This paper describes the systems developed by IRISA to participate to the four tasks of the SMM4H 2018 challenge. For these tweet classification tasks, we adopt a common approach based on recurrent neural networks (BiLSTM). Our main contributions are the use of certain features, the use of Bagging in order to deal with unbalanced datasets, and on the automatic selection of difficult examples. These techniques allow us to reach 91.4, 46.5, 47.8, 85.0 as F1-scores for Tasks 1 to 4.

Introduction

IRISA has participated in the four tasks of the SMM4H challenge [START_REF] Weissenbacher | Overview of the Third Social Media Mining for Health (SMM4H) Shared Tasks at EMNLP 2018[END_REF]. Yet, we have focused on Task 2 and 3, which are the most challenging ones, in particular because they have unbalanced data. Moreover, for Task 2, the three classes have very fuzzy boundaries, which makes some tweets difficult to classify even for humans. Our main contribution is to rely on Bagging (Bootstrap Aggregating) in order to deal with this problem of unbalanced data.

Methods

RNN: BiLSTM

For the four tasks, we have developed classifiers based on recurrent neural networks which consists in one Bidirectional LSTM layer [START_REF] Graves | Speech recognition with deep recurrent neural networks[END_REF] and a dense layer with a softmax activation as hidden layer. The input layer takes a representation of a tweet which consists in the word embeddings of each token and, depending of the task, a one-hot vector for each token or a one-hot vector for some medical terms in the tweet. Metamap Lite [START_REF] Demner-Fushman | Metamap lite: an evaluation of a new java implementation of metamap[END_REF] is used to extract specific medical terms from the tweets. We restrict the number of semantic types according to the task: for Task 1, we have selected only terms related to drugs or substances; for Task 2, only to procedural terms; and for Task 3, we have selected both terms related to drugs and terms related to symptoms. For Task 1 and Task 2, we observe an improvement while using medical terms, whereas for Task 4 the use of metamap has no influence on the results. We use the word embeddings distributed by [START_REF] Grave | Learning Word Vectors for 157 Languages[END_REF]. They have been trained with FastText [START_REF] Bojanowski | Enriching Word Vectors with Subword Information[END_REF].

Bonzaiboost

During the development phase, we have used BONZAIBOOST, an implementation of the boosting algorithm adaboost.MH [START_REF] Laurent | Boosting bonsai trees for efficient features combination : application to speaker role identification[END_REF] on decision trees. The results obtained are a bit lower than those of recurrent neural network methods. Yet, the experiments done with BONZAI-BOOST allowed us to extract the most discriminating words, to choose the better features for the RNN, and to select the difficult examples (see Section 2.4). For Task 1, the important words found are drug names, such as xanax. For Task 2, the useful words are verbs indicating the action of taking a drug, the results of its intake, or the fact that a drug is needed (e.g. took, need). For Task 3, the discriminating words include symptom names (e.g. dizzy, headache). Finally for Task 4, no relevant discriminating words have been found. These findings help us to determine the semantic types of the medical terms to be used in the feature set.

Bagging

Bagging [START_REF] Breiman | Bagging predictors[END_REF] 2 and 3, for Task 2 an equal number of instances of each class are chosen (2000 examples) and, for Task 3, every positive example is selected, and 20% of the negative ones are randomly selected. Bagging seems to improve the results, especially because it allows the RNN to deal with more balanced datasets. For Task 1 and Task 4, bagging does not improve the results; this may be due to the results already being high (F1 > 0.90), and for Task 1, to the data being already balanced.

Automatic cleaning of the datasets

Every manually annotated dataset may contain annotation errors or uncertain annotation due to the difficulty of the task. In order to improve the classification performance of our system, we have tried to clean up the training data by removing potential errors. We have considered that the tweets to be removed are those incorrectly classified although it was part of the training data used to train the model. More precisely, we proceed as follows: a model is trained on the complete training dataset; this model is then applied to predict the class of every example of this training dataset; the misclassified tweets are finally removed from the data; the cleaned dataset is then used to train the final model. We have removed 234, 183 and 250 examples respectively for Tasks 1, 3 and 4. For the Task 2, we have not observed improvement while removing difficult examples.

Evaluation

For each experiment the data is split into train set (80%) and dev set (20%). Evaluation is performed with a 5-fold cross validation, except when us-ing bagging techniques. For the experiments with bagging, we train 20 models (with more models we do not get any improvement). The description of all the submitted runs and the obtained results on the training data are given in Table 1.

The official results are given in Table 2. The use of bagging techniques enables us to improve from 1.9 to 3.9 points the performance of our systems for Task 2 and Task 3. The automatic cleaning of the datasets is also a reason for a light improvement for Task 1 and Task 4.

Table 1 :

 1 is a technique that consists in combining the prediction of different learners, where each "learner" uses only a sample of the original training set. We learn several models, with, for each, a subset of the training dataset, different training parameters (number of epochs, number of hidden layers...) and different feature sets. To deal with unbalanced datasets in Tasks Description of the submitted runs and results obtained on the training dataset.

			Model	Input	Data
		BiLSTM	Bagging	epochs	metamap	tokens	cleaned	F1
		R1 x		3	x			90.2
	T1	R2 x		3	x		x	90.0
		R3 x		3		x		88.1
		R1 x		3	x			67.9
	T2	R2	x	3	x	x		67.7
		R3	x	1 to 5 x	x		68.1
		R1 x		3		x	x	50.1
	T3	R2	x	3		x		52.0
		R3	x	1 to 7 x	x		46.6
		R1 x		3				87.7
	T4	R2 x		3			x	92.2
		R3 x		3	x			87.2

Table 2 :

 2 Final results in terms of F1-score.

	Task Run 1 Run 2 Run 3
	T1	91.1	91.4	90.6
	T2	43.6	45.5	46.5
	T3	43.9	46.2	47.8
	T4	84.4	85.0	82.4