Olivier Cailloux
email: olivier.cailloux@ulb.ac.be

Claude & Lamboray

Philippe Nemery

A taxonomy of clustering procedures

Keywords: Multicriteria clustering, Taxonomy, MCDA, Clustering, Multiple criteria analysis

In the field of multicriteria decision aid, considerable attention has been paid to supervised classification problems, especially to so-called sorting problems, where an order is assumed on the predefined classes. Recently, some non-supervised multicriteria classification procedures, also known as multicriteria clustering procedures, have been proposed aiming to discover data structures from a multicriteria perspective. We enlighten some properties of such approaches and their differences with regards to classical procedures, and we propose a taxonomy of this family of procedures. Moreover, we analyze extend to which these procedures differ from the multicriteria ranking problematic.

Introduction

Classification problems are commonly encountered in various application fields such as health care, biology, finance, marketing, agriculture, etc. [START_REF] Duda | Pattern classification[END_REF][START_REF] Zopounidis | MCDA methodologies for classification and sorting[END_REF]. Two main problems are usually distinguished: the supervised and the unsupervised classification or clustering problem.

In supervised classification problems the purpose is to assign a new object to homogeneous groups (so-called classes) which are defined a priori. We may think for instance about the medical diagnosis problem where a new patient has to be assigned to a known pathology-class on the basis of a set of symptoms. A lot of 1 supervised classification procedures have been proposed such as the k-nearest neighbor algorithm or the Bayes classifier [START_REF] Everitt | Cluster Analysis[END_REF][START_REF] Doreian | Generalized Blockmodeling[END_REF].

On the other hand, there may be no information available about the groups (which are then often called clusters) and the purpose is then to elicit a structure in the data set. For instance, one may consider a marketing problem where the aim is to discover similar customer behaviors in the retail industry. Among the most common clustering procedures, one may cite the K-means, hierarchical or finite mixture densities algorithms [START_REF] Jain | Data clustering: a review[END_REF]. Multicriteria tools have also been considered. Bisdorff proposes an Electre-like clustering procedure based on the L-valued kernels [START_REF] Bisdorff | Electre-like clustering from a pairwise fuzzy proximity index[END_REF].

In the multicriteria decision aid field, a lot of attention has been paid to supervised classification. Moreover, a distinction is made between nominal classification and ordinal classification, also called sorting [START_REF] Zopounidis | Multicriteria classification and sorting methods: A literature review[END_REF]. In the former case, there is no order on the classes whereas in the latter, the classes (also called categories) are completely ordered from the best to the worst. For instance, the evaluation of the creditworthiness of a company is a sorting problem. A bank will assign a request for a new credit into one of the following classes: the classes of accepted credits (the "creditworthy" clients), the classes of clients for which some more information is needed and the classes of refused credits ("untrustworthy" clients). In sorting problems the procedures explicitly take into account preference information (using criteria, weights, indifference and preference thresholds, etc.). Among others, we may cite Electre-Tri [START_REF] Yu | Electre tri: Aspescts méthodologiques et manuel d'utilisation[END_REF], FlowSort [START_REF] Ph | Flowsort: a flow-based sorting method based on limiting or central profiles[END_REF], UTA-DIS [START_REF] Zopounidis | Business failure predictions using the utadis multicriteria analysis method[END_REF].

Recently, some new multicriteria clustering procedures have been proposed who aim to discover data structures from a multicriteria perspective. De Smet and Guzman [START_REF] Smet | Towards multicriteria clustering: An extension of the k-means algorithm[END_REF] and Figueira et al. [START_REF] Figueira | Mcda methods for sorting and clustering problems: Promethee tri and promethee cluster[END_REF] have extended the classical Kmeans in a multicriteria framework, explicitly taking into account a preference structure. The question of the positioning of these new research problems with respect to both the classical clustering field and multicriteria problematics such as ranking has, to the best of our knowledge, not been addressed yet. A first answer is provided in this paper.

To this aim, we define some properties of clustering procedures. The fact of working with criteria instead of attributes (like in classical approaches) is a first distinctive feature that is analyzed. Furthermore, obtaining a partition with a (possibly transitive) relation on the clusters is considered as well. Based on these considerations, we propose a taxonomy of clustering procedures.

Such a clarification opens up some perspectives for designing new multicriteria clustering procedures. We propose some broad strategies to achieve this. Besides, we discuss how such approaches could help a decision maker.

The paper is organized as follows. After having described the general context in which we place in this paper, we describe in section 3 our taxonomy proposition. We first propose a property to distinguish classical clustering from multicriteria clustering, then, propose to distinguish the case where the multicriteria clustering procedure contains a relation, then point the fact that this relation could be transitive, and discuss the particularities of each of these branches. We compare in section 4 the multicriteria clustering to the ranking problematic, and we conclude by suggesting some paths which exploration may prove interresting.

Context

To simplify the context, we will restrict here to the clustering procedures taking attribute values in the set of reals numbers, and we restrict to crisp clustering, i.e. to the procedures assigning an object to exactly one cluster. Let us define the context more precisely.

Definition 1 A real-valued attribute function g, defined in the context of a clustering procedure using a set of actions A = {a 1 , . . . , a n }, is a function taking its input in A and giving an output in R.

We call here "action" what is usually called in the classical clustering domain "object", because the main concern of this paper is the multicriteria domain.

Definition 2 A real-valued clustering procedure is a procedure which takes as input a set A of actions to be clusterized and a set F of real-valued attribute functions, and gives as output a partition ρ on the set of actions, or such a partition ρ and a binary relation on ρ.

We use the symbol F to refer to what is usually called in the multicriteria decision aid field a criteria family. We include in this rather general definition the case where the procedure's output includes a binary relation on the resulting partition. This is needed to include the Relational Multicriteria Clustering procedures, which are defined in Section 3.2.

We will study in this paper the procedures which are deterministic and can be modeled as a function f (A, F) giving the resultant partition ρ (and the resultant partition relation if appliable). Some clustering procedures are not deterministic because they use heuristics to guess the possibly best partition (e.g., K-means). In that case, we will consider a deterministic version of the same procedure which always selects the best partition instead of the one chosen by the heuristic. We thus assume that some algorithm to deterministically break the ties is used. An example of such reasoning applied to a multicriteria clustering procedure is shown in Appendix A.

Taxonomy

Criteria dependency

Some clustering procedures [START_REF] Smet | Towards multicriteria clustering: An extension of the k-means algorithm[END_REF][START_REF] Figueira | Mcda methods for sorting and clustering problems: Promethee tri and promethee cluster[END_REF] have been proposed in the multicriteria decision aid domain. These procedures are a bit particular in the sense that they use criteria instead of attributes. To the best of our knowledge, no formal separation between these procedures and classical clustering procedures (using attributes without preferencial information) has been proposed yet. In this section, we propose a way to differenciate these particular procedures from the classical ones, by the way of a property called "criteria-dependancy".

A criteria is an attribute including a preferential information on the set of considered actions. For example, a criterion g is often defined using a binary transitive relation S g on the set of actions such that for any two actions a and b, we have aS g b if and only if a is preferred or indifferent to b.

In order to include situations where only a binary relation S g is provided to describe a criterion, we assume here that such an ordinal criterion is first numerically represented: if S g is a semi order, then a real-valued function g and a constant ǫ can be defined such that g(a) ≥ g(b) -ǫ iff aS g b. Such a transformation is always possible [START_REF] Pirlot | Semi Orders[END_REF]. The function g can then be considered as an input of any real-valued clustering procedure.

It should be noted that a "direction" of preference on the set of actions can be deduced from the preference information associated with a criterion. For example, a "price" attribute, used for a seller, would become a "sell price" criterion, having the same values as the price, but including the information that it should be maximized. In a multicriteria procedure used by a buyer, the "buying price" (or cost) criterion should rather be used, where it should be minimized.

Formally, such a "criteria-dependant" procedure satisfies the definition given here above and is thus a real-valued clustering procedure. But not all real-valued clustering procedures are criteria-dependant procedures: to be so, a procedure must somehow take into account the criterion-nature of the attributes it is dealing with. This is reflected by the "criteria-dependancy" property that we define hereunder. This property captures the fact that the qualified procedure depends, or not, on the criteria it uses. It is satisfied when the procedure's results sometimes change when the criteria information change.

Let us define the IN V (F, g * ) function, which for any attribute set F and attribute g * ∈ F, transforms F to another set of attributes, similar to the first, but where the attribute g * has been inverted by inverting the sign of its attribute values.

∀F, ∀g

* ∈ F : IN V (F, g * ) = (F \ {g * } ∪ {g * ′ }), where g * ′ (a) = -g * (a) ∀a ∈ A.
In the case where the criterion which we invert has been initially ordinal (only a binary relation S g * is provided), then this construction consistently inverts the order. Assume that aS g * b and therefore build a real-valued function g * such that g * (a) ≥ g * (b) -ǫ. Applying the transformation to g * yields a new criterion function g * ′ such that g * ′ (a) = -g * (a) and g * ′ (b) = -g * (a). That is why we now have that g * ′ (b) ≥ g * ′ (a) -ǫ. The criterion g * ′ then models a semi-order S g * ′ such that bS g * ′ a.

If a clustering procedure does not use the added informations of the criteria, transforming the attributes set using the IN V function will not change the procedure's output. In the opposite case, the procedure's output should change, at least for some input sets, because the countrary would mean that the preferencial information is never really taken into account. It should be noted that the fact that the output changes does not tell us how the criteria information has actually been exploited. An example of a procedure whose output changes when the IN V function is applied is given in Appendix B (see Figures 3 and4).

Definition 3 A real-valued clustering function f is criteria-dependant iff ∃A, F, g * | f (A, F) = f (A, IN V (F, g * )).
Definition 4 A Multicriteria Clustering procedure, or MCC1 procedure, is a real-valued clustering procedure which is criteria-dependant. Otherwize, the procedure is said to be a Classical Clustering procedure.

Having a formal way to distinguish between these two types of procedures has an additional benefit: we can ensure whether a procedure used in the multicriteria domain, such as those ones already published in the literature, is really using the criteria information. Indeed, it is interesting to note that some, if not most, Classical Clustering procedures define their partition quality measure by aggregating distances (which are symetric measures) on each attribute, for example the least-square error quality measure, whereas well-known multicriteria procedures such as PROMETHEE [START_REF] Brans | How to select and how to rank projects: the promethee method[END_REF] (on which PROMETHEE Cluster is based) use a nonsymetric π preference function to discriminate between actions.

It is thus more natural for a Multicriteria Clustering procedure to be criteriadependant than for a classical one. This reasoning is confirmed if looking at the MC-K-means procedure, which is proved to be criteria-dependant in Appendix B. But the link between being called multicriteria, or using non-symetric preference functions such as π, and being criteria-dependant, is not guaranteed, as can be seen by examining the PROMETHEE-Cluster procedure. We prove in Appendix A that this procedure, altough based on PROMETHEE, is in fact not criteria-dependant. Another example of a clearly non criteria-dependent procedure is presented by Bisdorff [Bis02] who, although using multicriteria tools, makes no use of preference directions. Instead, the procedure is based on a symmetric similarity index.

Relational Multicriteria Clustering

Among all the criteria-dependent clustering procedures, the second point of interest is the presence of a relation between the clusters.

In the multicriteria context, actions are generally compared by defining a preference structure. A decision maker who compares two actions may express a preference, an indifference or an incomparability statement between these two actions [START_REF] Roubens | Preference Modeling[END_REF]. It is thus natural to somehow incorporate this information into the clustering results.

Classical clustering procedures typically do not propose a preferencial relation between the obtained clusters because they are not criteria-dependant. Indeed, the absence of preference statements between action pairs makes it difficult to infer a preference statement between two group of actions, i.e. clusters.

On the contrary, one may imagine to enrich a partition obtained by a MCC procedure with a binary preference relation between its clusters.

Definition 5 A Relational Multicriteria Clustering (RMCC) procedure is a MCC procedure which ouputs a partition ρ and a binary relation on ρ.

This relation may for instance be an "at least as good" relation and will be noted S. In a general framework, this permits to obtain preferred, incomparable or indifferent clusters:

C 1 P C 2 means that cluster C 1 is preferred to cluster C 2 (C 1 SC 2 and C 2 ¬SC 1 ), C 1 IC 2 that cluster C 1 is indifferent to C 2 (C 1 SC 2 and C 2 SC 1 ) and C 1 JC 2 that C 1 and C 2 are incomparable (C 1 ¬SC 2 and C 2 ¬SC 1 ).
In the example (see Fig. 1), we have that cluster C1 is preferred to cluster C 3 , C 3 preferred to C 2 and C 2 to C 1 . Finally we have that clusters C 3 and C 4 are indifferent.

Although the extension of the K-means proposed by De Smet and Guzman [START_REF] Smet | Towards multicriteria clustering: An extension of the k-means algorithm[END_REF] (defined in Appendix B) explicitly uses a preference relation between the actions, there does not exist a relation on the clusters. The use of rich preference information as input for achieving a classical "output" induces a loss of information and may be criticized. The two applications given in their paper illustrate this concern. For instance, in the first application, countries are grouped according to their level of creditworthiness. The resulting clusters are then treated as if they were ordered whereas no ordering appears in the results of the procedure.

The following strategy can be pursued in order to obtain a RMCC procedure. First, a classical clustering algorithm (such as the K-means algorithm) is applied on the data such that each cluster can be characterized with a centroid. In a second step, any multicriteria pairwise comparison procedure can be applied on these centroids in order to come up with an "at least as good" relation on the clusters. The outranking relation computed in ELECTRE I [START_REF] Roy | Aide Multicritère à la Décision : Méthodes et Cas[END_REF] can be used for this purpose.

Ordered Multicriteria Clustering

We treat in this section the special case when RMCC procedures always output a transitive relation on the clusters.

Definition 6 An Ordered Multicriteria Clustering (OMCC) procedure is a RMCC procedure which ouputs a partition ρ and a transitive binary relation on ρ.

The transitivity property is special in the sense that it unambiguously implies an order on the clusters. If the relation is complete, then the clusters can be totally ranked. If the relation is not complete, then the transitivity property nevertheless implies a partial ranking, with some incomparable clusters.

OMCC procedures have the advantage over RMCC ones of providing less ambiguous results. However, the decision maker may feel uncomfortable with forcing transitivity. In such case, RMCC procedures would be more suitable. In a multicriteria decision aid context, compare this to either only computing pairwise comparisons (which may lead to a non-transitive relation) or going on and deriving a ranking from these pairwise comparisons.

Ordering clusters can be useful when some hierarchy has to be discovered in the data. Consider for instance the problem where employees, evaluated on various performance measures, have to be clustered. Depending on the data, one may discover for instance three clusters: a cluster with the above average perfoming employees, a cluster with the average performing employees and a cluster with the below average performing employees.

The procedure proposed by Nemery [START_REF] Ph | Multicriteria ordered clustering[END_REF] is an example of what we call OMCC. It combines the ideas of both the clustering and the ranking problematics. First pairwise preference degrees are computed. For any ordered partition, a homogeneity indicator measures to what extend the actions belonging to the same cluster are similar and a heterogeneity indicator measures to what extend the order on the clusters is compatible with the preference degrees.

Apart from this specific procedure, the strategy described in Section 3.2 can also be adapted in order to build OMCC procedures: first, cluster the data, then, rank the centroides using a multicriteria ranking procedure. Conversely, a ranking procedure can be first applied on the data, then an ordered partition compatible with that ranking can be built, effectively splitting up the initial ranking.

OMCC procedures are also useful as a preprocessing step before applying a sorting procedure, such as for instance Electre-Tri [START_REF] Yu | Electre tri: Aspescts méthodologiques et manuel d'utilisation[END_REF]. In fact, the following OMCC procedure could be imagined which is directly based on the sorting procedure. Supose that all the parameters of that sorting procedure, except the parameters defining the classes (for example the reference profiles in the case of Electre-Tri) have been fixed by the decision maker. After generating a set of reference profiles, the sorting procedure can be applied and each action can be assigned to a class. A quality measure needs to be defined which evaluates how "easy" these reference profiles allow to assign the actions. The resulting OMCC procedure is the one which choses the optimal reference profiles set, i.e. the one which yields the best assignments after applying the sorting procedure.

Apart from an ordered partition, such a procedure also provides good reference profiles that come with the optimal ordered partition. This could support a decision maker who would like to use a sorting procedure but is uncomfortable with the definition of the classes.

Comparison with the ranking problematic

Ordered clustering is closely related to the problematic of ranking. According to B. Roy [START_REF] Roy | Méthodologie Multicritère d'Aide à la Décision[END_REF], the ranking problematic consists in partitioning the set of actions into partially or totally ordered equivalence classes. By adopting such a rather general definition, OMCC can be considered as a particular case of the ranking problematic. In fact, an OMCC procedure, which partitions the actions into ordered classes, can very naturally be seen as just another ranking procedure. Despite this apparent similarity between OMCC and ranking, let us however insist on some fundamental differences between these two problems.

On the one hand, a ranking procedure aims at discriminating the different actions. Consequently, a reasonable ranking procedure tends to maximize the number of equivalence classes: the preferred case in a ranking procedure is usually to build a linear order whenever possible. In such a case, the number of classes is maximal since it corresponds to the number of actions. Even if the number of equivalence classes is not always equal to the number of actions, the size of an equivalence class tends to be as small as the input data allows it to be.

On the other hand, a clustering procedure also aims at discriminating the different actions but at the same time it also tries to group together similar actions. Whereas the first objective tends to maximize the number of classes, the second objective tries to minimize it. The clustering solution finally adopted can usu-Reference Type [START_REF] Bisdorff | Electre-like clustering from a pairwise fuzzy proximity index[END_REF] CC [START_REF] Figueira | Mcda methods for sorting and clustering problems: Promethee tri and promethee cluster[END_REF] CC [START_REF] Smet | Towards multicriteria clustering: An extension of the k-means algorithm[END_REF] NRMCC [START_REF] Ph | Multicriteria ordered clustering[END_REF] OMCC Table 1: Some clustering procedures.

ally be seen as a compromise between these two contradictory objectives. This observation will have several consequences.

Let us imagine a trivial problem with one criterion. Applying any reasonable ranking procedure to this data, we expect the output to be exactly the preference relation given by that criterion. Indeed, it is hardly conceivable that two actions are in the same equivalence class in the output ranking when the input data clearly states that the first action is preferred to the second one. Applying a OMCC procedure to the trivial one criterion problem, one could however imagine that the output is different from the initial criterion since some actions can possibly be put together. For example in a problem with three actions, where g(a) = 1, g(b) = 2 and g(c) = 1000, c being preferred by far to b and b being slightly preferred to a, a and b could be put together.

This example shows another difference between a solution obtained with a ranking procedure and one obtained with an OMCC procedure. In the first case, using the semantics of a {P, I, J} preference structure [START_REF] Roubens | Preference Modeling[END_REF], an equivalence class can be interpreted as a set of actions which are indifferent between themselves. Consequently, there is no preference nor incomparability between actions of the same equivalence class. In the second case, there is no clear link anymore between the cluster obtained in the OMCC procedure and such an indifference relation. In the example above, a and b could belong to the same cluster, even so a is preferred to b.

Moreover, in a ranking procedure, the decision maker usually does not fix the number of equivalence classes: it will be implicitly determined by that particular ranking mechanism. It does not usually make sense to fix it because it should be maximized. This is not true in the OMCC domain, where some procedures require to fix the number of clusters in advance.

Conclusion

The taxonomy of clustering procedures which we have presented in this paper is summarized in Figure 2. First criteria-dependency is used to distinguish between Classical Clustering and what we call Multicriteria Clustering. We then further classify MCC procedures into those which do not additionally yield a preference structure on the clusters and those which do. This distinction leads to either Non-Relational Clustering or Relational Clustering. Finally, the transitivity of this possible preference structure on the clusters characterizes Ordered Multicriteria Clustering. We recapitulate in Table 1 how some clustering procedures developped by the multicriteria community fit into this taxonomy.

The main goal of this paper was to clarify the meaning and the distinctive features of Multicriteria Clustering. Criteria-dependency is an important aspect since it imposes that the clustering procedure takes into account the preference scale implied by the criteria. Surprisingly, a procedure such as PROMETHEE Cluster, which nevertheless assumes a criteria input, is not criteria-dependent.

Non-relational Multicriteria Clustering procedures are peculiar since, on the one hand, they take into account the preferential information contained in the criteria, but, on the other hand, they output a result without any preferential information between the clusters. Seen from this angle, the interpretation of the partition obtained by these type of procedures is not entirely clear yet.

Relational Multicriteria Clustering procedures overcome this limitation by providing a preference structure on the clusters. However, only a few RMCC procedures have been proposed so far. The next step will now be to actually develop particular RMCC procedures (OMCC or not), following for instance one of the strategies explained in this paper. This will also help to analyze and understand more easily the results obtained by this type of clustering procedures. For instance, using OMCC procedures raises the question of monotonicity. The impact of improving some evaluations on the resulting ordered partition could be investigated.

Finally, the different types of clustering procedures defined in this taxonomy answer different types of decision problems. These different decision problems still need to be better described and their added value for the decision maker should be more clearly highlighted.

equal-qualities partitions is not important for the proof, as long as the deterministic rule is based solely on the distance measure defined in the procedure and not directly on the criteria values.

Central profiles

Having a cluster C, we note r C the central profile of that cluster. Its evaluation values on each criterion g are computed as the average of the evaluations, on the same criterion, of the actions belonging to the same cluster, as follows:

g(r C ) = 1 |C| a∈C g(a)
, ∀g (where |C| is the number of actions in C).

For a given partition ρ, we note R the set of all central profiles of that partition: R = {r C , ∀C ∈ ρ}. We have |R| = K.

Preference intensities

To each criterion g is associated a preference function f g : R → [0, 1], used to compute the preference intensity P g , P g (x, y) measuring how x is preferred to y.

∀g ∈ F, P g : A ∪ R × A ∪ R → [0, 1] | ∀x, y ∈ A ∪ R : P g (x, y) = f g (g(x) -g(y)) .

Net flow functions

The per criteria net flow is computed using two different formulas.

The per criteria net flow φ R g , for a criterion g and an object a ∈ A, measures to which extend a is preferred over a set of reference objects, from the point of view of g.

φ R g : A → [0, 1] | ∀a ∈ A : φ R g (a) = 1 |R| r * ∈R (P g (a, r * ) -P g (r * , a)) .
The per criterion net flow of an reference action r ∈ R is defined similarily.

φ g : R → [0, 1] | ∀r ∈ R : φ g (r) = 1 |R| -1 r * ∈R \{r} (P g (r, r * ) -P g (r * , r)) .
The authors do not describe the case where |R| = 1. We will thus consider that |R| > 1.

Deviation measure

The per criterion net flow are used to compute the deviation of an action compared to a reference profile:

∀a ∈ A, r ∈ R : d (a, r) = p g∈F w g W φ R g (a) -φ g (r)
p .

Heterogeneity measure

We can now define the heterogeneity measure:

E(ρ) = C∈ρ a∈C d (a, r C ).
The optimal partition ρ is the one minimizing that measure (recall that we assume the procedure has a deterministic way of chosing between ex-aequos).

A.2 PROMETHEE-Cluster is not criteria-dependent

Let us show that ∀A, F, g * :

f (A, F) = f (A, F ′ ), with F ′ = IN V (F, g * ).
This proves that the procedure is not criteria-dependant.

To show that the procedure's output is equal, it is sufficient to show that the distance measure they use are equal. Let us write d ′ , φ R g ′ , φ g ′ , P ′ g the distance measure, the net flow on the action set, the net flow on the reference profiles set, and the preference function computed from the input F ′ . We thus have to show that d (a, r) and d ′ (a, r) are equal ∀F, g * , a, r. To do this we need two intermediary results.

First, we have, ∀x, y ∈ A ∪ R :

P ′ g (x, y) = f g (g(x) -g(y)) = P g (x, y) ∀g = g * , f g (-g(x) -(-g(y))) = f g (g(y) -g(x)) = P g (y, x) for g = g * .
Thus, P ′ g * (x, y)-P ′ g * (y, x) = P g * (y, x)-P g * (x, y) = -P g * (x, y) -P g * (y, x) .

Using that we can deduce a second result.

∀a ∈ A, r ∈ R, g ∈ F: φ R g ′ (a) -φ g ′ (r) = φ R g (a) -φ g (r)
. This is trivially true when g = g * . When g = g * , we have:

φ R g * ′ (a) -φ g * ′ (r) = 1 |R| r * ∈R P ′ g * (a, r * ) -P ′ g * (r * , a) - 1 |R| -1 r * ∈R\{r} P ′ g * (r, r * ) -P ′ g * (r * , r) = 1 |R| r * ∈R -P g * (a, r * ) -P g * (r * , a) - 1 |R| -1 r * ∈R\{r} -P g * (r, r * ) -P g * (r * , r) = 1 |R| r * ∈R P g * (a, r * ) -P g * (r * , a) - 1 |R| -1 r * ∈R\{r} P g * (r, r * ) -P g * (r * , r) = φ R g * (a) -φ g * (r) .
And finally: d

′ (a, r) = p g∈F w g W φ R g ′ (a) -φ g ′ (r) p = p g∈F w g W φ R g (a) -φ g (r) p = d (a, r).

B MC K-means

We analyze in this appendix the procedure, that we call "MC-K-means", defined by De Smet and Guzmàn [START_REF] Smet | Towards multicriteria clustering: An extension of the k-means algorithm[END_REF]. After formally presenting the procedure, we proof by an example that the procedure is criteria-dependent.

B.1 Definition of the procedure

The MC-K-means procedure assumes that a preference structure (P, I, J) has been built on the set of actions A = {a, b, . . .}. A preference structure is a triplet of binary relations, where P models strict prefererence, I indifference and J incomparability. Such a preference structure can be constructed by using a multicriteria decision aid method.

Each action a ∈ A is represented by the sets P + (a), P -(a), I(a) and J(a) containing the actions which are preferred by a, which prefer a, which are indifferent with a and which are incomparable with a: This distance function measures the degree to which the two actions are similar with respect to the other actions. A particularity of this distance is that it does not only depend on the the two actions a and b, but on the whole set of actions A.

Given a subset of actions A ′ ⊆ A, the sets P + (r), P -(r), I(r), and J(r) of a centroid r of A ′ are such that: Furthermore, any action a ∈ A can only belong to one of these four sets. If an action could be assigned to more than one set, one of the possibilities is chosen randomly.

a ∈ P + (r) if |{b ∈ A ′ : bP a}| ≥ max{|{b ∈ A ′ : aP b}|, |{b ∈ A ′ : aIb}|, |{b ∈ A ′ : aJb}|}. a ∈ P -(r) if |{b ∈ A ′ : aP b}| ≥ max{|{b ∈ A ′ :
The algorithm then follows a traditional K-means scheme, but we do not detail it. We assume that the procedure always chooses one of the partitions minimizing the average distances within each cluster (which one is chosen when there are several possibilities is not important for the proof).

B.2 MC K-means is criteria-dependent

We illustrate the procedure on an example with 4 actions which can be found in Figure 3. We use the dominance relation in order to build the (P, I, J) structure.

That is why we have the following sets: In the second clusters, the action d coincides with the centroid and consequently the average distance in that cluster is 0. For this example, another optimal solution with 2 clusters would be {a} and {b, c, d}. In order to check for criteria-dependency, we must assume that the procedure deterministically outputs one of these two partitions. Whatever the tie-breaking mechanism used to chose between these two optimal solutions, we will now see that the procedure is criteria-dependent.

Let us now reverse the criterion on the vertical axis (see Figure 4). The preference structures now change accordingly: Hence this solution is different from the two optimal solutions previously obtained. This illustrates the fact that the procedure is criteria-dependent, whatever the tie-breaking mechanism used to discriminate between multiple optimal solutions.

Figure 1 :

 1 Figure 1: Example of a partition with a relation on the clusters.

Figure 2 :

 2 Figure 2: A taxonomy of clustering procedures.

P

  + (a) = {b ∈ A : aP b}. P -(a) = {b ∈ A : bP a}. I(a) = {b ∈ A : aIb}. J(a) = {b ∈ A : aJb}. A distance between any two action a, b ∈ A is defined as follows: d(a, b) = 1-|P + (a) ∩ P + (b)| + |P -(a) ∩ P -(b)| + |I(a) ∩ I(b)| + |J(a) ∩ J(b)| n .

  bP a}|, |{b ∈ A ′ : aIb}|, |{b ∈ A ′ : aJb}|}. a ∈ I(r) if |{b ∈ A ′ : aIa}| ≥ max{|{b ∈ A ′ : aP b}|, |{b ∈ A ′ : bP a}|, |{b ∈ A ′ : aJb}|}. a ∈ J(r) if |{b ∈ A ′ : aJa}| ≥ max{|{b ∈ A ′ : aP b}|, |{b ∈ A ′ : bP a}|, |{b ∈ A ′ : aIb}|}.

P

  Figure 3: A 2-Cluster solution with four actions.

P

  Figure 4: A 2-Cluster solution with four actions.

We use in this paper the conventional "MC" abbreviation for the word "multicriteria".

Acknowledgment

The authors wish to thank Yves de Smet for his advices. We especially acknowledge his contributions when the reflexions presented in this paper were still at an early stage.

Appendixes

A PROMETHEE Cluster

We show in this appendix that the PROMETHEE Cluster clustering procedure, defined by Figueira et al. [START_REF] Figueira | Mcda methods for sorting and clustering problems: Promethee tri and promethee cluster[END_REF] and slightly modified here to make it deterministic, is not criteria-dependant.

A.1 Definition of the procedure

We first decribe the (modified) PROMETHEE Cluster procedure.

Context

The PROMETHEE Cluster procedure, defined for a given number of clusters K, takes as input a set of actions A and a set of criterion F = {g 1 , . . . , g n } defined on A, and finds the partition ρ on A which minimises the badness criterion E measuring the partition heterogeneity. This section explains how this partition heterogeneity measure E(ρ) is computed.

A partition ρ is a set of clusters. A cluster, denoted by C, is a set of actions.

We warn the reader about the fact that in the original paper, the authors define the PROMETHEE Cluster procedure with a heuristic trying to find the optimal partition (i.e., a K-means using the given deviation measure). As we need a deterministic procedure to apply the criteria-dependance property, we present here a variant which always finds the optimal procedure, and thus do not talk about the heuristic. To make this PROMETHEE Cluster variant deterministic, we also suppose it uses some algorithm to deterministically choose an optimal partition in case of ex-aequo. The way the procedure chooses between these


Olivier Cailloux

Dealing with numerical imprecision in mathematical programs for Electre Tri models disaggregation

Introduction

In this paper, we are interested in decision problems formulated as multicriteria sorting problems, i.e., when a finite number of alternatives from a set A evaluated on a set of criteria {g j , j ∈ J} are to be assigned to one of k predefined ordered categories c 1 ≪ c 2 ≪ ... ≪ c h ≪ ... ≪ c k (c 1 being the worst category, and c k the best one). The assignment is done based on the comparison of the alternatives to external norms, rather than by comparison of the alternatives to each other.

Several approaches have been proposed to address such multicriteria sorting problem [START_REF] Perny | Multicriteria filtering methods based on Concordance/Non-Discordance principles[END_REF][START_REF] Greco | Rough sets methodology for sorting problems in presence of multiple attributes and criteria[END_REF]. We consider a well know multiple criteria sorting method, Electre Tri [START_REF] Figueira | ELECTRE methods[END_REF][START_REF] Mousseau | A user-oriented implementation of the ELECTRE TRI method integrating preference elicitation support[END_REF][START_REF] Roy | The outranking approach and the foundations of ELECTRE methods[END_REF]. More precisely, we consider a variant of the Electre Tri method in line with the axiomatic work of Bouyssou and Marchant [START_REF] Bouyssou | An axiomatic approach to noncompensatory sorting methods in MCDM, I: The case of two categories[END_REF][START_REF] Bouyssou | An axiomatic approach to noncompensatory sorting methods in MCDM, II: more than two categories[END_REF]. This variant assigns alternatives using the alternatives performances and preferential parameters of three types: profiles defining the category limits, weights specifying the importance of each criterion, and veto thresholds. To support specifying their preferences, we suppose that the DMs are able to provide assignment examples, i.e. alternatives (fictitious or real) associated to the categories the DMs think they belong to. Such assignment examples can correspond to past decision records or be expressed directly by DMs.

Most of the work on preference elicitation in Multicriteria Decision Aid focuses on representing the preferences of a single decision maker (DM). We are interested in elicitation procedures for multiple DMs that make it possible for each DM to provide individual preference information in order to build a multiple criteria sorting model accepted by each DM as representing the group preferences. We present linear programs able to find, on the basis of assignment examples provided by DMs, common profiles, shared among all the DMs, but allowing their weights (criteria importance factors) to vary individually. This can be used as a first step towards reaching an agreement on a preference model.

In a recent paper [START_REF] Cailloux | Eliciting ELECTRE TRI category limits for a group of decision makers[END_REF], three linear and mixed integer programs solving the following problems are described. ICL, or Infer Category Limits, finds, if possible, a set of profiles such that it is possible to satisfy the assignment examples of each DM using individual weights and majority threshold parameters without using veto thresholds.

ICLV, or Infer Category Limits with Vetoes, finds, if possible, a set of profiles such that it is possible to satisfy the assignment examples of each DM using individual weights and majority threshold parameters and using veto thresholds if necessary. This is a generalization of the first program but they are presented in order of increasing complexity.

CWR, or Compute Weights Restrictions, having fixed a set of shared profiles, computes a measure indicating the remaining latitude for each DM regarding their possibility of choosing the weights ordering on the criteria.

These inference programs may be used in a process aiming to build a consensus by progressively reaching a common preferential model. These tools should be combined with other decision aiding tools, therefore allowing to build a comprehensive decision aiding process.

This technical report is mainly based on the disaggregation programs proposed in that paper, which should be read before reading this report. (First part of this introduction is reproduced from that article.) The MPs have been implemented in J-MCDA, an open source software for Multicriteria Decision Aiding (MCDA). This document gives detailed technical informations about how the Electre Tri disaggregation programs proposed in the companion article have been implemented, including choice of constants and strategies to avoid numerical errors.

More generally, several articles have appeared proposing Linear Programs (LPs) and Mixed Integer Programs (MIPs) that aim to obtain Electre Tri like preference models on the basis of assignment examples from the Decision Makers (DMs). Most often, the articles do not include discussions concerning the problem of numerical imprecision, hence, implementing the proposed Mathematical Programs (MPs) correctly can be difficult. It is the opinion of the author of this document that the current situation where articles are often published with no sufficient technical details to enable easy implementation is not fully satisfactory. This hinders possibility to reproduce or exploit the published results. Determining relevant technical informations can be very time consuming, and in the current situation, it may be considered that the usual quality assessment process in the OR community (perhaps also in other scientific communities) do not sufficently value such work. More generally, it might be considered important to ease reproducibility of the published results. Suggestions to improve the situation include favoring development of open standards for data exchange, and mandating their use when applicable; favoring development of open source softwares.

Numerical errors and mathematical programs

Koch et al. [START_REF] Koch | MIPLIB 2010[END_REF] gives a good overview of problems related to numerical imprecision when solving mathematical programs. The following paragraph is reproduced from their section 3.1.

Most MIP solvers (. . . ) are based on floating-point arithmetic and work with tolerances to check solutions for feasibility and to decide on optimality. In their feasibility tests, solvers typically consider absolute tolerances for the integrality constraints and relative ones for linear constraints. Some normalize the activity of linear constraints individually, others directly scale the constraint matrix. The tolerances affect solution times and solution accuracy, normally in opposite ways (. . . ). If one fixes all integer variables from the reported solution to the closest integer value and recomputes the continuous variables by solving the resulting LP with exact arithmetic, some of these post-processed solutions turn out to be infeasible with respect to exact arithmetic and zero tolerances. (. . . ) [This means] that the computed solution lies outside the feasible area described by the input file, but inside the extended feasible area created by reading in the problem and introducing tolerances.

This document refers to such situation where the solver considers some values as satisfying some constraints when these values, in exact arithmetic, do not satisfy the constraints, as a situation of numerical error. In the problems we are concerned with, such numerical errors may have important consequences. The MPs considered in this document are designed to satisfy all assignment examples from the DMs. If no particular measures are taken against numerical errors, a solver may report a solution which it considers feasible but which, when applied again to the original problem, does not satisfy all assignment examples.

In order to avoid such numerical errors, this document describes how some constraints must be modified by adding appropriate tolerance values. It also describes how the constants the MPs use should be chosen to make sure their use do not artificially reduce the set of feasible solutions. Finally, it includes some simple extentions and optimizations reducing the size of the resulting MP that have not been included in the companion article for simplicity. Tags have been added to constraints following the names used in the source code and displayed in files that can be exported from the library.

Constants used in the programs

• g j and g j , the worst and best performances on the criterion j. Defining g j lower than the worst performance on the criterion j is also acceptable, it must only represent a lower bound on the performances reached by any alternative on that criterion. Similar remark holds for g j .

• ∀j ∈ J : δ j , a value smaller than the minimal difference between any two different performances on j (∀j ∈ J : min j = min a,a ′ ∈A |g j (a) -g j (a ′ )|) divided by k. This leaves space to fit k -1 profiles into the interval [g j (a), g j (a ′ )] corresponding to any two different alternatives performances on j and separating each profile by δ j . If there are no two different performances for a given criterion, δ j is defined arbitrarily to 1. It is used to transform strict inequality constraints into loose constraints in Constraints (b, increase), (C, floor), (C, ceiling), (V , floor), (V , ceiling), (V , used). We used min j /(k + 1).

• ∀j ∈ J : δ b j , the "profile margin", maximal separation between the extreme profiles (resp. best and worst) and the extreme performances (resp. g j and g j ). We want to let the successive profiles be at least δ j apart from each other, and at least δ j apart from the extreme performances, thus, δ b j must be defined so that δ b j ≥ (k -1)δ j , in order to let all profiles be greater than the best performance, or lower than the worst performance, if necessary. We used δ b j = kδ j . It is used to define the bounds of the profiles b 1 and b k-1 , and indirectly in constraints involving M j .

• ∀j ∈ J : M j = g j -g j + δ b j , a scaling factor representing the maximal performance difference on the criterion j including one extreme profile. It is used in Constraints (C, floor), (C, ceiling), (V , floor), (V , ceiling), (V , used).

• δ λ , an arbitrary small positive value, used in Constraints (support, ceiling) and (support, ceiling-v). We used δ λ = 0.001.

• δ v j , a value used in the definition of the veto variables ranges and in Constraints (V , ceiling), which must be greater than δ j . We used δ j * 2.

2 Infer Profiles (IP)

Stating the problem

Having a set of alternatives A, categories c 1 , . . . , c h , . . . , c k ordered by preference where c 1 is the least preferred one, a set of profiles B = {b 1 , . . . , b k-1 }, where b h is the upper profile to category c h and lower profile to category c h+1 , a set of criteria indices J, the evaluations of the alternatives g j (a), ∀a ∈ A, j ∈ J, a set of DMs L, assignment examples E l , the goal of IP is to determine the performances of profiles g j (b h ), ∀j ∈ J, 1 ≤ h ≤ k -1 shared among the DMs, together with individual weights w l j and majority thresholds λ l , matching all assignment examples. For each DM l ∈ L, the set of examples E l is the set of pairs (a, b h ) ∈ A× B specifying that the alternative a is assigned to the category c h by l. We write (a -→ l h) to denote such an assignment example.

Our programs are designed to be correctly defined if k = 1. It is useful to have a working program working even in such a trivial case for testing purposes and to make it as general as possible.

Note that the lowest profile, b 0 , must be outranked by every alternative (because they must go into at least category c 1 , the worst one) and hence the performances g j (b 0 ) on every criterion necessarily consist in performances lower than every other performances on the same criterion. The upper profile of the best category, that would be b k , is used only when an other assignment procedure known as the optimistic procedure is used. Therefore, the lowest and best profiles are not considered in our inference programs. Satisfying these assignment examples can be written as follows:

∀l ∈ L : ∀(a -→ l h) ∈ E l : j∈J:gj (a)≥gj (b h-1 ) w l j ≥ λ l , and (1)
∀l ∈ L : ∀(a -→ l h) ∈ E l : j∈J:gj (a)≥gj (b h ) w l j < λ l . (2)
Equation (1) ensures that the example alternative is assigned to a category at least as good as c h , and (2) makes sure that it is assigned to a category not better than c h . Hereafter we present a mathematical program finding adequate profiles without using veto thresholds. The case where veto thresholds are allowed is considered later in Section 3.

0 1 -M j 0 M j g j (a) -g j (b h ) C j C j = 1/M j * (g j (a) -g j (b h )) + 1 C j = 1/M j * (g j (a) -g j (b h )) ✇ ♦ × Figure 1: constraining C j to the appropriate value 2.2 Constraints ∀j ∈ J, a ∈ A, 1 ≤ h ≤ k -1: 1 M j (g j (a) -g j (b h )) < C j (a, b h ), (3)
C j (a, b h ) ≤ 1 M j (g j (a) -g j (b h )) + 1. (4)
Constraints ( 3) and ( 4) define C j (a, b h ), binary variables indicating the agreement of the criterion j to say that a is at least as good as b h . See Figure 1. In order to transform (3) into a non strict inequality, δ j may be used. It is defined so that adding this value to the constraint does not restrict the set of acceptable values for g j (b h ). It is used to change the strict inequality to a loose inequality:

∀j ∈ J, a ∈ A, 1 ≤ h ≤ k -1, 1 M j + δ j (g j (a) -g j (b h ) + δ j ) ≤ C j (a, b h ). (C, floor)
Constraints (4) are exposed to numerical errors. The solver could find a solution with g j (b h ) = g j (a) + ε, for some alternative a, criterion j, profile b h , with ε a small positive value, and consider C j (a, b h ) = 1 although C j (a, b h ) should equal zero as the profile value is higher than the alternative performance. This is so because it could happen that

C j (a, b h ) = 1 satisfies the constraint (4) stating that C j (a, b h ) ≤ -ε
Mj + 1 because of the solver tolerance. To avoid this situation, Constraints (4) should be transformed to

C j (a, b h ) ≤ 1 M j + x j (g j (a) -g j (b h ) -x j ) + 1. (C, ceiling)
Having t the tolerance for integer values used by the solver, xj Mj +xj should be at least t, thus x j ≥ (M j + x j )t. This makes the constraint stronger, as it now holds that g j (a) < g j (b h ) + x j ⇒ C j (a, b h ) = 0. The new constraint form prevents situations where g j (b h ) < g j (a) < g j (b h ) + x j , thus, prevents to choose the performance of the profile such that ∃a ∈ A | g j (a)-x j < g j (b h ) < g j (a). In 0

w j 1 0 1 C j σ j σ j = C j σ j = C j + w j -1 • ( ✻ ❄ ❡ Figure 2
: constraining σ l j to the appropriate value order to avoid reducing the feasible solution space, x j has to be small enough.

A practical solution is to take x j = δ j . For this solution to be implementable, it must hold that δj Mj +δj ≥ t, ∀j ∈ J. For example, the CPLEX solver version 12.3 uses by default t = 1 10 5 . This implies that the proposed strategy does not apply if the proportion of the minimal difference over the maximal difference of performance is too small. A solution to this problem is to rescale the data. An alternative strategy is to avoid using the values given by the solver for g j (b h ), instead of changing constraint (4). The profiles evaluations may instead be deduced from the solver values for C j (a, b h ). This may be a better strategy as it imposes no restriction on the input data, but it requires more efforts to implement.

The following constraints are used to define the variables σ l j (a, b h ). These variables are defined as non negative. ∀l ∈ L, j ∈ J, a ∈ A * , 1 ≤ h ≤ k -1:

       σ l j (a, b h ) ≤ C j (a, b h ) σ l j (a, b h ) ≤ w l j C j (a, b h ) -1 + w l j ≤ σ l j (a, b h ). (σ, ceiling C) (σ, ceiling w) (σ, bottom)
These variables represent the sum of the support for saying that a is at least as good as b h . The constraints ensure that σ l j (a, b h ) = w l j C j (a, b h ) while avoiding the use of a non-linear expression. See also Figure 2.

Then we need to ensure that the sum of supports for each examples are lower and greater than the related majority thresholds (Constraints ( 5), ( 6)).

∀l ∈ L, ∀(a -→ l h) ∈ E l , h > 1 : j∈J σ l j (a, b h-1 ) ≥ λ l . ( 5
) ∀l ∈ L, ∀(a -→ l h) ∈ E l , h ≤ k -1 : j∈J σ l j (a, b h ) ≤ λ l -δ λ , (6)
Constraints (5) are subject to numerical errors. It is possible (and it has been observed with CPLEX) that j∈J σ l j (a, b h-1 ) = λ l -ε, for a given a, h, l, with a small positive ε value, such that the solver considers the constraint is satisfied when it is strictly speaking not. Modifying the constraint by adding a small positive δ ′ λ is not a good solution because it would restrict the feasible space, in particular it would exclude solutions where λ = 0.5 involving two disjoint winning coalitions. Moreover, this problem requires a more general solution. Even when no MP is involved, imprecision may be introduced when reading the weights values from a file, or obtaining them from an other source, or when computing the sum itself, so that the computed sum of weights may well be slightly below the λ value even though the true weight values may be greater than or equal to λ. The solution we adopted for this general problem is the following. When comparing the sum of weight values to the majority threshold λ, we use a small tolerance margin ε (configurable in our library). If j∈J|gj (a)≥gj (b h ) w j ≥ λ l -ε, we consider that the alternative outranks the profile, as if j∈J|gj (a)≥gj (b h ) w j (a, b h-1 ) ≥ λ l held. This requires to make sure that the true weight values (considering no numerical imprecision) are such that no coalitions have a value in [λ -ε, λ[, otherwize the tolerance margin modifies the intended result. In the case of the MP, suffices to take ε < δ λ (we suggest ε = δ λ /2), because Constraints (6) make sure that either the coalition is less than or equal to λ l -δ λ , or it should be considered as a winning coalition. This solves the MP imprecision problem as long as ε > t, with t the imprecision tolerance used by the solver for linear constraints (CPLEX version 12.3 uses t = 1 10 6 by default). One problem remains when using this strategy. The weights solution values taken from the solver solution to the MP have to be interpreted using an appropriate ε value, that the user has to know. A solution to that problem would be to recompute equivalent weight and λ values (not posing any numerical imprecision risk), that have the same winning coalitions, and show the recomputed values to the user instead of the direct values from the solver.

Constraint (weights, sum) ensure that the weights sum to one. ∀l ∈ L:

j∈J w l j = 1.
(weights, sum) This is obviously subject to numerical imprecision, but it is very unlikely to cause any practical problem. Constraints (b, increase) make sure that the profiles are ordered correctly.

∀j ∈ J, 2 ≤ h ≤ k -1: g j (b h-1 ) ≤ g j (b h ) -δ j . (b, increase)
Ensuring that the profiles are separated by δ j permits to avoid numerical errors where a profile would be higher than a worst one by a very small margin such as 1e-10. Separating them by δ j does not restrict the possibility that they are semantically equal, as that value is small enough. Observe that it is therefore possible that two profiles have semantically equal performance on all criteria, thus are exactly the same. A necessary condition for this to happen is that at least one category has no assignment examples. Finally, note that it is necessary to define the bounds of the profiles (if k ≥ 2), to be able to use the scaling constants in the rest of the program. The bounds must be defined only for the worst and best profiles as Constraints (b, increase) ensure that the other profiles also satisfy the bounds. Bounds are defined as follows, ∀j ∈ J: g j -δ b j ≤ g j (b 1 ), g j (b k-1 ) ≤ g j + δ b j .

Using intervals instead of crisp assignments

The user may wish to provide assignment examples in the form of a contiguous interval of categories where an alternative may be assigned to, instead of a single category. In the case of continuous intervals, the mathematical program is easily transformed. If the assignments were allowed to be non contiguous, e.g. alternative a may go to category 1 or 3, the change would be more complex. Now E l contains, for each example involving an alternative a, two pairs (a, h) with the lowest and highest category the alternative may be assigned to. Let us write (a -→ l h) and (a -→ l h) the lower category and the upper category the alternative a should be assigned to according to the decision maker l. Note that (a -→ l h) = (a -→ l h) is possible, if the alternative is to be assigned into a single category. This change requires to modify Constraints ( 5) and [START_REF] Koch | MIPLIB 2010[END_REF].

∀l ∈ L, ∀(a -→ l h) ∈ E l , h ≥ 2: j∈J σ l j (a, b h-1 ) ≥ λ l . (support, floor) ∀l ∈ L, ∀(a -→ l h) ∈ E l , h ≤ k -1: j∈J σ l j (a, b h ) ≤ λ l -δ λ .
(support, ceiling)

Objective function

If we want to maximize the separation between the sum of support and the majority thresholds, we may maximize a slack variable s as objective of the MIP and replace Constraints (support, floor) and (support, ceiling) with the following ones. ∀l ∈ L, ∀(a -→

l h) ∈ E l , h ≥ 2: j∈J σ l j (a, b h-1 ) ≥ λ l + s,
and ∀l ∈ L, ∀(a -→ l h) ∈ E l , h ≤ k -1: j∈J σ l j (a, b h ) + s ≤ λ l -δ λ .

Reduced mathematical program

The following program uses less constraints than what has been described previously by using the fact that only the technical variables required to ensure satisfaction of the assignment examples are necessary. It is thus possible to reduce the size of the program. For example, it is not necessary to define C j (a, b h ) variables for each alternative a and profile b h . Let us note P l the set of pairs of alternatives and profiles that we have to consider to satisfy assignment examples of DM l. For each assignment example (a -→ l h), if h ≥ 2, we have to consider the comparison of a to b h-1 to make sure alternative a is at least as good as the profile and can reach category h. Similarily, for each assignment example (a -→ l h), if h ≤ k -1, the pair (a, b h ) must be considered. Finally, we have:

P l = (a, b h-1 ), ∀(a -→ l h) ∈ E l , h ≥ 2 , P l = (a, b h ), ∀(a -→ l h) ∈ E l , h ≤ k -1 , P l = P l ∪ P l .
Having a set of alternatives A, a set of criteria indices J, the evaluations of the alternatives g j (a), ∀a ∈ A, j ∈ J, the number of categories k, a set of DMs L, assignment examples E l , determine the performances of the profiles g j (b h ), ∀j ∈ J, 1 ≤ h ≤ k -1, together with individual weights w l j and majority thresholds λ l , satisfying the following constraints.

∀l ∈ L:

j∈J w l j = 1. (weights, sum) ∀j ∈ J, 2 ≤ h ≤ k -1: g j (b h-1 ) ≤ g j (b h ) -δ j . (b, increase) ∀l ∈ L, (a, b h ) ∈ P l , j ∈ J:          1 M j + δ j (g j (a) -g j (b h ) + δ j ) ≤ C j (a, b h ), C j (a, b h ) ≤ 1 M j + δ j (g j (a) -g j (b h ) -δ j ) + 1. (C, floor) (C, ceiling) ∀l ∈ L, (a, b h ) ∈ P l , j ∈ J:        C j (a, b h ) + w l j -1 ≤ σ l j (a, b h ), σ l j (a, b h ) ≤ C j (a, b h ), σ l j (a, b h ) ≤ w l j .
(σ, floor)

(σ, ceiling C) (σ, ceiling w) ∀l ∈ L, (a, b h ) ∈ P l : j∈J σ l j (a, b h ) ≥ λ l . (support, floor) ∀l ∈ L, (a, b h ) ∈ P l : j∈J σ l j (a, b h ) ≤ λ l -δ λ .
(support, ceiling)

The constants g j , g j , M j , δ j , δ b j , and δ λ are defined in Section 1.2. The variables C j (a, b h ) are binaries, g j (b h ) are real, with g j -δ b j ≤ g j (b 1 ) and g j (b k-1 ) ≤ g j + δ b j , w l j and σ l j (a, b h ) are real and non negative, λ l are in [0.5, 1].

Infer Profiles with Vetoes (IPV)

Suppose now that the DMs are ready to accept veto thresholds in the individual preference models, i.e. when searching for common profiles, it is deemed acceptable to use shared veto thresholds to satisfy the individual assignment examples. This can enable to find common profiles in situations where it would not be possible to satisfy all examples without vetoes. This program can be seen as a generalization of the previous one, except for the change in the objective function, as it tries to find solutions having zero vetoes. However we choose to present the programs in an increasing order of complexity. For simplicity, we also consider that the DMs share the vetoes. The same approach would be applicable for searching individual vetoes, with an objective function that could e.g. minimize the number of individual vetoes used or minimize the number of DMs using some vetoes. Sharing the vetoes also reduces the number of binary variables and reduces the risk that the resulting preference model would overfit the provided data.

The mathematical program is based on the previous one, with a few additions and changes. The veto situations are modeled as follows: a veto threshold v h j (a variable in our problem) is associated with each of the criteria j ∈ J and profile index 1 ≤ h ≤ k -1. We also need binary variables V j (a, b h ), ∀j ∈ J, a ∈ A, 1 ≤ h ≤ k -1, equal to one iff there is a veto situation between a and b h . When for any criterion and profile the evaluation g j (a) is strictly lower than the corresponding v h j veto threshold, the alternative may not outrank the profile. Not using a veto threshold is equivalent to setting v h j < g j , the worst performances on the criterion j. We thus define the variables v h j as having a range g j -δ v j ≤ v h j ≤ g j (b h ), where δ v j > δ j . The implementation uses a more classical definition of the veto. E.g. Roy [START_REF] Roy | The outranking approach and the foundations of ELECTRE methods[END_REF] defines a veto threshold r j ≥ p j , with p j > 0 the preference threshold, which prevents a from outranking b iff g j (a) < g j (b) -r j . In our implementation

v h j = g j (b h ) -v h j (or: v h j = g j (b h ) -v h j
). An alternative a may not go into category h if g j (b h ) -g j (a) > v h j , which is equivalent to g j (a) < v h j . Thus, not using a veto threshold is equivalent to setting v h j ≥ g j (b h ) -g j , and the variables v h j must have a range defined as at least 0 ≤ v h j ≤ g j (b h )-g j +δ v j , with δ v j > δ j . We choose to define all upper bound for variables v h j as v h j ≤ M j + δ v j , for simplicity. Using a classical definition of the veto makes it more efficient to implement the case of constant veto thresholds, where the value of v h j does not depend on h.

In order to clarify the relation between the implementation and the companion article, the following subsection gives both form of constraints, those with the companion article definition of the veto v h j and those with the implementation definition of the veto v h j .

Additional constraints

∀j ∈ J, 2 ≤ h ≤ k -1: v h-1 j ≤ v h j
ensures that the veto thresholds are correctly ordered. Equivalently:

v h j -v h-1 j ≤ g j (b h ) -g j (b h-1 ). (v, order)
The following constraints define the binary variables V j (a, b h ) indicating the existence of a veto involving alternative a and category h. ∀j ∈ J, a ∈ A,

1 ≤ h ≤ k -1: v h j -g j (a) + δ j M j + δ j ≤ V j (a, b h ) ≤ v h j -g j (a) 2M j + δ v j + 1,
or equivalently:

g j (b h ) -g j (a) -v h j + δ j M j + δ j ≤ V j (a, b h ), (V , floor) V j (a, b h ) ≤ g j (b h ) -g j (a) -v h j -δ j 2M j + δ v j + δ j + 1. (V , ceiling) Note that g j (b h ) -g j (a) -v h j ∈ [-2M j -δ v j , M j ]
. Substracting δ j in (V , ceiling) permits to avoid numerical errors: (V , floor) and (V , ceiling) together forbid that there exists g j (b h ) -g j (a) = v h j , therefore allowing a security margin for numerical imprecision.

∀l ∈ L, ∀(a -→ l h) ∈ E l , h ≥ 2: j∈J σ l j (a, b h-1 ) ≥ λ l + j∈J V j (a, b h-1 ). (support, floor-v) ∀l ∈ L, ∀(a -→ l h) ∈ E l , h ≤ k -1: j∈J σ l j (a, b h ) ≤ λ l -δ λ + j∈J V j (a, b h ). (support, ceiling-v)
Constraints (support, floor-v), (support, ceiling-v) take the veto into account when computing the assignments. j∈J V j (a, b h ) accounts for the existence of a veto situation between a and b h .

To minimize the number of vetoes used, we need a binary variable for each criterion, V j , capturing the fact that a veto is used for this criterion. The following sufficient condition for considering that a veto is not used holds, ∀j ∈ J,

1 ≤ h ≤ k -1: v h j < g j ⇒ V j = 0.
Thanks to the ordering of the vetoes (Constraints (v, order)), it can be refined as it must hold only for h = k -1. In the linear model we only need to constrain V j to one if necessary, thus having defined V j as a binary variable, ∀j ∈ J:

V j ≥ v k-1 j -g j + δ j M j + δ j ,
or equivalently:

V j ≥ g j (b k-1 ) -g j + δ j -v k-1 j M j + δ j . (V , used)
This formulation is much more economical than the formulation used in the companion paper (V j ≥ V j (a, b h ), ∀a, h), but requires more justification. Let us say that a veto, associated to a profile b h and criterion j, is possibly used iff v h j ≥ g j (b h ) -g j . By this phrase we mean that the veto is defined to a value which, considering g j is the lowest possible value on the scale of performances of j, makes it possibly intervene to veto an outranking situation. If the performance g j is reached by some alternative in the set of alternatives used as example, then the veto value v h j is reached by that alternative. If the veto value v h j is reached by at least one alternative, we say that the veto is used. Note that is an abuse of language, because it might be that the veto is not necessary for the outranking situation not to hold. If the veto is necessary to prevent the outranking situation for at least one alternative in the example alternative set, that is, if the concordance is greater than or equal to the majority threshold for the relevant alternative and profile, we say that the veto is useful. Recall we authorize g j to be lower than all alternatives evaluations.

It follows from Constraints (V , used) that if a veto is possibly used, then V j = 1 and if V j = 0, then no veto is possibly used, thus, no veto is ever used, for criterion j. The V j variables should be defined if and only if the objective function includes minimizing the number of vetoes. Thanks to that objective, V j = 1 requires that the veto on criterion j is useful. We also have that useful implies possibly used, thus it holds that V j = 1 iff the veto on criterion j is useful.

Should the user want to search for preference models where some criteria are forbidden to use a veto, it is possible to force non use of a veto for a given criterion j by constraining the value of v k-1 j to be at least g j (b k-1 ) -g j , or v k-1 j ≥ M j , or by simply not defining relevant v k-1 j and V j variables. Note also that it is meaningless to force V j to one: supplementary constraints would be needed to make sure the veto is used. In the implementation, it is also possible to constrain a veto threshold to some value. This is implemented by simply restricting the range of the appropriate v h j variable. It does not guarantee that the veto is indeed useful. Remark that forcing the value of v h j would be a problem if the choice of g j (b h ) would lead to g j (b h ) -g j ≤ v h j < g j (b h ) -g j + δ v j . In that case we would have V j = 1 although the veto would be unused. However, this situation will not happen because the objective is to minimize the sum of the V j variables, therefore leading the solver to choose a value for g j (b h ) which does not cause this situation. This also shows why these constraints should be used only if the objective involves minimizing the sum of the V j variables.

Nul weights and veto thresholds

Procedures based on Electre Tri take different decisions, depending on the variant used, when a veto is bound to a criterion j having a nul weight. An ambiguous situation happens when the concordance, thus the sum of weights of the criteria in favor of an alternative a being at least as good as a profile b h , equals one, and criterion j has a veto against that affirmation. In the original Electre Tri definition [START_REF] Roy | The outranking approach and the foundations of ELECTRE methods[END_REF], a concordance of one is a sufficient condition to determine outranking, which opposes the rule that the veto should make outranking impossible. If a veto can be defined on a nul weight criterion, such an ambiguous condition may happen. Let us qualify a solution involving at least one criterion where a veto is defined and having a nul weight as a solution with zero-weight vetoes. In the recently axiomatized version of Electre Tri [START_REF] Bouyssou | An axiomatic approach to noncompensatory sorting methods in MCDM, I: The case of two categories[END_REF][START_REF] Bouyssou | An axiomatic approach to noncompensatory sorting methods in MCDM, II: more than two categories[END_REF], it is admitted that a veto is defined on a criterion which has no role in any winning coalition. In such a case, the veto plays its role, forbidding the outranking result. In our implementation, the question arises whether such a situation should be allowed. We decide that if a veto is defined on a zero weight threshold, it should play its role and veto the outranking, as suggested by Bouyssou and Marchant. With such a decision, let us show that by forbidding zero-weight vetoes, we do not reduce expressiveness of the model, or conversely, adding such a possibility does not augment the expressiveness of the model. We must show that if no solution exists without zero-weights vetoes, then no solution exists allowing zero-weight vetoes. Conversely, let us show that if a solution exists involving zero-weight vetoes, then a solution exists without zero-weight vetoes.

Consider an Electre Tri preference model M involving zero-weight vetoes, let us transform it to M ′ which does not involve zero-weight vetoes and is equivalent, thus sorts all possible alternatives to the same categories. Let us note j a criterion with zero weight and a veto in M . We show how to transform the solution to an equivalent one in which j has a non zero weight. If several criteria have zero weight and a veto, the procedure may be repeated.

Let us note the vetoes and profile levels in M bound to criterion j as v h j and g j (b h ), ∀h. As criterion j has zero weight, the profiles may be transformed to any values g ′ j (b h ), for all h, keeping the resulting model equivalent to the original one. We may also choose new veto values v ′h j but the vetoes must operate in the same conditions, otherwise the transformed solution is not equivalent to the one found, thus we must have g

′ j (b h ) -v ′h j close enough to g j (b h ) -v h j . Define g ′ j (b h ) = g j (b h ) -v h j
and v ′h j = 0, so that the veto occurs for a category h and alternative a exactly when the alternative is less good than the corresponding profile according to j. It is then possible to associate a non nul weight to the criterion j. When the criterion is not in favor of a > b, its weight does not matter as the veto will be decisive. In all cases where its weight matter, it will be part of the winning coalition. We may thus give this criterion any weight (e.g., 0.1), and raise the majority threshold by the same value.

The above result proves that forbidding vetoes on zero-weight criteria does not reduce the set of feasible solutions when a single preference model is involved. Observe however that this holds in the case of a single DM. In our case of multiple DMs sharing profiles, adding such constraints could reduce the set of feasible solution. We therefore chose to authorize solutions involving zero-weight vetoes.

Objective function

In most situations it is probably reasonable to find a solution involving the least possible number of vetoes: allowing too many veto thresholds to be used may lead to an over-fitting of the model with ad-hoc veto thresholds. The objective function should then be to minimize the sum of the V j variables:

min j∈J V j .
An alternative could be e.g. to minimize the number of situations where a veto is used.

Reduced mathematical program

Having a set of alternatives A, a set of criteria indices J, the evaluations of the alternatives g j (a), ∀a ∈ A, j ∈ J, the number of categories k, a set of DMs L, assignment examples E l , determine the performances of the profiles g j (b h ) and veto levels v h j , ∀j ∈ J, 1 ≤ h ≤ k -1, together with individual weights w l j and majority thresholds λ l , minimizing j∈J V j subject to the following constraints. Note that this MP is also smaller than the one published in the companion article.

∀l ∈ L:

v h j -v h-1 j ≤ g j (b h ) -g j (b h-1 ).
(v, order) ∀l ∈ L, (a, b h ) ∈ P l , j ∈ J: (support, ceiling-v) ∀j ∈ J:

           g j (b h ) -g j (a) -v h j + δ j M j + δ j ≤ V j (a, b h ), V j (a, b h ) ≤ g j (b h ) -g j (a) -v h j -δ j 2M j + δ v j + δ j
V j ≥ g j (b k-1 ) -g j + δ jv k-1 j M j + δ j .

(V , used)

The constants g j , g j , M j , δ j , δ b j , δ v j and δ λ are defined in Section 1.2. The variables C j (a, b h ), V j (a, b h ) and V j are binaries, g j (b h ) are real, with g j -δ b j ≤ g j (b 1 ) and g j (b k-1 ) ≤ g j + δ b j , w l j , σ l j (a, b h ) are real and non negative, λ l are in [0.5, 1], v h j are in [0, M j + δ v j ].

Conclusion

We have presented in this techical report implementation details permitting to formulate several disaggregation programs as MPs while taking into account numerical imprecision thresholds used by solvers. The report also presents reduced MPs that permit a more efficient implementation than the one which was previously published. These algorithms are available in J-MCDA, a free (libre) open source software library. The report uses, as much as possible, the same technical terms and notations as are used in the source code and it may therefore also be useful as a detailed code documentation.

As is mentioned in the companion paper, some instance sizes are not currently solvable in a reasonable time using this approach. For example, instances involving more than eight criteria remain difficult to solve. One possibility to reduce the resolution time is to design resolution algorithms making use of the specific structure of the problems to solve. This is left for future work.

1 MC

 1 sum) ∀j ∈ J, 2 ≤ h ≤ k -1: g j (b h-1 ) ≤ g j (b h ) -δ j .(b, increase)∀l ∈ L, (a, b h ) ∈ P l , j ∈ J: j + δ j (g j (a) -g j (b h ) + δ j ) ≤ C j (a, b h ), C j (a, b h ) ≤ 1 M j + δ j (g j (a) -g j (b h ) -δ j ) + 1. (C, floor) (C, ceiling) ∀l ∈ L, (a, b h ) ∈ P l , j ∈ J: j (a, b h ) + w l j -1 ≤ σ l j (a, b h ), σ l j (a, b h ) ≤ C j (a, b h ), σ l j (a, b h ) ≤ w l j .(σ, floor) (σ, ceiling C) (σ, ceiling w) ∀j ∈ J, 2 ≤ h ≤ k -1:

  , (a, b h ) ∈ P l : j∈J σ l j (a, b h ) ≥ λ l + j∈J V j (a, b h ). (support, floor-v) ∀l ∈ L, (a, b h ) ∈ P l : j∈J σ l j (a, b h ) ≤ λ l -δ λ + j∈J V j (a, b h ).


Florent Kaisser
email: florent.kaisser@ifsttar.fr

Christophe Gransart
email: christophe.gransart@ifsttar.fr

Marion Berbineau
email: marion.berbineau@ifsttar.fr

Simulations of VANET scenarios with OPNET and SUMO

Keywords: VANET, Opnet, SUMO, simulation, framework, dissemination

Vehicular Ad hoc Networks (vanet) are a special kind of Mobile Ad-Hoc Networks (manet) adapted to the communications between vehicles. Several specific protocols to vanets have been developed to improve performances and satisfy vehicular application needs. To evaluate a protocol for vanet, some realistic mobility models are needed. Unfortunately, such models are not provided by Opnet Modeler. In this work, we propose a framework that enhances Opnet Modeler simulation scenario using realistic vehicular mobility models. This framework makes use of the open source software called "Simulation of Urban MObility" (sumo) and the "input trajectory files" feature of Opnet Modeler.

Introduction

Starting with the idea of making driving safer by inter-vehicle communication, the concept of vehicular networks or vehicular ad hoc networks (vanets) has been extended to a large collection of various applications that can profit from wireless communication between vehicles. Vehicles are not only communicating between each other, but are also getting information from and sending data to infrastructure units. This particular context has several specificities like the deployment of safety applications that have critical requirements regarding communications. Classical ad hoc routing protocol (aodv, olsr, gpsr) are usable in vanet, but they are not adapted to the specificities of these networks.

Several specific protocols to vanets have been developed to improve performances and satisfy vehicular application needs. To evaluate scalability and efficiency of a protocol for vanet, some simulations with realistic mobility model are needed. Numerous works use various tools to evaluates their proposals. In this paper we propose to use Opnet Modeler to simulate vanet by associating it with a vehicular mobility simulator.

In a first section, we propose an overview of vanet simulation by describing current simulation tools. Afterwards, in a second section, we introduce our framework to simulate vanet with Opnet Modeler. Finally, we use our work to evaluate a simple dissemination protocol for vanet by simulation of adapted scenarios.

VANET simulation overview

In this section, we give a brief overview of vehicular ad hoc network and tools to simulate them. Like other kind of networks, simulating vanet is necessary to validate protocols and applications. In addition, the total number of vehicles in a network can be large, so evaluating the scalability is central.

Many tools allow to simulate vanet. In many case, this tool is a vehicular mobility model associate with a network simulator. In some case, vehicular mobility model is a simple random way point mobility model, but it restricts the movement of vehicles to real roads. To improve realism of the simulation, a car-following model can be added, allowing to compute the vehicle acceleration (then speed and position) according to neighbor vehicles in the same lane or adjacent lanes. Next, we describe some network simulators associated to a vehicular mobility model. A more exhaustive list of tools to simulate vanet is depicted in a dedicated book [?] and a paper [?].

swans++ [?] is the network simulator swans (from jist/swans [?] project) extended with a vehicular mobility model, straw [?] (Street Random Way point). straw uses a simple random way point mobility model but it takes in account a real street map loaded from tiger [?] (Topologically Integrated Geographic Encoding and Referencing, an us street database) data files.

GrooveNet [?] (originally known as GrooveSim) is a network and mobility simulator for real and simulated vehicles. GrooveNet, originally as an extension of RoadNav [?] open-source simulator, can load real street map from tiger database and includes a car-following model.

TraNS [?] (Traffic and Network Simulation Environment) was the first work to combine the network simulator ns-2 [?] with a vehicular mobility simulator sumo. We introduce sumo below. The link between the two simulators is done with a parser that reads the output of sumo and converts it to a suitable format for ns-2. Other works like move [?] gui and traceexporter tool (module of sumo) allow to link ns-2 with sumo.

In Veins [?] (Vehicles in Network Simulation), sumo is paired with an other network simulator omnet++ [?]. It creates a bidirectional communication between sumo and omnet++. Thus, the network simulator can react to events from the mobility simulator.

itetris simulation platform [?] use ns-3 [?] as network simulator and sumo. The two open source simulation platforms are connected with a central module called itetris Control System (ics). This approach permits to have the best performance in terms of scalability and modularity.

Opnet Modeler enables both random mobility and trajectory mobility. The last-mentioned is setting with one trajectory file per node. This method allows to elaborate complex node movements. Unfortunately, interaction between nodes are not taken in account, so realistic mobility is limited. To the best of our knowledge, no tool for Opnet Modeler exists allowing to simulate vanet with a realistic mobility model.

In this paper we propose a framework for Opnet Modeler to simulate complex mobility, in our case moving vehicles on a road, using an extern microscopic traffic simulation called sumo.

A framework to simulate VANET

A microscopic traffic simulator computes the position of all vehicles on road at some time t from vehicles and road characteristics. These positions are used to show vehicles on a graphical user interface (gui) or written in a file (dump file). These simulators use a realistic model to describe the vehicles moving. This model computes the ideal acceleration, velocity and position for each vehicle any time, therefore avoid the physical collisions between vehicle.

Input data can be initials positions, vehicle characteristics (acceleration, maximum speed, etc), road network,way to go, position of destination, speed limits, etc. sumo [?] is a free implementation of such a simulator and supports carfollowing model (issue of [?,?,?,?]). sumo implementation consists of several modules (or commands), with the sumo module in the center (Figure ??). Input data of sumo is one or several road network files and one route file. The road network file can be generated from various input formats with netconvert module. These input formats can be osm files, from Open Street Map [?] database, or shape files, from tiger [?] database. Many other formats are available.

A route file describes both the characteristics of vehicles on the road and the path taken by the cars (edge sets of network road). Like road network files, route files can be generated with a other module called duarouter from two kinds of input: trip or flow definition. Each trip consists at least of the starting, the ending edge and the departure time. Then duarouter computes the shortest path between theses edges. Each trip is associated with one vehicle. Flow is mostly the same approach as using trip definitions, but one may join vehicles having the same departure and arrival edge using this method. Moreover, initial position of all vehicles are computed randomly (from a simple discrete uniform distribution).

Generate simple scenario

From network and route files, sumo module simulates all the positions at several times (e.g. every seconds). These positions are written in a dump file. This file is used to generate file(s) in a format understood by network simulator softwares. In our case, we need a converter to generate files for Opnet Modeler. This is achieved by developing our extension traceexporter1 . This extension implement the data flow diagram shown in Figure ??. In addition of dump file, two other

Generate multiple scenarios

We added a feature to traceexporter allowing to generate multiple scenarios at the same time. A scenario file defines all scenarios to generate. Each scenario contain links to one input file for the road network (road network file), one for the route definitions (route file, trip file or flow file), one for the include objects and one for the node attributes (Figure ??). The different scenario can use same or different input files. For examples, to generate scenarios with different number of vehicles (50, 100, 150), three scenarios use the same network and node attributes files, but three different flow files containing three number of vehicles to generate. Moreover, traceexporter runs automatically the commands like sumo and duarouter (for this reason, sumo does not appear on Figure ??).

Dissemination of informations in VANET

Several applications for vanet need to disseminate information on the network. For security, an alert is spread to neighbor vehicles or the current informations of vehicles (like the position, speed or other information from vehicle probes) can be sent to all neighbors to increase driver visibility. We take this application as an instance of a vanet simulation. Therefore, we add a process model for Opnet Modeler to simulate a dissemination of information in vanet. This process is above wireless lan mac. A new packet format is defined, containing: vehicle id, type of information, position, number of hop, lifetime of the information, sequence number. This packet is the payload of a mac packet sent by mac layer. The process sends a packet every 500 ms. We define a simple forwarding scheme (flooding): when the process receives a packet not received in the past, the packet is re-sent to the neighbors. Thus, all nodes in the network receive informations contained in the packet.

With a high density of vehicles, the number of packet sent in the network can reach the network capacity, packets are no longer forwarded, then some vehicles do not receive information. To avoid this, we define a forwarding scheme to limit the number of packet sent. Several existing works [?,?,?,?] propose an achievement of dissemination in vanet. In this paper, we simulate (in addition to flooding) a simple distance-based protocol (sdp) [?]. On message reception, a vehicle starts a timer T inversely proportional to the distance from previous sender :

T = t max * (1 - d R )
with t max the maximum waiting time, d the distance from previous sender, R the radio range. In the simulation, R = 550 m and t max = 50 ms. When the timer reaching zero the node forward the packet. Other waiting nodes, receive this packet and cancel their timer. Thus, we reduce the number of packet sent in the network. We simulate flooding and sdp protocol with several number of vehicles. In Figure ?? we see a good improvement with sdp protocol: the maximum number of discovered neighbor with flooding is about 120, whereas the maximum is close to 200 with sdp. In Communication Technologies for Vehicles, édité par Alexey Vinel, Rashid Mehmood, Marion Berbineau, Cristina Rico Garcia, Chung-Ming Huang, et Naveen Chilamkurti, p103 112. Lecture Notes in Computer Science 7266. Springer Berlin Heidelberg, 2012. http://link.springer.com/chapter/10.1007/978-3-642-29667-3_9.

Fig. 1 .

 1 Fig. 1. Process to generate vehicular mobility with sumo

Fig. 2 .

 2 Fig. 2. Topology import with new scenario assistant

Fig. 3 .

 3 Fig. 3. vanet in Opnet Modeler with our framework

Fig. 4 .

 4 Fig. 4. Multiple scenarios generation with traceexporter

Fig. 5 .

 5 Fig. 5. Neighboor discovery with simple dissemination protocols

Extension traceexporter already exists, but it only for ns-2. We have preferred redevelop a similar extension for both ns-2 and Opnet Modeler simulators. Moreover our implementation is more modular and therefore more easier to extend.In Communication Technologies for Vehicles, édité par AlexeyVinel, Rashid Mehmood, Marion Berbineau, Cristina Rico Garcia, et Naveen Chilamkurti, p103 112. Lecture Notes in Computer Science 7266. Springer Berlin Heidelberg

, 2012. http://link.springer.com/chapter/10.1007/978-3-642-29667-3_9.

Conclusion

In this paper we have proposed a framework to simulate vanet from Opnet Modeler and sumo. Our proposal allows to use a realistic mobility model to compute movement of vehicles on a real road with Opnet Modeler to effectively simulate communication networks and with many existing models. The aim of this framework is to be modular and easy to use by exploiting judicious feature of Modeler like topology import.

But simulation of vanet with several number of vehicles or random seed require many Opnet Modeler scenarios and an equivalent number of topology import, which limits a good protocols evaluation. In future works, we wish to integrate in Opnet Modeler a direct and bidirectional communication with sumo allowing us to define more complex simulation scenarios.

Source code of this work can be downloaded at https://bitbucket.org/ florent_k/traceexporter.