Patrick Saint-Dizier
email: stdizier@irit.fr

Argument Mining: the Bottleneck of Knowledge and Language Resources

Keywords: Argument mining, Knowledge representation, Generative lexicon

Given a controversial issue, argument mining from natural language texts (news papers, and any form of text on the Internet) is extremely challenging: domain knowledge is often required together with appropriate forms of inferences to identify arguments. This contribution explores the types of knowledge that are required and how they can be paired with reasoning schemes, language processing and language resources to accurately mine arguments. We show via corpus analysis that the Generative Lexicon, enhanced in different manners and viewed as both a lexicon and a domain knowledge representation, is a relevant approach. In this paper, corpus annotation for argument mining is first developed, then we show how the generative lexicon approach must be adapted and how it can be paired with language processing patterns to extract and specify the nature of arguments. Our approach to argument mining is thus knowledge driven

Aims and Challenges of Argument Mining

One of the main goals of argumentation mining is, given a controversial issue, to identify in various texts the arguments for or against that issue. These related arguments act as supports or attacks of the issue, depending on their orientation. Arguments may also attack or support the other arguments which support or attack that controversial issue in order to cancel out or reinforce their impact. An argumentation is represented by a graph of supports and attacks.

Arguments are difficult to identify and to characterize, in particular when they are not adjacent to the controversial issue, possibly not in the same text. Arguments are often standard natural language statements which get the status of arguments because of the specific relations they have with a controversial issue. For example, the statement from the Indian Times: (a) we now see long lines of young girls with school bags along the roads could be just factual, but given the controversial issue: (b) the situation of women has improved in India, then, statement (a) becomes an argument supporting (b), which is then interpreted as a controversial issue which can then be supported or attacked. Except in specific contexts, and for certain forms of arguments (e.g. warnings, threats, advice, requirements), most arguments do not have any specific linguistic mark that would allow to identify their relation to a controversial issue. Furthermore, it is difficult to identify whether a statement is a support or an attack of a controversial issue, and what it precisely attacks or supports. In the above example, school bags means education: it is a means to improve women's condition because it leads to jobs and more independence. It does not talk about anything else concerning women's conditions. Relating a controversial issue with arguments requires knowledge, lexical semantics data, and appropriate inferential patterns. It is therefore much more complex in terms of semantics and reasoning than e.g. standard opinion analysis based on evaluative expressions analysis. Argument mining is an emerging research area with new challenges that require the combination of linguistic analysis and language processing with artificial intelligence. Argument mining is at the moment applied mainly to written texts, e.g. (Mochales Palau et ali.., 2009), (Kirschner et ali., 2015), opinion analysis, e.g. [START_REF] Villalba | Some Facets of Argument Mining for Opinion Analysis[END_REF] dialogue analysis, e.g. (Budzynska et ali., 2014), (Swanson et ali., 2015). The analysis of argument mining techniques from annotated structures in analyzed in e.g. [START_REF] Peldszus | From argument diagrams to argumentation mining in texts: a survey[END_REF]. Annotated corpora are being made available, such as the AIFDB dialog corpora at Dundee university or corpora developed by [START_REF] Walker | A Corpus for Research on Deliberation and Debate[END_REF]. These corpora are very useful to identify argumentative discourse units (ADUs), linguistic cues, [START_REF] Nguyen | Extracting Argument and Domain Words for Identifying Argument Components in Texts[END_REF], and argumentation strategies, in a more concrete way than abstract argumentation schemes, as shown in e.g. [START_REF] Feng | Classifying arguments by scheme[END_REF]. Finally, reasoning aspects related to argumentation analysis are developed in e.g. [START_REF] Fiedler | Argumentation within deductive reasoning[END_REF] and [START_REF] Winterstein | What but-sentences argue for: An argumentative analysis of but[END_REF] from a formal semantics perspective.

The goal of argument mining is, given a controversial issue, to identify in a set of texts of various origins, statements which can be interpreted as supports or attacks to that issue. In opinion analysis, the benefits are not only to identify the customer satisfaction level, but also to characterize why customers are happy or unhappy. Abstracting over arguments allows to construct summaries and to define customer value systems (e.g. low fares are preferred to localization or quality of welcome for some categories of hotel customers). Argument mining from full natural language texts is extremely challenging: given a controversial issue, the identification of the relations between arguments and that issue is often more complex than just the bipolar support or attack view. For example, given the issue Vaccination against Ebola is necessary and the argument: There are almost no cases of Ebola in Europe: is this argument a support, an attack or something else ? Identifying the conceptual link between a controversial issue and an argument is of much importance to have a clear analysis of the role of an argument. In this example, the attack comes from the fact that there is no contamination in Europe. Our approach to argument mining is therefore knowledge driven.

Research Questions, Hypothesis and Foundations

This paper addresses the following challenges:

• The identification of the forms of knowledge and inferences required to identify arguments in texts,

• The identification of the linguistic cues that contribute to identify arguments in texts, in conjunction with knowledge and inference,

• The definition of a model that accommodates both knowledge and linguistic data,

• The identification of relatedness factors between a controversial issue and a statement, in particular which aspects or facets of the issue are attacked or supported,

• The identification of the argumentative relations between an issue and an argument: supports, attacks, various types of causality, concessions and supports, strength of the argument and its persuasion effect(s),

Our approach is organized as follows:

(1) The words in the controversial issue originate lexical and conceptual knowledge structures, where the main concepts in the issue form the root of the structure, (2) Language patterns dedicated to argument analysis are associated to these knowledge structures, similarly to the procedural attachment techniques developed for frames and scripts. Argument mining is thus knowledge driven, (3) These patterns allow to identify the kernel of the argument. They are associated with discourse analysis rules that recognize additional information frequently associated with these kernels that elaborate, justify or constrain them.

(4) Given our observations (reported below) the Qualia structure of the Generative lexicon (GL) is investigated as an appropriate formalism to represent both conceptual and lexical knowledge for argument mining. We show that the Qualia structure needs to be structured and improved for this task. A controversial issue then defines a network of Qualias, connected via their various roles.

(5) To each concept in the Qualia are associated lexical terms and language patterns designed to identify arguments.

(6) The features of an argument (polarity, strength, facets of the issue concerned, etc.) are computed compositionally from Qualia structures and dedicated inferences.

In this paper, to motivate this approach, we first develop a corpus analysis to characterize these challenges, outlining the types of knowledge required to extract and characterize arguments. We then briefly show how the Qualia structure can be enhanced for the purpose of argument mining. Finally we show via examples how language patterns are associated with Qualia to extract arguments. This paper is essentially a linguistic and knowledge modeling contribution. An important point observed in our corpora is that argument kernels are not so diverse for a given issue. The diversity and the power of arguments comes from the discourse structures they are associated with, that elaborate, justify, illustrate or constrain them. These structures are identified using our TextCoop discourse analysis platform.

Corpus Construction and Analysis

Corpus construction

To explore and characterize the forms of knowledge that are required to develop argument mining in texts, we constructed and annotated four corpora based on four independent controversial issues. These corpora are relatively small, they are designed to explore the problem, and to elaborate a model, not to design a comprehensive argument mining system. The text fragments which are investigated are extracts from various sources where these issues are discussed, in particular: newspaper articles and blogs from associations. These are documents accessible to a large public, with no professional consideration. Language is essentially French (glosses are given is paper); some English texts have also been analyzed. This corpus analysis shows that although texts are often rich in arguments, their diversity is not very large, since e.g. a maximum of 50 different arguments have been found for issue (1) and much less for the others. There is quite a high overlap rate, which is not very informative since authors frequently copy each others.

Annotation parameters

Arguments seldom come in isolation, as independent statements. They are often embedded into a context that indicates e.g. circumstances, restrictions, concessions, comparisons, purposes, and various forms of elaborations. In terms of language realization, arguments and their related context may be included into a single sentence via coordination or subordination or may be realized as separate sentences. In both cases, the relations between these different elements are realized by means of conjunctions, connectors, various forms of references and punctuation. We call such a form an argument compound [START_REF] Saint-Dizier | A Discourse Grammar for Processing Arguments in Context, COMMA 2014[END_REF]. The claim, behind this term, is that the elements in a compound form a single, possibly complex, unit, which must be considered as a whole from a conceptual and argumentative point of view.

An argument kernel and its context (the argument compound) are tagged between XML <argument> tags with attributes. In the compound, the argument kernel is tagged <main arg>. Discourse structures within the compound are annotated using the tags defined in our TextCoop platform [START_REF] Saint-Dizier | Processing natural language arguments with the TextCoop platform[END_REF]. Annotations are relatively informal at this exploratory stage. Attributes in the main argument tag characterize the knowledge dimensions that are required for humans to analyze the arguments, these include:

1. the text span involved in the compound, which ranges from a few words to a paragraph. Arguments are numbered for referencing aspects, 2. the polarity of the argument w.r.t. the issue has one of the following values: support, concession (argumentative concession is a weak support), contrast (a weak attack), and attack. There is a kind of continuum between these values, and it is sometimes a matter of context and personal evaluation to make a decision, 3. the conceptual relation with the issue, which informally describes why it is an attack or a support, 4. the knowledge involved, when appropriate, to identify the argument: list of the main concepts used, informally described, 5. the strength of the argument, which is based on the linguistic marks in the text fragment. Some justifications can be included. In our view, persuasion is differentiated from strength: persuasion is a pragmatic notion that depends on context more than on pure linguistic marks.

An argument for issue (1) is the following: The <main arg> tag identifies the argument kernel, that is modified by discourse structures realized either before of after the kernel. This simple example shows the type of text that is annotated and the nature of the concepts which are at stake. This example shows that the facet of the concept vaccine that is invoked is not the necessity of the vaccine but the need of some care (while other arguments, in contrast, develop costs, political or ethical aspects). At this stage, the way these concepts are linguistically realized is not tagged. This is developed in section 5, where our method for argument mining driven by knowledge is developed.

<argument

Main characteristics of the corpus

From our manual analysis, the following argument polarities for the four controversial issues above are observed: These figures, although limited to a small experiment, show that for about 78% of the arguments found related to one of the 4 issues investigated, some form of knowledge is involved to establish an argumentative relation between a statement and an issue. An important result is that the number of concepts involved is not very large: 122 concepts for 95 arguments over 4 domains. Even if the notion of concept remains somewhat vague, these results are nevertheless interesting. The number of arguments found per controversial issue in our experiment shows a relatively good coverage of the domain. This is an important observation for the scalability issue since this means that the necessary concepts remain limited.

Analysis of the types of knowledge involved in argument identification

In this section, the different facets of the knowledge that is required for argument mining are explored. We show that a revised version of the Generative Lexicon (GL) (Pustejovsky 1996) is an adequate representation that merges lexical aspects with knowledge. The experiments have been realized on the four corpora; the examples given here are extracts from case (1) (Ebola vaccination), the other corpora, although quite different from a linguistic point of view, induce similar types of observations. Let us now illustrate the various concepts used in argument kernels and how they lead to the identification of their polarity with the use of knowledge.

Main concepts used in argument kernels

Here are samples of arguments organized by polarity: Supports:

-efficiency of vaccine very good, 100% protection, -avoids or reduces dissemination of disease, -limited side-effects, -no medical alternative to vaccine, -useful to avoid crimes and bio-terrorism, -vaccine production possible, -severity of disease (high number of deaths

Expression of concepts in argument kernels

The above arguments are expressed in various ways:

• use of evaluative expressions: arguments based on concepts such as side-effects, efficiency, or costs, independently of their polarity (support or attack), can linguistically be realized by means of evaluative expressions: side effects are limited, very high. Vaccine development is very expensive, etc. The general form is based on the attribute-value format, similarly to opinion statements in opinion analysis.

• use of comparatives: arguments based on concepts such as severity of the disease, can be linguistically realized by means of comparisons: number of sick people much smaller than with Malaria. Disease is better controlled by other treatments such as patient hydration. In this case, the orientation must be evaluated from the different components of the comparison.

• use of facts related to properties of the main concept(s) of the issue: that support or contradict the issue, directly or in an elliptical way: Vaccine is not yet available. There is no risk of dissemination. Contamination can be easily controlled via simple hygiene rules., not fully tested, etc.

• use of facts related to the consequences, purposes, uses or goals of the issue, which are positive or which must be avoided: vaccine prevents bio-terrorism. Vaccination allows to develop a protection belt for other populations.

From concepts to knowledge representation

Let us now investigate how concepts can be structured and characterized to allow for an efficient argument mining process. Given any statement in a text, the challenges are (1) to identify the potential relatedness of this statement with the issue, then, (2) if related, which aspect(s) of the issue it deals with, and finally, (3) the orientation or polarity of the statement.

In corpus (1), the concept vaccine is the root of the system since it is the main term of the issue, on which the modal necessary is applied. The issue may be elliptical since vaccine may also stand for the event vaccination. The facets of this concept can be organized as follows:

-The parts of a vaccine are rather simple: the adjuvant and the active principle.

-Concerning its super types, a vaccine is a kind of medicine.

-The most central aspects of the concept vaccine w.r.t. argument mining are:

(1) its purposes, goals and consequences,

(2) how it is used, (3) how it is created, tested and sold.

A number of these features may be inherited from the concept medicine, super-type of vaccine. Another central concept of the controversial issue is the disease Ebola whose effects and consequences should be controlled by the vaccine (section 5.2).

Let us consider a few concepts used to identify the arguments presented in section 4.1 and investigate how they are related to the concepts of vaccine and Ebola, and their super-types:

-The concepts of side-effect and toxicity are consequences of using a medicine or, from a different perspective they are properties of (some) medicines.

-The concept of contamination is related to one of the purposes of a vaccine, namely to avoid contamination and disease dissemination.

-Population isolation is a means to avoid dissemination.

-Production costs are related to the creation and development of any product, including medicines and vaccines.

-Efficiency is a property that must be considered during the test phase.

The terms used in this short analysis: purpose, properties, creation and development, etc. are foundational aspects of the structure of a concept, relatively well defined in the Generative Lexicon.

Knowledge-Driven Argument Mining

An introduction to the Generative Lexicon

The Generative Lexicon (GL) [START_REF] Pustejovsky | The Generative Lexicon[END_REF] emerged from Aristotle's notion of modes of explanation. The GL is an attempt to structure lexical semantics knowledge in conjunction with domain knowledge from several perspectives. It allows to explain a number of language phenomena such as various types of metonymies via a decompositional view of lexical meaning. Various forms of so-called 'generative aspects of lexical combinations' have been characterized via the operation of type shifting, where the original type that is expected has been coerced to another type, allowing metaphors such as 'to devour books' or various forms of sense variations, which are frequent in language.

The GL develops some original forms of semantic typing, such as dotted types, that allow to account for the different facets of an entity (e.g. the physical and contents facets of a book), the development of a specific argument structure with semantic types, lexical paradigms, an event structure and the Qualia structure, which is the structure that is considered in our investigations. Very briefly, the Qualia structure of an entity is a kind of knowledge repository from which various operations can be applied. The Qualia structure is composed of four fields called roles:

-the constitutive role describes the various parts of the entity and its physical properties, it may include subfields such as material, parts and components, -the formal role describes what distinguishes the entity from other objects, i.e. the entity in its environment, in particular the entities which are more generic. It may also be structured into several subroles such as shape, dimensions, position, etc.

-the telic role describes the entity functions, uses, roles and purposes, -the agentive role describes the origin of the entity, how it was created or produced. These definitions are relatively vague and empirical. Roles are composed of predicates, which are related to the the argument structure and the event structure, which is not presented here. The predicates used in the different roles are a priori defined from a domain ontology or from a general purpose ontology.

A simple and well-known example is the case of novel(X):

Novel(X):               CONSTITUTIVE:   PHYSICAL OBJECT: PAGES, COVER, CONTENTS: CHAPTERS, STORY, CHARACTERS, ETC.

  ,

TELIC: CONTENTS: READ(Y,X), COMMENT(Y,X), ETC. , FORMAL: BOOK , AGENTIVE : WRITE(T,X), PUBLISH(P,X), SELL(P,X), ETC.

             
In this informal Qualia structure, variables are in capital letters. X is the novel, Y, a reader, T, the author, P, the publisher and P, the retailer. In the constitutive, two facets of novel are encoded: the physical object and the contents.

In the telic role, the main predicate is read; others such as comment, criticize, illustrate, develop various purposes. The physical facet, not represented here may contain predicates such as print, bind. The same remark holds for the agentive role, where, besides the authors that writes the novel, this novel is then published and sold by other actors.

Let us consider the controversial issue:

The vaccine against Ebola is necessary.

The Qualia structure of the head term of this statement, vaccine, is represented as follows:

Vaccine(X):

                CONSTITUTIVE: ACTIVE PRINCIPLE, ADJUVANT , TELIC:     MAIN: PROTECT FROM(X,Y,D) ⇒ AVOID(X,DISSEMINATION(D)), MEANS: INJECT(Z,X,Y), CONSEQUENCES: PROTECTION-BELT(D),     , FORMAL: MEDICINE, ARTEFACT , AGENTIVE : DEVELOP(T,X), TEST(T,X), SELL(T,X)                
where X is the variable that represents the vaccine, Y is the person that is vaccinated, T is the biologist or company that develops the vaccine, Z is the doctor that makes the injection, and D is the disease associated with the vaccine. The agentive role develops the way the vaccine is created while the telic role develops its functions and purposes. Note the typing introduced in this role: main functions (protect, avoid dissemination) and the means: how these functions are realized (via an injection). This Qualia representation can be further organized, in particular to develop causal and temporal chains, e.g.:

develop(E1,T,X) ∧ test(E2,T,X) ∧ sell(E3,T,X) ∧ E1 < E2 < E3.
The Qualia structure of Ebola (and more generally, of a virus) can be defined as follows: Ebola:

     FORMAL: VIRUS, DISEASE , TELIC:
INFECT(E1,EBOLA, P) ⇒ GET SICK(E2,P) ⇒ ✸ DIE(E3,P) ∧ E1 ≤ E2 ≤ E3.

    

P represents here the patient that gets the disease. The purpose of Ebola is to infect people (P) who get sick and may die. There is no agentive role since there is no volition in the Ebola virus. Ebola is a constant in this representation.

As discussed above, the roles of a Qualia contain predicative expressions. A limitation is that the GL remains a relatively theoretical notion. Relatively few resources have been produced to validate the approach, except for the EEC SIMPLE project, carried out about two decades ago.

With respect to other well-known resources, the constitutive role is close to the part-of relation and the formal is close the the isa relation frequently found in ontologies and in WordNet. The constitutive role has a rich informational structure since the different types of constituents can be specified in dedicated sub-roles. The argument structure of the GL and its semantic typing is different from FrameNet which basically develops semantic roles, which are not present in the GL. Finally, VerbNet basically describes the structure of verbs, from WordNet and semantic classifications. VerbNet also provides a conceptual representation of verbs based on a small set of conceptual primitives. The GL does not offer this level of detail, and it is, in fact, not very efficient to describe verbs. The Generative Lexicon is particularly appropriate for argument mining because of the development it offers of the telic and the agentive roles. These two roles structure most of the knowledge that is required for argument mining.

A Network of Qualias

The root of the knowledge structure are the concepts that appear in the controversial issue, namely 'vaccine' and 'Ebola' and their Qualias. Then, a network of Qualias is derived from the concepts in the root , and further on. This process stops after a few stages (three or four), because the concepts at stake to mine arguments must remain functionally or causally close to the root concepts. Qualias are related via arcs where a concept is developed into its own Qualia.

For example, in the case of 'vaccine', from 'adjuvant' in its constitutive role, the following Qualia is included into the network:

Adjuvant(Y,X1):    FORMAL : VACCINE, MEDICINE, CHEMICALS , TELIC: DILUTE(Y,X1), ALLOW(INJECT(X1,P))   
where Y is the adjuvant of X1, which is the active principle of the vaccine X. The role of an adjuvant is to dilute X1, and to allow to inject it to patients P.

From the formal role of 'vaccine', the Qualia of the concept 'medicine' is included into the network:

Medicine(X):                   CONSTITUTIVE: ACTIVE PRINCIPLE, ADDITIONS TELIC:       MAIN: CURE FROM(X,Y,D), MEANS: EAT(Z,X,Y) ∨ DRINK(Z,X,Y) ∨ INJECT(Z,X,Y) , ETC., CONSEQUENCES: PROTECTION-FROM(D), REDUCE(RISKS FOR(PEOPLE,X))       FORMAL: ARTEFACT AGENTIVE: DEVELOP(T,X), TEST(T,X), SELL(T,X,FARE)                  
Medecine is not exactly a super-type for 'vaccine', it is more shallow a notion. Therefore, a property inheritance is not systematic as it is in an 'isa' relations.

From the telic and agentive roles, a number of Qualias are introduced into the network. First, entities such as D (disease) or Y (patient) introduce their Qualias in the network. Next, predicates such as develop, test, protect, etc. introduce their own Qualia. Qualias which deal with abstract notions are more difficult to develop and make argument mining less accurate. For example, test(X,Y,T) applied to medicines:

test(X,Y, T): test X about Y by T on A:

              CONSTITUTIVE: PARTS OF A TEST: DATA, PROTOCOL TELIC:   MAIN: EVALUATE(T, PROTECTION(X,Y, A)), EVALUATE(T, SIDE-EFFECTS(X,Y, A)) MEANS:   FORMAL : SCIENTIFIC ACT AGENTIVE : ELABORATE(T,X)              

Pairing Qualia concepts with language patterns

The objective is to associate with every concept in the Qualia a number of language structures that allow the recognition of these concepts in texts. These language structures cover base forms (e.g. predicate argument structures) and various transformations such as alternations. Finally, they are embedded into argument expression structures, such as those presented in 4.2. The initial goal is therefore, given a Qualia to identify language forms which directly refer to the concepts it is composed of. If we consider the Qualia of vaccine, we have, for example for the telic role, which is the most productive in terms of argument mining: protect from(X,Y,D) : associated language pattern: [X:vaccine/medicine PRED:protect Y:human FROM D:disease] where vaccine, medicine, human and disease are lexical semantic types. 'Protect' is the verb type, which can be lexically realized by various terms which are more or less prototypical, such as: avoid, protect, immunize, keep away, and their nominal counterparts: protection. The primitive FROM can be lexicalized as any preposition that conveys this notion. This type of pattern is close to those found in VerbNet and, to a lesser extend, in FrameNet. Their usages is however restricted to the domain at stake, therefore, the lexical semantic types may be more restricted. avoid(dissemination(D)) : associated language pattern: [X:vaccine/medicine Pred :avoid DISSEMINATION of D :disease] The concept DISSEMINATION can be realized in any lexical form that captures this notion, e.g.: dissemination, diffusion, dispersal, spreading.

The same approach is used for any predicative term in the telic or agentive roles. The use of higher-order predicates (such as 'avoid') induces a pattern that includes such verbal constructions. Nominal concepts found in the constitutive and formal roles are associated with their lexical realization(s) andq with evaluative expressions: adjuvant is toxic.

From language patterns to utterances

In argument expression, the patterns presented in the previous section are realized as language utterances with some specific syntactic constructions proper to argument expression (section 4.2). A first set of realizations deals with evaluative expressions. The following constructions are frequently observed:

-negation of the VP mainly with not and do not.

-adverbs of frequency and compounds:never, almost never, seldom, rarely, not frequently, very frequently, -modals expressing doubts or uncertainty: seem, could, should, -evaluations: 100%, totally, systematically, or via adjectives that evaluate the concept: toxic, useless, etc. These constructs allow to evaluate e.g. how purposes and goals are reached: the vaccine is not fully tested; it seems to protect people from Ebola.

The other types of expressions described in 4.2 are derived in the same way. From the different terms which compose these expressions, dedicated semantic composition rules derive the orientation of the argument w.r.t. the issue. From the concepts from the Qualias which are used, the facet that is supported or attacked is induced, for example the 'test', 'protection' or 'dissemination' facets. A facet is defined from one or more combinations of concepts in the network of Qualias.

A few illustrative case-studies

Let us now illustrate our proposal via a few use-cases given the controversial issue: The vaccine against Ebola is necessary. Let us assume that an utterance such as A1 is found in a text. the problem is to identify if it is related to the issue, and, if so, how and what is its polarity.

Argument A1: The adjuvant is toxic for humans This statement a priori negatively evaluates the adjuvant (assuming it is related to the Ebola vaccine). The constitutive role of vaccine(X) says that the adjuvant is part of the vaccine. The Qualia of adjuvant is given in 5.2 indicates that the adjuvant is mixed via dilution with the active principle of the vaccine:

(1) The purpose of dilute(Y,X1) (given in its telic role) is that Y and X1 are mixed together and form a single entity: the vaccine X.

Then the following reasoning schema is developed:

(1) upwards inheritance of a property in a part-of relation: if a (major) constitutive part K1 of an object K has a property P (i.e. toxic), then (probably) the entire object K has P (is toxic for humans): has property(K1,P) ∧ part of(K1,K) ⇒ has property(K,P).

(2) since Y and X1 are parts of X, and Y is injected with X1 (from the telic of adjuvant), then since Y is toxic for humans, it follows that X is also toxic for humans. Therefore, argument A1 has a negative orientation, due to the negative polarity of toxic (lexical feature of the adjective), therefore A1 attacks the controversial issue. This statement may also be interpreted as a contrast to the controversial issue: 'the vaccine is necessary BUT it is toxic'. According to the semantics of a contrast (e.g. (Winterstein 2012)), the second part of the contrast, Q, in: 'P but Q', wins without being in full contradiction with the controversial issue P.

Argument A2: The vaccine does not always protect people: 3 vaccinated people died in Monrovia

This statement is composed of two parts: an evaluation and then a justification. (2) Then it follows from the telic of vaccine(X) that: ¬ ✷(protect from(X,Y,ebola).

(3) Argument A2 attacks the controversial issue, which says that vaccines protect the population (with no exception). However, since the number of deaths is very limited, this statement may be interpreted either as a weak attack or as a concession:

Vaccine protects the population HOWEVER there are a few cases where it does not work. Informally, a concession in argumentation basically supports the controversial issue, but adds some restrictions that weaken the strength of the support.

Argument A3: Seven persons died during the Ebola vaccine tests

This statement reports deaths that occurred during tests. 'Die' has obviously a negative polarity. If we consider again the GL structure of vaccine(X), the 'test' activity is related to the agentive role. An axiomatization of the GL structure says: By definition, the agentive role is pre-telic: the events it describes occur before the functions or events given in the telic role. There are a priori no relations between these two sets of events. In more formal terms, where P and Q are predicates, and E event variables:

∀ P(E) ∈ agentive-role, ∀ Q(E1) ∈ telic-role, E < E1 ∧ ¬(P ⇒ Q).
From an argumentation point of view, A3 is irrelevant or neutral w.r.t. the controversial issue since tests are independent from the vaccination itself. However, due to its very negative orientation we can say that A3 weakly attacks the issue: the vaccine must be developed, BUT tests are dangerous. It is a form of concession. These three case studies show the type of reasoning schemes that need to be developed to identify arguments, their polarity and the facet(s) involved in the controversial issue. These need to be further elaborated and categorized to form a set of argument mining reasoning schemes.

Summing up

The analyses we carried out show that the boundaries between attacks, neutral, concession, contrast and support are not very clearcut, and that there is a kind of continuum between them. They also show that attacks and supports may only concern some facets of the controversial issue.

The other main interest of this analysis is that, given a set of independent statements, coming from different origins, it is possible to precisely relate them (or not) to the main issue and to identify, for each of them, if they are arguments, how they are related, their argumentative orientation and strength. This is realized by means of three main knowledge and reasoning sources:

• lexical data: via semantic features for lexical items, in particular polarity (for verbs and adjectives), intensity and modality (for adverbs and adjectives), scales for antonyms, etc.,

• domain knowledge: encoded via the Generative Lexicon Qualia structure, including event structures, causal chains and role sub-typing, in conjunction with lexical data.

• reasoning: several types of inferences have been identified:

1. inferences related to the semantics of the Qualia roles in the GL structure, 2. inferences related to lexical semantics structures (e.g. feature inheritance, blocking), 3. inferences related to general purpose domain knowledge and to presuppositions, 4. inferences dedicated to argumentation, that allow to compute relations and their strength between the controversial issue and the argument at stake. These are specific compositionality rules.

A challenge is to identify strategies that indicate which rule or data must be triggered to analyze the relation between the potential argument at stake and the controversial issue.

Finally, another challenge is the analysis of the scalability of such an argument mining system that includes domain knowledge, in particular the development of Qualia structures. So far, there is no resource available. It seems that for a given controversial issue, or for a domain, such as those advocated in section 3.1, the number of Qualias to be developed should be lower than 50. However, while this number of Qualias allows a manual development, the introduction of automatic acquisition techniques would permit to have richer Qualias. For example, for the telic facet, purposes could be searched via language patterns (which can be encoded in TextCoop). This is an open research topic that deserves attention since Qualias seem an appropriate formalism for dealing with knowledge and linguistic data in argument mining.

Perspectives

This paper shows how knowledge can be introduced and paired with language processing to mine arguments. Knowledge is a major bottleneck to argument mining, given a controversial issue and a set of texts in which arguments can be found. The goal is to identify arguments, their polarity or orientation, which facet of the issue is attacked or supported and how. Our approach to argument mining is thus knowledge driven.

In this paper, to motivate this approach, we first developed a corpus analysis to characterize these challenges, outlining the types of knowledge required to extract and characterize arguments. We then briefly shown how the Qualia structure can be enhanced for the purpose of argument mining. Finally we developed via examples how language patterns are associated with Qualia to extract arguments. This paper is essentially a linguistic and knowledge modeling contribution. Such a topic requires more corpus analysis, the elaboration resource development methods and techniques, and a categorization of the reasoning schemas which are involved before developing a large-scale argument mining system.

Table 3 .

 3 Evidence for Knowledge

	Attacks Supports Concessions Contrasts Ambiguous
	51	32	17	18	4
		Table 2. Polarity distribution
	The corpus shows a tendency to argue against an issue
	rather than to support it (attacks and contrasts = 57%,
	supports and concessions = 40%). The need of knowledge
	to identify the relation between the issue and the argument
	and the number of different concepts involved is summa-
	rized as follows:
	Issue need of knowledge total number of concepts
		(nb of cases + rate)	involved (estimate)
	(1)	44 (88%)		54
	(2)	18 (75%)		23
	(3)	18 (58%)		19
	(4)	15 (88%)		25
	Total	95 (78%)		121

  ) .

	Attacks:
	-Limited number of cases and deaths compared to other
	diseases,
	-Limited risk of contamination, ignorance of contamina-
	tion forms,
	-Can be controlled by other medical treatments,
	-Very high production costs, too expensive for poor coun-
	tries,
	-Toxicity and high side-effects,
	-Excessive government reaction: isolation of populations,
	racism.
	Concessions or Contrasts:
	-Some side-effects,
	-High production and development costs,
	-Getting competent staff + P4 lab difficult,
	-Difficult to demonstrate efficiency, not enough data,
	-Vaccine not yet available,
	-Ethical and freedom problems,
	-Results around 90% (performances), therefore not fully
	reliable.
	etc.


Jean-Guillaume Fages
email: jean-guillaume.fages@mines-nantes.fr

Xavier Lorca
email: xavier.lorca@mines-nantes.fr

Louis-Martin Rousseau
email: louis-martin.rousseau@cirrelt.net

The Salesman and the Tree: the importance of search in CP

The traveling salesman problem (TSP) is a challenging optimization problem for CP and OR that has many industrial applications. Its generalization to the degree constrained minimum spanning tree problem (DCMSTP) is being intensively studied by the OR community. In particular, classical solution techniques for the TSP are being progressively generalized to the DCMSTP. Recent work on cost-based relaxations has improved CP models for the TSP. However, CP search strategies have not yet been widely investigated for these problems. The contributions of this paper are twofold. We first introduce a natural generalization of the weighted cycle constraint (WCC) to the DCM-STP. We then provide an extensive empirical evaluation of various search strategies. In particular, we show that significant improvement can be achieved via our graph interpretation of the state-of-the-art Last Conflict heuristic.

Motivation

The traveling salesman problem (TSP) involves finding a Hamiltonian cycle of minimum weight in a given undirected graph G = (V, E) associated with a weight function w : E → Z. It has been widely investigated by the operational research (OR) community for more than half a century, because it is an important optimization problem with many industrial applications. Its simple structure has enabled the development of general techniques, such as cutting planes, variable fixing, Lagrangian relaxation, and heuristics. These techniques are the key to the success of dedicated solvers (e.g., Concorde [START_REF]Concorde TSP solver[END_REF]), and they can be adapted to a range of optimization problems. Some have even been integrated into general MIP solvers, leading to great improvements in OR.

A natural extension of the TSP is the degree constrained minimum spanning tree problem (DCMSTP). Given an undirected weighted graph G = (V, E) associated with a weight function w : E → Z and an integer array d max , the DCMSTP involves finding a minimum spanning tree (MST) of G for which every vertex v ∈ V has at most d max [v] neighbors. In this way, a TSP can be reduced to a DCMSTP in which for any v ∈ V , d max [v] = 2. Consequently, the techniques developed for the TSP have been generalized to the DCMSTP.

From the constraint programming (CP) point of view, the TSP is very challenging, because it is only slightly constrained, and the cost function is a major difficulty. This means that only a poor propagation can be expected from a basic CP approach. However, when relaxations are considered, a good cost-based filtering can be achieved [START_REF] Focacci | Cost-based domain filtering[END_REF][START_REF] Focacci | Optimization-oriented global constraints[END_REF]. Indeed, the most successful CP approaches to date owe their success to the introduction of relaxations, first introduced in OR, in the global constraints [START_REF] Benchimol | Improved filtering for weighted circuit constraints[END_REF][START_REF] Focacci | Embedding relaxations in global constraints for solving TSP and TSPTW[END_REF]. From this perspective, the TSP allows us to study the behavior of CP solvers on problems that are dominated by optimization and to experiment with hybridization between CP and OR. However, search has not yet been widely investigated for this problem. Furthermore, none of the recent advances have been generalized to the DCMSTP, although such generalization is natural.

The contributions of this paper are twofold. First, in Section 2.2 we introduce a natural generalization of the weighted cycle constraint (WCC) [START_REF] Benchimol | Improved filtering for weighted circuit constraints[END_REF] to the DCM-STP. Second, we empirically evaluate a wide range of graph search heuristics on the TSP and the DCMSTP. These heuristics are presented in Section 3. They include a graph adaptation of Last Conflict [START_REF] Lecoutre | Reasoning from last conflict(s) in constraint programming[END_REF], which brings a greedy form of learning to the model. The experimental analysis (Sections 4 and 5) shows that significant improvement can be achieved by considering some simple graph properties at the search level. More precisely, the runtime is improved by up to four orders of magnitude over that of the state-of-the-art TSP approach of Benchimol et al. [START_REF] Benchimol | Improved filtering for weighted circuit constraints[END_REF]. This pushes further the limits of CP, although dedicated OR solvers [START_REF]Concorde TSP solver[END_REF] remain ahead. For the DCMSTP, the results show that CP is a competitive approach.

The state-of-the-art CP models for the TSP and the DCMSTP

This section presents the state-of-the-art TSP model in CP (Section 2.2) and derives a DCMSTP model from it (Section 2.3). Since these models rely on a graph variable, we begin by providing an introduction to graph variables (Section 2.1).

Graph variables

Graph variables were introduced in [START_REF] Le Pape | Robust and parallel solving of a network design problem[END_REF]. We recall that a graph variable GRAPH has a domain defined by a graph interval dom(GRAPH) = [GRAPH, GRAPH]. A value for GRAPH is a graph included between GRAPH and GRAPH; see Figure 1 for an illustration.

The solving process involves adding to GRAPH (enforcing) some vertices and edges, and removing from GRAPH some other vertices and edges. Such operations are triggered by either filtering algorithms or the search process. These steps are performed until the graph variable is instantiated, i.e., until GRAPH = GRAPH. In other words, GRAPH and GRAPH are respectively monotonically increasing and decreasing.

A C D F G H (a) GRAPH A B C D E F G H (b) GRAPH A B C D E F G H (c) GRAPH compact domain representation A C D E F G H (d) A possible value for GRAPH Fig. 1. Graph variable illustration.
We use an undirected graph variable for which every vertex is mandatory, so the branching and filtering will concern only edges. More precisely, we use a binary search process in which each decision selects an unfixed edge, enforcing it in the left branch and removing it in the right branch. One can view the graph variable as an abstraction over a set of binary variables representing edges. In this representation, a decision selects a non-instantiated binary variable associated with an edge, and tries to assign it first the value 1 and then 0. Additional information on graph variables can be found in [START_REF] Dooms | CP(Graph): Introducing a graph computation domain in constraint programming[END_REF][START_REF] Régin | Tutorial: Modeling problems in constraint programming[END_REF].

TSP state-of-the-art model

The state-of-the art CP formulation for the TSP uses a single graph variable GRAPH to represent the expected cycle and an integer variable Z to represent the objective function:

INPUT: Undirected graph G = (V, E) Weight function w : E → Z CP MODEL: Minimize Z (1) Constraint WCC(GRAPH, Z, w) (2) Initial domains dom(GRAPH) = [(V, ∅), (V, E)], (3) dom
(Z) = [-∞, LKH(G, w)] (4)
As can be seen, the TSP can be modeled as a minimization problem (1) involving a single graph constraint (2), the WCC, introduced by Benchimol et al. [START_REF] Benchimol | Improved filtering for weighted circuit constraints[END_REF]. The graph variable GRAPH is defined (3) as a spanning subgraph of G. The domain of the objective variable Z (4) is initialized via the Lin-Kernighan-Helsgaun heuristic (LKH) [START_REF] Helsgaun | An effective implementation of the Lin-Kernighan traveling salesman heuristic[END_REF], which is probably the most efficient heuristic for the TSP. No initial lower bound is given since the WCC propagation handles the lower bounding.

The WCC of Benchimol et al. [START_REF] Benchimol | Improved filtering for weighted circuit constraints[END_REF] was a significant step forward that enabled CP to be competitive on instances of a reasonable size. This constraint is defined over a graph variable and embeds the 1-tree relaxation of Held and Karp [START_REF] Held | The traveling-salesman problem and minimum spanning trees: Part II[END_REF], which provides a very powerful filtering. The 1-tree relaxation is roughly a careful adaptation of the minimum spanning tree relaxation to the case where a cycle is expected instead of a tree. More precisely, a 1-tree rooted in a vertex u ∈ V consists of a minimum tree spanning every vertex but u, plus the two cheapest edges that are incident to u, so that the resulting relaxation has as many edges as a Hamiltonian cycle. This relaxation is improved with the subgradient optimization of Held and Karp [START_REF] Held | The traveling-salesman problem and minimum spanning trees: Part II[END_REF], which tends to the linear relaxation of the classical TSP linear programming model. In addition to lower bounding, back-propagation can be achieved from this relaxation: edges in (resp. out of) the relaxation support can be enforced (resp. removed) based on replacement (resp. marginal) costs [START_REF] Benchimol | Improved filtering for weighted circuit constraints[END_REF]. The filtering rules of WCC are detailed in [START_REF] Benchimol | Improved filtering for weighted circuit constraints[END_REF], and they mainly stem from [START_REF] Held | The traveling-salesman problem and minimum spanning trees: Part II[END_REF][START_REF] Régin | Simpler and incremental consistency checking and arc consistency filtering algorithms for the weighted spanning tree constraint[END_REF][START_REF] Régin | Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems[END_REF], which form good further references. An illustration is provided in Figure 2(c). This relaxation is rooted at vertex F and gives a lower bound of 12.

Extending the TSP model to solve the DCMSTP

From the above TSP model, we can naturally derive a CP model for the DCM-STP. It uses a single graph variable GRAPH to represent the expected tree, an array of n integer variables D to represent the vertex degrees, and an integer variable Z to represent the objective function:

INPUT: Undirected graph G = (V, E) Weight function w : E → Z Maximum degree function d : V → N CP MODEL: Minimize Z (5) Constraint DCWSTC(GRAPH, Z, w, D) (6) Initial domains dom(GRAPH) = [(V, ∅), (V, E)], (7) dom
(D[v]) = [1, d(v)], ∀v ∈ V (8) dom(Z) = [-∞, +∞] (9)
The DCMSTP is modeled as a minimization problem (5) involving a single graph constraint [START_REF] Dooms | CP(Graph): Introducing a graph computation domain in constraint programming[END_REF], the degree constrained weighted spanning tree constraint (DCWSTC) that we introduce as a generalization of WCC. The graph variable GRAPH is defined as a spanning subgraph of G [START_REF] Focacci | Cost-based domain filtering[END_REF]. The degree variables D are defined according to the maximum degree function d [START_REF] Focacci | Embedding relaxations in global constraints for solving TSP and TSPTW[END_REF]. The domain of the objective variable Z has no initial bounds [START_REF] Focacci | Optimization-oriented global constraints[END_REF].

The DCWSTC is a direct generalization of the WCC in which the 1-tree is replaced by a spanning tree, and the vertex degrees are no longer constrained to be 2 but are equal to the corresponding degree variable. It thus involves a Lagrangian process that iteratively solves the MST problem and updates the cost function according to the violations of the degree constraints, as described in [START_REF] Andrade | Using Lagrangian dual information to generate degree constrained spanning trees[END_REF][START_REF] Salles | Lower and upper bounds for the degree-constrained minimum spanning tree problem[END_REF]. The filtering rules are directly derived from the WCC.

In contrast to the TSP model, the DCMSTP model has no particular upper bounding procedure. Since DCWSTC requires an upper bound for its subgradient method, we set up our own preprocessing step by simply changing the search strategy of the model. We compute a first solution by branching on the cheapest edges and propagating constraints (with Lagrangian relaxation turned off). Once a solution has been found, the solver restarts and the preprocessing is over. Thanks to the powerful DCWSTC filtering, the model is better at finding a good lower bound than improving the upper bound. Therefore, we use a bottom-up minimization strategy: instead of computing improving solutions, the solver aims to find a solution that has the value of the objective lower bound. If no such solution exists, then the objective lower bound is increased by one unit. This scheme is implemented by branching on the objective variable and enumerating its values. Once the objective variable has been fixed, we must branch on the graph variable to either find a solution or prove that none exists. This paper focuses on the use of graph search heuristics for this step.

Studying graph search strategies

This section describes the application of various general heuristics to a graph variable. We also suggest several graph adaptations of Last Conflict [START_REF] Lecoutre | Reasoning from last conflict(s) in constraint programming[END_REF], which may be useful for solving many other graph problems.

General graph heuristics

We believe that simpler heuristics are more likely to be used in different contexts and therefore more likely to yield general results. We describe some heuristics that can naturally be applied to a graph variable, and we experimentally compare them in the next section:

-General graph heuristics consider only the graph variable:

• LEXICO: Selects the first unfixed edge.

• MIN_INF_DEG (resp. MAX_INF_DEG): Selects an edge for which the sum of the endpoint degrees in GRAPH's lower bound is minimal (resp. maximal). • MIN_SUP_DEG (resp. MAX_SUP_DEG): Selects an edge for which the sum of the endpoint degrees in GRAPH's upper bound is minimal (resp. maximal).

• MIN_DELTA_DEG (resp. MAX_DELTA_DEG): Selects an edge for which the sum of the endpoint degrees in GRAPH's upper bound minus the sum of the endpoint degrees in GRAPH's lower bound is minimal (resp. maximal).

-Weighted-graph heuristics have access to the cost function w:

• MIN_COST (resp. MAX_COST): Selects an edge with the minimal (resp. maximal) weight.

-Relaxation-based graph heuristics have access to a problem relaxation, presumably embedded in a global constraint, which maintains a support, variable marginal costs, and variable replacement costs:

• IN_SUPPORT (resp. OUT_SUPPORT): Selects an edge in (resp. out of) the support of the relaxation.

• MIN_MAR_COST (resp. MAX_MAR_COST): Selects an edge with the minimal (resp. maximal) marginal cost, i.e., the edge outside the relaxation support for which enforcing involves the smallest (resp. largest) increase in the relaxation value.

• MIN_REP_COST (resp. MAX_REP_COST): Selects an edge for which the replacement cost is minimal (resp. maximal), i.e., the edge of the relaxation support for which removal involves the smallest (resp. largest) increase in the relaxation value.

To keep this study simple, we break ties in a lexicographic manner. Figure 2 illustrates the behavior of the heuristics. Given the graph variable domain of Figure 2 It is worth mentioning that the TSP model of [START_REF] Benchimol | Improved filtering for weighted circuit constraints[END_REF] uses MAX_REP_COST to branch on edges. However, it uses an opposite branching order: it first removes the selected edge and then enforces it upon backtracking. We found that the branching order had no significant influence on the results, so we decided to consider only the case where the edge is first enforced and then removed. This order is more natural, by analogy to integer variables for which decisions are usually value assignments, not value removals.

LEXICO MIN_INF_DEG MAX_INF_DEG MIN_SUP_DEG MAX_SUP_DEG MIN_DELTA_DEG MAX_DELTA_DEG MIN_COST MAX_COST IN_SUPPORT OUT_SUPPORT MIN_MAR_COST MAX_MAR_COST MIN_REP_COST MAX_REP_COST Next edge to be (A,B) (A,B) (G,H) (A,B) (A,E) (G,H) (A,E) (E,G) (B,E) (A,E) (A,B) (A,B) (D,E) (B,C) (E,G) selected (c) Edge selection for each heuristic.

Adapting Last Conflict to graph problems

This paper focuses on exact approaches that are able to provide an optimality certificate. Because of the need to prove optimality, the search will presumably spend much time in infeasible regions of the search space. Hence, the Fail First principle [START_REF] Haralick | Increasing tree search efficiency for constraint satisfaction problems[END_REF] recommends first taking the decisions that are the most likely to fail, in order to get away from infeasible regions as soon as possible. To follow this principle, we apply a graph adaptation of the Last Conflict search pattern together with a heuristic.

Last Conflict [START_REF] Lecoutre | Reasoning from last conflict(s) in constraint programming[END_REF] is a generic heuristic that is designed to be used together with any other heuristic, whence the term search pattern. We recall that its main rule is basically: If branching on some variable x yields a failure, then continue branching on x. Let us consider a decision involving a variable x that resulted in a failure. Last Conflict is based on the intuition that including x in the next decision would have a similar result, i.e., another failure. More precisely, there exists a minimal unsatisfiable set (MUS) of constraints [START_REF] García De La Banda | Finding all minimal unsatisfiable subsets[END_REF], C MU S , that is responsible for the failure that occurred. There is no guarantee that x is involved in a constraint of C MU S . However, if x is not responsible for the unsatisfiability of the problem, it has allowed propagation to determine that the problem was not satisfiable at the previous search node. This could be a matter of luck, or it could occur because the problem structure is such that x is strongly related to C MU S . If so, and if the problem remains unsatisfiable after several backtracks, it is likely that branching on x will allow the solver to again determine the unsatisfiability. Thus, this process should speed up the recovery of a satisfiable state as well as the proof of optimality. For this reason, Last Conflict can be seen as a form of greedy learning, coming with no overhead.

In our case, the LKH heuristic [START_REF] Helsgaun | An effective implementation of the Lin-Kernighan traveling salesman heuristic[END_REF] provides an extremely good initial upper bound for the TSP. Furthermore, since our DCMSTP model involves a bottomup minimization, the objective upper bound of the DCMSTP is also low. Thus, both the TSP model and the DCMSTP model are presumably unsatisfiable during most of the search, and failing again is therefore desirable. However, when we use a single graph variable, Last Conflict is useless because any decision already considers this variable. Thus, we must modify Last Conflict to achieve its expected behavior. We suggest a graph adaptation that involves a vertex, instead of a variable, in the last decision. The resulting branching rule is illustrated in Figure 3. Whenever a decision over an edge (u, v) ∈ E is computed, one of its endpoints, say u, is arbitrarily chosen to be stored. While failure occurs, our graph interpretation of Last Conflict states that the next decision must involve an edge that is incident to u, if at least one such edge is unfixed. In other words, the heuristic continues branching in the same region of the graph, because it believes that there is more structure to exploit there.

We empirically investigate several policies for choosing the vertex to reuse after a failed branching decision over an edge (u, v) ∈ E:

-LC_FIRST: Reuses the first vertex, u.

-LC_RANDOM: Keeps both u and v in memory and randomly chooses which to reuse.

-LC_BEST: Keeps both u and v in memory and reuses that most suited for the heuristic. For instance, if MIN_COST is used, then this policy will select the vertex with the cheapest unfixed edge in its neighborhood.

A simple way to implement LC_FIRST is given by Algorithm 1. This branching rule adjusts the heuristic upon failure by restricting the decision scope to the subset of unfixed edges induced by the neighborhood of a given vertex (line 7), if this subset is not empty. Otherwise, while no failure occurs, the heuristic operates normally. For the sake of generality, we show how it can be used when branching on vertices as well (see the NEXTVERTEX function). However, in the context of the TSP, only edge selection is relevant because every vertex is mandatory.

Algorithm 1 Implementation of LC_FIRST as a composite

20:

end if

21:

return last_vertex

22: end function

An illustration of the behavior of LC_FIRST with the MAX_COST heuristic is given in Figure 3. MAX_COST sequentially selects edges (B, E), (G, H), and (A, B). The constraint propagation then raises a failure, so the solver backtracks and removes edge (A, B). This leads to another failure, as well as the removal of edge (G, H), so the solver backtracks and deduces that edge (B, E) must be removed. Propagating this information leads to no failure, so a new decision has to be computed to continue the solving process. LC_FIRST now adjusts MAX_COST by forcing it to use an edge around vertex A, because A was in the last decision.

Settings

Our implementation has been integrated into Choco-3.1.1, a Java library for constraint programming, so that the community can reproduce our results. The state-of-the-art model of [START_REF] Benchimol | Improved filtering for weighted circuit constraints[END_REF] was implemented in C++; it was compiled with gcc with optimization flag -O3. All the experiments were performed on a Macbook Pro with a 6-core Intel Xeon at 2.93 Ghz running MacOS 10.6.8 and Java 1.7. Each run had one core. We considered the TSP instances of the TSPLIB data set, which is a reference benchmark in OR. This library is a compilation of the most challenging TSP instances that have been studied in the literature. These instances are due to various authors and stem from routing, VLSI design, simulations, etc. We considered instances with up to 300 vertices, which seems to be the new limit for exact CP approaches on this benchmark.

This study is divided into two parts. First, we compare the heuristics of Section 3.1, together with the Last Conflict policies of Section 3.2 and the case where no policy is used, in order to highlight both good and bad design choices. Second, we compare the best model found with the state-of-the-art approach and measure the speedup we achieve.

Heuristic comparison

We now evaluate the heuristics suggested in Section 3.1, together with the graphbased Last Conflict policies of Section 3.2, to determine the best combination. To reduce the computational time, we consider the 42 simplest instances of the TSPLIB and use a time limit of one minute. Figure 4 gives the results for the various search heuristics, together with several Last Conflict policies. The policy NONE corresponds to the case where we do not use any form of Last Conflict.

The best results are achieved by MAX_COST and MIN_DELTA_DEG. In contrast, MIN_COST is surprisingly bad. This result confirms the intuition of the Fail-First principle on which our approach is based. Indeed, MIN_DELTA_DEG, which selects edges in sparse graph areas, may trigger failures from structurebased propagation, and MAX_COST, which selects expensive edges, may trigger failures from the 1-tree relaxation. This result also shows that simple heuristics perform better than more elaborate ones that require access to a problem relaxation (to obtain marginal and replacement costs). Surprisingly, MAX_REP_COST does not give good results. Since it is used in the state-of-the-art model, this confirms the claim that search plays an important role in the solution process and that it can still be improved.

Furthermore, whatever the policy, Last Conflict improves every search strategy evaluated. LC_FIRST allows us to solve 27% more instances on average. While it is the simplest policy, it performs better than both LC_RANDOM and LC_BEST. Overall, using LC_FIRST with either MIN_DELTA_DEG or MAX_COST enables us to solve 41 of the 42 instances within the one-minute time limit. Interestingly, the instance that remains unsolved varies from one heuristic to another. However, we were not able to solve all 42 instances by combining two heuristics. In summary, Last Conflict significantly improves the model, and important performance differences can be observed from one heuristic to another.

Pushing the limits of CP

We now compare our model to the state-of-the-art CP approach of Benchimol et al. [START_REF] Benchimol | Improved filtering for weighted circuit constraints[END_REF], referred to as SOTA. For these comparisons we use MAX_COST with LC_FIRST, which appears to work well. We note that similar results are obtained when MIN_DELTA_DEG is used instead of MAX_COST.

For this study, we increase the time limit to 30, 000 seconds to obtain a more precise evaluation of the speedup possible. We consider 34 challenging instances, with between 100 and 300 vertices, which represents the current limit of CP. The simpler instances are solved in less than a second by both approaches, whereas the harder ones cannot be solved by either approach. Figure 5 compares our approach with SOTA. The horizontal axis represents the instances. The first vertical axis shows the speedup (black), which is defined as the ratio of the solution time of SOTA over the solution time of CHOCO, with a log scale. The second vertical axis shows the solution time of CHOCO (dark gray) and SOTA (light gray), in seconds. The raw solution times are also provided.

Figure 5 shows that our heuristic gives a significant speedup on most instances. More precisely, the speedup is 511 on average, and it increases with the instance difficulty, up to four orders of magnitude (on bier127). The speedup then decreases because of the time limit. The solution time of the two approaches clearly shows that we have pushed the exponential further, from 100-200 to 200-300 vertices. This remains however below the performance of Concorde [START_REF]Concorde TSP solver[END_REF], the state-of-the-art TSP solver in OR (see [START_REF] Benchimol | Improved filtering for weighted circuit constraints[END_REF] for a comparison). Comparison with the state-of-the-art CP approach on challenging instances of the TSPLIB with a 30, 000-second time limit.

5 Experimental analysis for the DCMSTP

Settings

Our implementation has been integrated into Choco-3.1.0, a Java library for constraint programming, so that the community can reproduce our results. We reproduced the state-of-the-art approach of [START_REF] Salles | A hybrid relax-and-cut/branch and cut algorithm for the degree-constrained minimum spanning tree problem[END_REF]. All our experiments were done on a Macbook Pro with a 6-core Intel Xeon at 2.93 Ghz running MacOS 10.6.8 and Java 1.7. Each run had one core. We consider the hardest DCMSTP instances in the literature, the data sets ANDINST, DE, and DR [START_REF] Salles | Lower and upper bounds for the degree-constrained minimum spanning tree problem[END_REF]. In the ANDINST and DE instances, each vertex is associated with a randomly generated point in the Euclidean plane. The cost function is then the Euclidean distance between the vertices. The maximum degree of each vertex is randomly chosen in [START_REF] Andrade | Using Lagrangian dual information to generate degree constrained spanning trees[END_REF][START_REF] Salles | Lower and upper bounds for the degree-constrained minimum spanning tree problem[END_REF] for the ANDINST instances, and it is in [START_REF] Andrade | Using Lagrangian dual information to generate degree constrained spanning trees[END_REF][START_REF]Concorde TSP solver[END_REF] for the DE instances. Thus, DE can be said to be harder to solve. In the set DR, the cost function associates with each edge a randomly generated value in the range [START_REF] Andrade | Using Lagrangian dual information to generate degree constrained spanning trees[END_REF]1000], and the maximum degree of each vertex is in [START_REF] Andrade | Using Lagrangian dual information to generate degree constrained spanning trees[END_REF][START_REF]Concorde TSP solver[END_REF]. This last set is known to be hard to solve by existing approaches. The ANDINST instances have from 100 to 2, 000 vertices, while the DE and DR instances involve graphs of 100 to 600 vertices.

This study is divided into two parts. First, we compare the heuristics of Section 3.1, together with the Last Conflict policies of Section 3.2 and the case where no policy is used, in order to highlight both good and bad design choices. Second, we compare the best model found with the state-of-the-art approach and measure the speedup we achieve.

Heuristic comparison

We now extend the previous experimental analysis to the DCMSTP. As a first step, we evaluate the heuristics of Section 3.1, together with the graph-based Last Conflict policies of Section 3.2, to determine the best combination. To reduce the computational time, we consider the 36 smallest instances and use a time limit of one minute. These 36 instances have up to 400 vertices, and they are evenly spread over the data sets ANDINST, DE, and DR. Figure 6 shows the number of instances that could be solved within the time limit, for each heuristic combination. NONE corresponds to the case where we do not use any form of Last Conflict. We make two observations. First, Last Conflict has a similar impact on the results as in the TSP case. Whatever the policy, it improves every search strategy evaluated. Furthermore, LC_FIRST again provides the best results on most of the problems. It gives a significant improvement, allowing us to solve 14% more instances on average.

Second, when LC_FIRST is used, all the search heuristics lead to similar results (between 29 and 31 solved instances). This is quite different from the observations for TSP instances.

Competitiveness of CP

We now compare our model to the state-of-the-art approach of Salles da Cunha and Lucena [START_REF] Salles | A hybrid relax-and-cut/branch and cut algorithm for the degree-constrained minimum spanning tree problem[END_REF], referred to as SOTA. This method is inspired by techniques found in [START_REF]Concorde TSP solver[END_REF] that are used to solve the TSP. It combines local search, Lagrangian relaxation, filtering, and cutting planes. We used the MIN_SUP_DEG heuristic with LC_FIRST, which appears to work well for solving the DCMSTP with CP.

For this study, because some of the instances are hard to solve, we increase the time limit to 30, 000 seconds. We consider all the instances of the data sets ANDINST, DE, and DR that were studied in [START_REF] Salles | A hybrid relax-and-cut/branch and cut algorithm for the degree-constrained minimum spanning tree problem[END_REF]. Figure 7 depicts the improvement (or deterioration) over SOTA. The horizontal axis represents the instances. The first vertical axis shows the speedup (black), which is defined as the ratio of the solution time of SOTA to the solution time of CHOCO, with a log scale. The second vertical axis shows the solution time of CHOCO (dark gray) and SOTA (light gray) in seconds. Figure 7 is split according to the data sets.

Figure 7(a) shows that our CP approach to the DCMSTP is competitive with [START_REF] Salles | A hybrid relax-and-cut/branch and cut algorithm for the degree-constrained minimum spanning tree problem[END_REF] on most easy Euclidean instances. However, it has difficulty solving three 2, 000-vertex instances. Since the input graphs are complete, this represents about two million edge instances. In the Euclidean case, when the maximum vertex degrees become more restricted (Figure 7(b)), the CP approach gets into trouble on smaller instances. More precisely, it cannot solve two instances, with 500 and 600 vertices respectively, within the time limit. This indicates that, up to a certain size, CHOCO is competitive with SOTA. However, for large instances, the dedicated OR approach is more efficient. One reason that Euclidean instances are hard to solve in CP is the fact that the proximity relationship between the vertices is transitive: if vertex A is close to vertex B and if B is close to C, then vertices A and C are also close. This impacts the behavior of the Lagrangian relaxation, which may have weak marginal costs and therefore an insufficient filtering. In contrast, CP is well suited to random instances (see Figure 7(c)). CHOCO achieves a significant speedup over SOTA, up to two orders of magnitude. On such instances, the vertex proximity is no longer transitive, and so the propagation of any edge removal (or enforcing) through the DCWSTC provides a strong filtering. This enables CHOCO to solve every instance in less than three minutes, whereas SOTA takes, for example, more than two hours to solve dr_600_2. This paper suggests a generalization of the WCC, which requires a graph variable to form a weighted spanning tree for which every vertex degree is constrained. As the WCC requires an important implementation investment, this natural generalization is convenient.

We have presented an extensive experimental study of the ability of numerous general graph heuristics to solve the TSP and the DCMSTP. We decided to study simple and natural heuristics, which we believe are more likely to be implemented and extended to other problems than sophisticated and dedicated ones are. Additionally, we have investigated several ways to adapt Last Conflict to graph variables. All of them improve the CP model, whatever the underlying heuristic. This gives a general significance to our results. Surprisingly, the experiments indicate that the simplest heuristics have the best performance, which is desirable. From a more practical point of view, we show how to improve the state-of-the-art CP approach for the TSP by up to four orders of magnitude, pushing further the limits of CP. We have shown that the CP model outperforms the state-of-the-art OR method on random DCMSTP instances. However, it does not yet compete with OR [START_REF]Concorde TSP solver[END_REF][START_REF] Salles | A hybrid relax-and-cut/branch and cut algorithm for the degree-constrained minimum spanning tree problem[END_REF] on the hardest TSP and DCMSTP instances.

Since Last Conflict is a greedy form of learning, a natural next step for the CP community would be to further investigate how learning can help the solution process, e.g., by explaining the WCC constraint. Recent work on explaining the circuit constraint [START_REF] Francis | Explaining circuit propagation[END_REF] provides a promising starting point.

  (a) and the relaxation of Figure 2(b), Figure 2(c) indicates the edge that each heuristic would branch on at the next decision.

  Graph variable with edge weights. Only dotted edges are valid candidates for branching. 1-tree relaxation rooted in F , with marginal and replacement costs. Bold edges represent the relaxation support. Search graph-based cost-based relaxation-based

Fig. 2 .

 2 Fig. 2. Illustration of various strategies.

Fig. 3 .

 3 Fig.3. Illustration of the search tree when using LC_FIRST with MAX_COST on the example. After a failure, the next decision must involve the last decision's first vertex (A).

  (a) Graphical representation: whatever the search heuristic, it is always better to use it with one of the Last Conflict policies. LC_FIRST and LC_BEST respectively provide the best results for 10 and 4 of the 15 tested heuristics.

Fig. 4 .

 4 Fig. 4. Quantitative evaluation of search heuristics, together with various Last Conflict policies: number of instances among 42 simple instances of the TSPLIB solved within a one-minute time limit.

  (a) Comparison of solution time in seconds for SOTA[START_REF] Benchimol | Improved filtering for weighted circuit constraints[END_REF] and CHOCO with LC_FIRST and MAX_COST. The speedup is computed as the solution time of SOTA over the solution time of CHOCO. The speedup decrease is due to the time limit.

Fig. 5 .

 5 Fig. 5.Comparison with the state-of-the-art CP approach on challenging instances of the TSPLIB with a 30, 000-second time limit.

Fig. 6 .

 6 Fig. 6. Evaluation of search heuristics, together with various Last Conflict policies: number of instances among the 36 smallest DCMSTP instances solved within a one-minute time limit. LC_FIRST provides the best results for every heuristic except one.

Fig. 7 .

 7 Fig. 7.Comparison with the state-of-the-art OR approach for the DCMSTP (SOTA)[START_REF] Salles | A hybrid relax-and-cut/branch and cut algorithm for the degree-constrained minimum spanning tree problem[END_REF], with a 30, 000-second time limit. The CHOCO model uses LC_FIRST and MIN_SUP_DEG. The speedup is computed as the solution time of SOTA over the solution time of CHOCO. The instances are sorted by increasing size.

  Maximum 32 39 35 35 38 41 35 27 41 32 39 41 34 36 29 (b) Table representation, with minimum, average, and maximum: LC_FIRST, MIN_DELTA_DEG, and MAX_COST provide the best average results.

									Search
					graph-based			cost-based			relaxation-based
	Last Conflict policy	LEXICO	MIN_INF_DEG	MAX_INF_DEG	MIN_SUP_DEG	MAX_SUP_DEG	MIN_DELTA_DEG	MAX_DELTA_DEG	MIN_COST	MAX_COST	IN_SUPPORT	OUT_SUPPORT	MIN_MAR_COST	MAX_MAR_COST	MIN_REP_COST	MAX_REP_COST	Minimum	Average	Maximum
	NONE	26 33 25 25 29 35	24 24 34	26 26 30 22 31 23 22 27.5 35
	LC_FIRST 32 39 35 33 37 41	35 27 41	32 39 37 34 33 29 27 34.9 41
	LC_BEST	31 38 30 35 38 39	28 27 40	30 36 41 31 36 27 27 33.8 41
	LC_RANDOM 32 38 34 31 37 40	33 27 40	29 36 37 30 33 26 26 33.5 40
	Minimum 26 33 25 25 29 35 24 24 34	26 26 30 22 31 23
	Average	30.3 37.0 31.0 31.0 35.3 38.8 30.0 26.3 38.8 29.3 34.3 36.3 29.3 33.3 26.3