A multiple criteria sorting method where each category is characterized by several reference actions: The Electre Tri-nC method

This paper presents Electre Tri-nC, a new sorting method which takes into account several reference actions for characterizing each category. This new method gives a particular freedom to the decision maker in the co-construction decision aiding process with the analyst to characterize the set of categories, while there is no constraint for introducing only one reference action as typical of each category like in Electre Tri-C (Almeida-Dias et al., 2010). As in such a sorting method, this new sorting method is composed of two joint rules. Electre Tri-nC also fulfills a certain number of natural requirements. Additional results on the behavior of the new method are also provided in this paper, namely the ones with respect to the addition or removal of the reference actions used for characterizing a certain category. A numerical example illustrates the manner in which Electre Tri-nC can be used by a decision maker. A comparison with some related sorting procedures is presented and it allows to conclude that the new method is appropriate to deal with sorting problems.     

Using assignment examples to infer weights for ELECTRE TRI method: Some experimental results

Given a finite set of alternatives A, the sorting (or assignment) problem consists in the assignment of each alternative to one of the pre-defined categories. In this paper, we are interested in multiple criteria sorting problems and, more precisely, in the existing method ELECTRE TRI. This method requires the elicitation of preferential parameters (weights, thresholds, category limits,…) in order to construct a preference model which the decision maker (DM) accepts as a working hypothesis in the decision aid study. A direct elicitation of these parameters requiring a high cognitive effort from the DM (V. Mosseau, R. Slowinski, Journal of Global Optimization 12 (2) (1998) 174), proposed an interactive aggregation–disaggregation approach that infers ELECTRE TRI parameters indirectly from holistic information, i.e., assignment examples. In this approach, the determination of ELECTRE TRI parameters that best restore the assignment examples is formulated through a nonlinear optimization program.In this paper, we consider the subproblem of the determination of the weights only (the thresholds and category limits being fixed). This subproblem leads to solve a linear program (rather than nonlinear in the global inference model). Numerical experiments were conducted so as to check the behaviour of this disaggregation tool. Results showed that this tool is able to infer weights that restores in a stable way the assignment examples and that it is able to identify “inconsistencies” in the assignment examples.     

Inferring an ELECTRE TRI Model from Assignment Examples

Given a finite set of alternatives, the sorting problem consists in the assignment of each alternative to one of the pre-defined categories. In this paper, we are interested in multiple criteria sorting problems and, more precisely, in the existing method ELECTRE TRI. This method requires the elicitation of parameters (weights, thresholds, category limits,...) in order to construct the Decision Maker's (DM) preference model. A direct elicitation of these parameters being rather difficult, we proceed to solve this problem in a way that requires from the DM much less cognitive effort. We elicit these parameters indirectly using holistic information given by the DM through assignment examples. We propose an interactive approach that infers the parameters of an ELECTRE TRI model from assignment examples. The determination of an ELECTRE TRI model that best restitutes the assignment examples is formulated through an optimization problem. The interactive aspect of this approach lies in the possibility given to the DM to revise his/her assignment examples and/or to give additional information before the optimization phase restarts.     

Approximating Promethee II’s net flow scores by piecewise linear value functions

Promethee II is a prominent method for multi-criteria decision aid (MCDA) that builds a complete ranking on a set of potential actions by assigning each of them a so-called net flow score. However, to calculate these scores, each pair of actions has to be compared, causing the computational load to increase quadratically with the number of actions, eventually leading to prohibitive execution times for large decision problems. For some problems, however, a trade-off between the ranking’s accuracy and the required evaluation time may be acceptable. Therefore, we propose a piecewise linear model that approximates Promethee II’s net flow scores and reduces the computational complexity (with respect to the number of actions) from quadratic to linear at the cost of some wrongly ranked actions. Simulations on artificial problem instances allow us to quantify this time/quality trade-off and to provide probabilistic bounds on the problem size above which our model satisfyingly approximates Promethee II’s rankings. They show, for instance, that for decision problems of 10,000 actions evaluated on 7 criteria, the Pearson correlation coefficient between the original scores and our approximation is of at least 0.97. When put in balance with computation times that are more than 7000 times faster than for the Promethee II model, the proposed approximation model represents an interesting alternative for large problem instances.     

A new method for multiple criteria group decision making with incomplete weight information under linguistic environment

A new method is proposed to solve multiple criteria group decision making (MCGDM) problems, in which both the criteria values and criteria weights take the form of linguistic information, and the information about linguistic criteria weights is partly known or completely unknown. Firstly, to get reasonable decision result, instead of assigning the same weight to the decision maker (DM) for all criteria, we propose a method to determine the weight of DM with respect to each criterion under linguistic environment by calculating the similarity degree between individual 2-tuple linguistic evaluation value and the mean given by all decision makers (DMs). Secondly, for the situations where the information about the criteria weights is partly known or completely unknown, we establish optimization models to determine the criteria weights by defining 2-tuple linguistic positive ideal solution (TL-PIS), 2-tuple linguistic right negative ideal solution (TL-RNIS) and 2-tuple linguistic left negative ideal solution (TL-LNIS) of the collective 2-tuple linguistic decision matrix. Thirdly, we propose a new method to solve MCGDM problems with partly known or completely unknown linguistic weight information. Finally, an illustrative example is given to demonstrate the calculation process of the proposed method.     

Inferring Electre’s veto-related parameters from outranking examples

When considering Electre’s valued outranking relations, aggregation/disaggregation methodologies have difficulties in taking discordance (veto) into account. We present a partial inference procedure to compute the value of the veto-related parameters that best restore a set of outranking statements (i.e., examples that an Electre model should restore) provided by a decision maker, given fixed values for the remaining parameters of the model.This paper complements previous work on the inference of other preference-related parameters (weights, cutting level, category limits, …), advancing toward an integrated framework of inference problems in Electre III and Tri methods. We propose mathematical programs to infer veto-related parameters, first considering only one criterion, then all criteria simultaneously, using the original version of Electre outranking relation and two variants. This paper shows that these inference procedures lead to linear programming, 0–1 linear programming, or separable programming problems, depending on the case.     

Integer Programming Duality in Multiple Objective Programming

The weighted sums approach for linear and convex multiple criteria optimization is well studied. The weights determine a linear function of the criteria approximating a decision makers overall utility. Any efficient solution may be found in this way. This is not the case for multiple criteria integer programming. However, in this case one may apply the more general e-constraint approach, resulting in particular single-criteria integer programming problems to generate efficient solutions. We show how this approach implies a more general, composite utility function of the criteria yielding a unified treatment of multiple criteria optimization with and without integrality constraints. Moreover, any efficient solution can be found using appropriate composite functions. The functions may be generated by the classical solution methods such as cutting plane and branch and bound algorithms.     

An effective Markov based approach for calculating the Limit Matrix in the analytic network process

Analytic network process is a multiple criteria decision analysis (MCDA) method that aids decision makers to choose among a number of possible alternatives or prioritize the criteria for making a decision in terms of importance. It handles both qualitative and quantitative criteria, that are compared in pairs, in order to forge a best compromise answer according to the different criteria and influences involved. The method has been widely applied and the literature review reveals a rising trend of ANP-related articles. The ‘power’ matrix method, a procedure necessary for the stability of the decision system, is one of the critical calculations in the mathematical part of the method. The present study proposes an alternative mathematical approach that is based on Markov chain processes and the well-known Gauss-Jordan elimination. The new approach obtains practically the same results as the power matrix method, requires slightly less time and number of calculations and handles effectively cyclic supermatrices, optimizing thus the whole procedure.     

Decision-aid for discrete multiple criteria decision making problems with imprecise data

We describe ways of aiding decision making with a discrete set of alternatives. In many decision situations, it is not possible to obtain explicit preference information from the decision makers. Instead, useful decision-aid can be provided to the decision makers by describing what kind of weighting of the criteria result in certain choices of the alternatives. The suggested treatment is based on the basic ideas of the ELECTRE III method. The modelling of the preferences by pseudo-criteria is especially helpful in case the data, that is, the criterion values are imprecise. Unlike ELECTRE III, no ranking of the alternatives is produced. Based on a minimum-procedure in the exploitation of the outranking relations, we provide information about the weights of the criteria that make a certain alternative the best. We also present an interactive searching procedure in the weighting space. The auxiliary optimization problems to be solved are nondifferentiable. Cases with both single and multiple decision makers are considered.     

Projection method for multiple criteria group decision making with incomplete weight information in linguistic setting

Multiple criteria group decision making (MCGDM) problems have become a very active research field over the last decade. Many practical problems are often characterized by MCGDM. The aim of this paper is to develop a new approach for MCGDM problems with incomplete weight information in linguistic setting based on the projection method. Firstly, to reflect the reality accurately, a method to determine the weights of decision makers in linguistic setting is proposed by calculating the degree of similarity between 2-tuple linguistic decision matrix given by each decision maker and the average 2-tuple linguistic decision matrix. By using the weights of decision makers, all individual 2-tuple linguistic decision matrices are aggregated into a collective one. Then, to determine the weight vector of criteria, we establish a non-linear optimization model based on the basic ideal of the projection method, i.e., the optimal alternative should have the largest projection on the 2-tuple linguistic positive ideal solution (TLPIS). Calculate the 2-tuple linguistic projection of each alternative on the TLPIS and rank all the alternatives according to the 2-tuple linguistic projection value. Finally, an illustrative example is given to demonstrate the calculation process of the proposed method, and the validity is verified by comparing the evaluation results of the proposed method with that of the technique for order preference by similarity to ideal solution (TOPSIS) method.     

Robustness and information levels in case-based multiple criteria sorting

Case-based preference elicitation methods for multiple criteria sorting problems have the advantage of posing rather small cognitive demands on a decision maker, but they may lead to ambiguous results when preference parameters are not uniquely determined. We use a simulation approach to determine the extent of this problem and to study the impact of additional case information on the quality of results. Our experiments compare two decision analysis tools, case-based distance sorting and the simple additive weighting method, in terms of the effects of additional case information on sorting performance, depending on problem dimension – number of groups, number of criteria, etc. Our results confirm the expected benefit of additional case information on the precision of estimates of the decision maker’s preferences. Problem dimension, however, has some unexpected effects.     

A two-phase algorithm for consensus building in AHP-group decision making

Group decision making through the AHP has received significant attention in contemporary research, the primary focus of which has been on the issues of consistency and consensus building. In this paper, we concentrate on the latter and present a two-phase algorithm based on the optimal clustering of decision makers (members of a group) into sub groups followed by consensus building both within sub groups and between sub groups. Two-dimensional Sammon’s mapping is proposed as a tool for generating an approximate visualization of sub groups identified in multidimensional vector space, while the consensus convergence model is suggested for reaching agreement amongst individuals in and between sub groups. As a given, all decision makers evaluate the same decision elements within the AHP framework and produce individual scores of these decision elements. The consensual scores are obtained through the iterative procedure and the final scores are declared as the group decision. The results of two selected numerical examples are compared with two sets of results: the results obtained by the commonly used geometric mean aggregation method and also the results obtained if the consensus convergence model is applied directly without the prior clustering of the decision makers. The comparisons indicated the expected differences among the aggregation schemes and the final group scores. The matrices of respect values in the consensus convergence model, obtained for cases when the decision makers are optimally clustered and when they are not, show that in the latter case the decision makers receive lower weights of respect from other members in the group. Various tests showed that our approach is efficient in cases when no clusters can be visually and undoubtedly identified, especially if the number of group members is high.     

Interactive outranking approaches for multicriteria decision-making problems with imprecise information

PROMETHEE is a powerful method, which can solve many multiple criteria decision making (MCDM) problems. It involves sophisticated preference modelling techniques but requires too much a priori precise information about parameter values (such as criterion weights and thresholds). In this paper, we consider a MCDM problem where alternatives are evaluated on several conflicting criteria, and the criterion weights and/or thresholds are imprecise or unknown to the decision maker (DM). We build robust outranking relations among the alternatives in order to help the DM to rank the alternatives and select the best alternative. We propose interactive approaches based on PROMETHEE method. We develop a decision aid tool called INTOUR, which implements the developed approaches.     

Approximation algorithms for the bi-criteria weighted MAX-CUT problem

We consider a generalization of the classical MAX-CUT problem where two objective functions are simultaneously considered. We derive some theorems on the existence and the non-existence of feasible cuts that are at the same time near optimal for both criteria. Furthermore, two approximation algorithms with performance guarantee are presented. The first one is deterministic while the second one is randomized. A generalization of these results is given for the bi-criteria MAX-k-CUT problem.     

Computing tournament solutions using relation algebra and RelView

We describe a simple computing technique for the tournament choice problem. It rests upon relational modeling and uses the BDD-based computer system RelView for the evaluation of the relation-algebraic expressions that specify the solutions and for the visualization of the computed results. The Copeland set can immediately be identified using RelView’s labeling feature. Relation-algebraic specifications of the Condorcet non-losers, the Schwartz set, the top cycle, the uncovered set, the minimal covering set, the Banks set, and the tournament equilibrium set are delivered. We present an example of a tournament on a small set of alternatives, for which the above choice sets are computed and visualized via RelView. The technique described in this paper is very flexible and especially appropriate for prototyping and experimentation, and as such very instructive for educational purposes. It can easily be applied to other problems of social choice and game theory.     

Extended use of the cards procedure as a simple elicitation technique for MAVT. Application to public procurement in Switzerland

The cards procedure was designed in the early 90 as a simple way to elicit weights for multiple criteria decision analysis outranking methods. It is based on the elicitation of the difference of importance between successive pairs of criteria. We propose to extend its use in two directions:     

Differential approximation of min sat, max sat and related problems

We present differential approximation results (both positive and negative) for optimal satisfiability, optimal constraint satisfaction, and some of the most popular restrictive versions of them. As an important corollary, we exhibit an interesting structural difference between the landscapes of approximability classes in standard and differential paradigms.     

Acceptable consistency of aggregated comparison matrices in analytic hierarchy process

The analytic hierarchy process is a method for solving multiple criteria decision problems, as well as group decision making. The weighted geometric mean method is appropriate when aggregation of individual judgements is used. This paper presents a new proof which confirms the property that if the comparison matrices of all decision makers are of acceptable consistency, then the weighted geometric mean complex judgement matrix (WGMCJM) also is of acceptable consistency. This property was presented and first proved by Xu (2000), but Lin et al. (2008) rejected the proof. We also discuss under what conditions the WGMCJM is of acceptable consistency when not all comparison matrices of decision makers are of acceptable consistency. For this case we determine the sufficient condition for the WGMCJM to be of acceptable consistency and provide numerical examples. For a special case of two decision makers with 3 × 3 comparison matrices we find out some additional conditions for the WGMCJM to be of acceptable consistency.     

A lexicographical compromise method for multiple criteria group decision problems with imprecise information

This paper addresses multiple criteria group decision making problems where each group member offers imprecise information on his/her preferences about the criteria. In particular we study the inclusion of this partial information in the decision problem when the individuals’ preferences do not provide a vector of common criteria weights and a compromise preference vector of weights has to be determined as part of the decision process in order to evaluate a finite set of alternatives. We present a method where the compromise is defined by the lexicographical minimization of the maximum disagreement between the value assigned to the alternatives by the group members and the evaluation induced by the compromise weights.     

Applying relational algebra and RelView to coalition formation

We present an application of relational algebra to coalition formation. This leads to specifications, which can be executed with the help of the RelView tool after a simple translation into the tool’s programming language. As an example we consider a simplification of the situation in Poland after the 2001 elections.