An evolutionary approach to construction of outranking models for multicriteria classification: The case of the ELECTRE TRI method

Outranking methods constitute an important class of multicriteria classification models. Often, however, their implementation is cumbersome, due to the large number of parameters that the decision maker must specify. Past studies tried to address this issue using linear and nonlinear programming, to elicit the necessary preferential information from assignment examples. In this study, an evolutionary approach, based on the differential evolution algorithm, is proposed in the context of the ELECTRE TRI method. Computational results are given to test the effectiveness of the methodology and the quality of the obtained models.     

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.     

ELECTRE: Robust ordinal regression for outranking methods

We present a new method, called ELECTRE^GKMS, which employs robust ordinal regression to construct a set of outranking models compatible with preference information. The preference information supplied by the decision maker (DM) is composed of pairwise comparisons stating the truth or falsity of the outranking relation for some real or fictitious reference alternatives. Moreover, the DM specifies some ranges of variation of comparison thresholds on considered pseudo-criteria. Using robust ordinal regression, the method builds a set of values of concordance indices, concordance thresholds, indifference, preference, and veto thresholds, for which all specified pairwise comparisons can be restored. Such sets are called compatible outranking models. Using these models, two outranking relations are defined, necessary and possible. Whether for an ordered pair of alternatives there is necessary or possible outranking depends on the truth of outranking relation for all or at least one compatible model, respectively. Distinguishing the most certain recommendation worked out by the necessary outranking, and a possible recommendation worked out by the possible outranking, ELECTRE^GKMS answers questions of robustness concern. The method is intended to be used interactively with incremental specification of pairwise comparisons, possibly with decreasing confidence levels. In this way, the necessary and possible outranking relations can be, respectively, enriched or impoverished with the growth of the number of pairwise comparisons. Furthermore, the method is able to identify troublesome pieces of preference information which are responsible for incompatibility. The necessary and possible outranking relations are to be exploited as usual outranking relations to work out recommendation in choice or ranking problems. The introduced approach is illustrated by a didactic example showing how ELECTRE^GKMS can support real-world decision problems.     

A reference point technique to compute nondominated solutions in MOLFP

This paper presents a new technique to compute nondominated solutions in multiobjective linear-fractional programming (MOLFP) by using reference points. The basic idea consists in dividing the nondominated region approximately through the “middle” making two subregions, which are then analyzed in order to try to discard one of them. The process is repeated with the remaining region(s), and it ends when the regions become so small that the differences among their nondominated solutions are lower than a predefined margin of error. The results of several tests carried out to evaluate the performance of the technique are reported.     

The set of all nondominated solutions in linear cases and a multicriteria simplex method

In this note we are interested in the properties of, and methods for locating the set of all nondominated solutions of multiple linear criteria defined over a polyhedron. We first show that the set of all dominated solutions is convex and that the set of all nondominated solutions is a subset of the convex hull of the nondominated extreme points. When the domination cone is polyhedral, we derive a necessary and sufficient condition for a point to be nondominated. The condition is stronger than that of Ref. [1] and enables us to give a simple proof that the set of all nondominated extreme points indeed is connected. In order to locate the entire set of all nondominated extreme points, we derive a generalized version of simplex method—multicriteria simplex method. In addition to some useful results, a necessary and sufficient condition for an extreme point to be nondominated is derived. Examples and computer experience are also given. Finally, we focus on how to generate the entire set of all nondominated solutions through the set of all nondominated extreme points. A decomposition theorem and some necessary and sufficient conditions for a face to be nondominated are derived. We then describe a systematic way to identify the entire set of all nondominated solutions. Through examples, we show that in fact our procedure is quite efficient.     

Necessary conditions of nondominated solutions in multicriteria decision making

A partial integrodifferential equation is studied in which the derivatives of highest order also contain a discrete and a distributed delay. By means of abstract regularity results, global existence and uniqueness of a strict solution are obtained; moreover a characterization of the infinitesimal generator of the solution operator is given.     

A multicriteria model for risk sorting of natural gas pipelines based on ELECTRE TRI integrating Utility Theory

This paper proposes a multicriteria model for assessing risk in natural gas pipelines, and for classifying sections of pipeline into risk categories. The model integrates Utility Theory and the ELECTRE TRI method. It aims to help transmission and distribution companies, when engaged in risk management and decision-making, to consider the multiple dimensions of risk that may arise from pipeline accidents. Pipeline hazard scenarios are presented, and it is argued that the assessment of risk in natural gas pipelines should not be based solely on probabilities of human fatalities, but should involve a wider perspective that simultaneously takes into consideration the human, environmental and financial dimensions of impacts of pipeline accidents. Finally, in order to verify the effectiveness of the model set out, a numerical application based on a real case study is presented.     

Sensitivity analysis for the ELECTRE multicriteria method

In this paper, we develop sensitivity ranges for parameters used in the ELECTRE I multicriteria decision method. Parameters studied include criteria weights as well as significance thresholds. For these parameters, intervals are determined in which parameter changes will not affect the set of non-outranked alternatives. The approach developed is illustrated by a numerical example and possible applications are discussed.

---

Zusammenfassung In dieser Arbeit wird ein Ansatz zur Sensitivitätsanalyse für das Multikriteria-Entscheidungsverfahren ELECTRE I vorgestellt. Für die Gewichte der Kriterien sowie die im Verfahren verwendeten Signifikanzschwellen werden jeweils Intervalle konstruiert, innerhalb derer Parameteränderungen keine Änderungen im Ergebnis des Verfahrens bewirken. Die entwickelte Sensitivitätsanalyse wird anhand eines Beispiels illustriert und mögliche Anwendungen des Konzeptes werden aufgezeigt.

     

Enhancing computations of nondominated solutions in MOLFP via reference points

In previous work, Costa and Alves (J Math Sci 161:(6)820–831, 2009; 2011) have presented Branch & Bound and Branch & Cut techniques that allow for the effective computation of nondominated solutions, associated with reference points, of multi-objective linear fractional programming (MOLFP) problems of medium dimensions (ten objective functions, hundreds of variables and constraints). In this paper we present some results that enhance those computations. Firstly, it is proved that the use of a special kind of achievement scalarizing function guarantees that the computation error does not depend on the dimension of the problem. Secondly, a new cut for the Branch & Cut technique is presented. The proof that this new cut is better than the one in Costa and Alves (2011) is presented, guaranteeing that it reduces the region to explore. Some computational tests to assess the impact of the new cut on the performance of the Branch & Cut technique are presented.     

Characterization of nondominated controls in terms of solutions of weighting problems

The problem of continuously dynamic multiobjective optimization, or multiobjective control, is discussed. The concepts of nondominated controls and viable controls are introduced. For a class of nonlinear dynamic systems, the convexity of their controlled Carathéodory trajectories is proved. Based on this convexity, sufficient conditions are given for the solution of a multiobjective control problem to be obtained in terms of solutions of weighting problems.This work was partly done at the Huazhong University of Science and Technology, Wuhan, China. The author is indebted to Professor Chen Ting for his advice. The author wishes to thank Professor G. Leitmann for his favorable comments. The author is also grateful to Ms. Mary S. Linn at the University of Kansas, who helped him improve the English presentation of this paper.     

用ELECTRE方法进行炮兵战场目标价值排序

结合炮兵火力运用的一般原则,分析引入了ELECTRE方法,并用ELECTRE方法建立符合指挥员习惯思维的目标价值排序模型,为指挥员战场决策提供一种量化的目标打击序列.     

Generalization of domination structures and nondominated solutions in multicriteria decision making

The concepts of domination structures and nondominated solutions are important in tackling multicriteria decision problems. We relax Yu's requirement that the domination structure at each point of the criteria space be a convex cone (Ref. 1) and give results concerning the set of nondominated solutions for the case where the domination structure at each point is a convex set. A practical necessity for such a generalization is discussed. We also present conditions under which a locally nondominated solution is also a globally nondominated solution.     

A new approach to multi-criteria sorting based on fuzzy outranking relations: The THESEUS method

In this paper, we propose the THESEUS method, a new approach based on fuzzy outranking relations to multi-criteria sorting problems. Compared with other outranking-based methods, THESEUS is inspired by another view of multi-criteria classification problems. It utilizes a new way of evaluating the assignment of an object to an element of the set of ordered categories that were previously defined. This way is based on comparing every possible assignment with the information from various preference relations that are derived from a fuzzy outranking relation defined on the universe of objects. The appropriate assignment is determined by solving a simple selection problem.The capacity of a reference set for making appropriate assignments is related to a good characterization of the categories. A single reference action characterizing a category may be insufficient to achieve well-determined assignments. In this paper, the reference set capacity to perform appropriate assignments is characterized by some new concepts. This capacity may be increased when more objects are added to the reference set. THESEUS is a method for handling the preference information contained in such larger reference sets.     

Cone convexity,cone extreme points,and nondominated solutions in decision problems with multiobjectives

Although there is no universally accepted solution concept for decision problems with multiple noncommensurable objectives, one would agree that agood solution must not be dominated by the other feasible alternatives. Here, we propose a structure of domination over the objective space and explore the geometry of the set of all nondominated solutions. Two methods for locating the set of all nondominated solutions through ordinary mathematical programming are introduced. In order to achieve our main results, we have introduced the new concepts of cone convexity and cone extreme point, and we have explored their main properties. Some relevant results on polar cones and polyhedral cones are also derived. Throughout the paper, we also pay attention to an important special case of nondominated solutions, that is, Pareto-optimal solutions. The geometry of the set of all Pareto solutions and methods for locating it are also studied. At the end, we provide an example to show how we can locate the set of all nondominated solutions through a derived decomposition theorem.     

Using the homotopy method to find periodic solutions of forced nonlinear differential equations

This paper discusses a result of Li and Shen which proves the existence of a unique periodic solution for the differential equation x + k [xdot] + g(x,t) = ε(t) where k is a constant; g is continuous, continuously differentiable with respect to x, and is periodic of period P in the variable t; ε(t) is continuous and periodic of period P, and when ?g/?x satisfies some additional boundedness conditions. This means that there exist initial values x(0) = α* and [xdot] (0) = β* so that the solution to the corresponding initial value problem is periodic of period P and is unique (up to a translation of the time variable) with this property. The proof of this result is constructive, so that starting with any initial conditions x(0) = α and [xdot](0) = β, a path in the phase plane can be produced, starting at (α, β) and terminating at (α*, β*). Both the theoretical proof and a constructive proof are discussed and a Mathematica implementation developed which yields an algorithm in the form of a Mathematica notebook (which is posted on the webpage http://pax.st.usm.edu/downloads). The algorithm is robust and can be used on differential equations whose terms do not satisfy Li and Shen's hypotheses. The ideas used reinforce concepts from beginning courses in ordinary differential equations, linear algebra, and numerical analysis.     

Enriched preference modeling and robustness analysis for the ELECTRE Tri-B method

Annals of Operations Research - We consider multiple criteria sorting problems with preference-ordered classes delimited by a set of boundary profiles. While significantly extending the ELECTRE...     

Using branch-and-bound algorithms to obtain suboptimal solutions

The branch-and-bound principle is successful in solving various combinatorial optimization problems. In general, however, the computation time becomes excessive as the sizes of problems grow. To overcome this difficulty the following three suboptimal methods are often employed in practice.

1. Letz be the value of currently known best solution of a given minimization problem, and letg (P _i ) be a lower bound on the objective value of partial problemP _i . TerminateP _i ifg (P _i ) ?z?? (z), where? (z) is an allowance specified in advance.
2. Cut off the computation as soon as T₀ partial problems are decomposed, where T₀ is a prespecified positive integer.
3. Always take into account at mostM ₀ (a given positive integer) number of active partial problems. The overflown partial problems are simply ignored.

The effects of these methods on the computation time and the quality of obtained suboptimal solutions are investigated from both theoretical and simulation points of view.     

Extensions of the prudence principle to exploit a valued outranking relation

In many outranking methods, the alternatives are first compared pairwise to build a valued outranking relation, which is then exploited to derive a recommendation for the decision maker. This paper proposes extensions of Arrow and Raynaud’s prudence principle to exploit a valued outranking relation, even in cases where the outranking values have an ordinal interpretation. The idea is to build a ranking that maximizes the weakest support for its implicit pairwise comparisons. We present a family of exploitation models providing three types of solutions, depending on the decision maker’s request: a linear order, a weak order, or a partial preorder. An algorithm is provided which solves the exploitation models. Relations between these models and some of their properties are also discussed.     

Evaluation of nondominated solution sets for k-objective optimization problems: An exact method and approximations

Integrated Preference Functional (IPF) is a set functional that, given a discrete set of points for a multiple objective optimization problem, assigns a numerical value to that point set. This value provides a quantitative measure for comparing different sets of points generated by solution procedures for difficult multiple objective optimization problems. We introduced the IPF for bi-criteria optimization problems in [Carlyle, W.M., Fowler, J.W., Gel, E., Kim, B., 2003. Quantitative comparison of approximate solution sets for bi-criteria optimization problems. Decision Sciences 34 (1), 63–82]. As indicated in that paper, the computational effort to obtain IPF is negligible for bi-criteria problems. For three or more objective function cases, however, the exact calculation of IPF is computationally demanding, since this requires k (⩾3) dimensional integration.In this paper, we suggest a theoretical framework for obtaining IPF for k (⩾3) objectives. The exact method includes solving two main sub-problems: (1) finding the optimality region of weights for all potentially optimal points, and (2) computing volumes of k dimensional convex polytopes. Several different algorithms for both sub-problems can be found in the literature. We use existing methods from computational geometry (i.e., triangulation and convex hull algorithms) to develop a reasonable exact method for obtaining IPF. We have also experimented with a Monte Carlo approximation method and compared the results to those with the exact IPF method.     

Multicriteria modelling for a repair contract problem based on utility and the ELECTRE I method

Each alternative for a repair contract implies a specific responsetime and related cost. The response time is associated withthe commitment of repair time, based on the contract. A decisionmaker chooses the best alternative taking into account the systemperformance and the cost of the contract. This problem has beenanalysed through a multicriteria decision model. This decisionmodel supports decision makers in the determination of the bestcombination of contracting conditions. The decision model proposedallows the decision maker to quantify the consequences of anaction taking into account two basic criteria: the cost of thecontract and the system performance. Two different decisionmodels have been built to support decision makers. These decisionmodels are based on different multicriteria approaches. Thefirst, reported in a previous paper, is based on the multiattributeutility theory (MAUT). The model presented in this paper isbased on the ELECTRE I method combined with utility functions.The paper presents the main theoretical aspects related to bothapproaches and practical implications related to model building.A numerical application is presented in order to illustratethe use of the decision model.