# Ranking Methods for Multicriteria Decision-Making: Application to Benchmarking of Solvers and Problems

Authors: Joseph Gogodze
Journal: Scientific Programming
 (2021)

---

## Abstract

Evaluating the performance assessments of solvers (e.g., for computation programs), known as the solver benchmarking problem, has become a topic of intense study, and various approaches have been discussed in the literature. Such a variety of approaches exist because a benchmark problem is essentially a multicriteria problem. In particular, the appropriate multicriteria decision-making problem can correspond naturally to each benchmark problem and vice versa. In this study, to solve the solver benchmarking problem, we apply the ranking-theory method recently proposed for solving multicriteria decision-making problems. The benchmarking problem of differential evolution algorithms was considered for a case study to illustrate the ability of the proposed method. This problem was solved using ranking methods from different areas of origin. The comparisons revealed that the proposed method is competitive and can be successfully used to solve benchmarking problems and obtain relevant engineering decisions. This study can help practitioners and researchers use multicriteria decision-making approaches for benchmarking problems in different areas, particularly software benchmarking.


---

## Body

## 1. Introduction

Recently, evaluating the performance of solvers (e.g., computer programs), that is, the problem of solver benchmarking, has attracted significant attention from scientists. Currently, most benchmarking tests produce tables that present the performance of each solver for each problem according to a specified evaluation metric (e.g., the central processing unit (CPU) time and number of function evaluations) and use various statistical tests for the conclusions. Thus, the selection of the benchmarking method currently depends on the subjective tastes and preferences of individual researchers. The following components of the benchmarking process, including the solver set, problem set, metric for performance assessment, and statistical tools for data processing, are chosen individually according to the researcher’s preferences. For example, the performance profile method, which is currently the most popular and widely used method in practice (see [1]), is based on a comparative analysis of empirical probability distribution functions obtained in numerical experiments with different solvers.In this study, we consider the benchmarking process based on the viewpoint that emphasizes natural relations between problems and solvers, as determined by their evaluation tables (see [2]). Specifically, we present data for benchmarking in the form of a so-called benchmarking context, that is, a triple S,P,J, where S and P are sets of solvers and problems, respectively, and J:S×P⟶ℝ is an assessment function (a performance evaluation metric). Throughout the paper, the sets of solvers and problems are assumed to be finite. This concept is quite general and emphasizes that problems, solvers, and assessment functions must be considered closely related and not independent.The benchmarking procedure presented in this study is described as follows. The data encapsulated by the given benchmarking contextS,P,J are used to build the corresponding multicriteria decision-making (MCDM) problem A,C, where A=S is a set of alternatives, and C=J⋅,p|p∈P is a set of criteria. Hence, we define a decision matrix as a matrix whose elements exhibit the performance of different alternatives (i.e., solvers) concerning various criteria (i.e., problems) through the assessment function. Thus, the investigation of benchmarking problems was reduced to an MCDM problem. Moreover, for each MCDM problem, a corresponding benchmark context is presented. The rationale for such a consideration is that a vast array of different approaches for MCDM problems can be used for benchmarking problem analysis. In particular, such a multicriteria formulation allows the consideration of Pareto-optimal alternatives (i.e., solvers) as “good” solvers.The next innovation presented in this study is that a recently proposed technique (see [3]) is used to solve the MCDM problem corresponding to a benchmarking problem. The multicriteria formulation is a typical starting point for theoretical and practical analyses of decision-making problems to clarify the essence of the new technique used in this study. Correspondingly, based on the fundamental concept of Pareto optimality, several methods and computational procedures have been developed to solve MCDM problems (see, e.g., overviews by [4–8], and more recently, [9–11]). However, unlike single-objective optimizations, a characteristic feature of Pareto optimality is that the set of Pareto-optimal alternatives is typically large. In addition, all these Pareto-optimal alternatives must be considered mathematically equal (equally “good”). Correspondingly, the problem of choosing a specific Pareto-optimal alternative for implementation arises because the final decision must usually be unique. Hence, additional factors must be considered to aid decision-makers in selecting specific or more favorable alternatives from the set of Pareto-optimal solutions.Therefore, we build a special score matrix for the MCDM problem, which allows us to construct the corresponding ranking for alternatives [3]. The score matrix can be built in different ways, but we use the simplest and most natural method. This study uses a scoring matrix calculating how many times one alternative is better than another according to the criteria. Hence, the proposed approach may yield an “objective” ranking method and provide an “accurate” ranking of the alternatives for MCDM. Correspondingly, a best-ranked alternative from the Pareto set is declared a “true” solution to the MCDM problem. The approach presented in this study for solving MCDM problems is useful when no decision-making authority is available or when the relative importance of various criteria has not been previously evaluated.Finally, we demonstrate the possibilities of the proposed method in a case study based on the computational and experimental results for benchmarking differential evolution (DE) algorithms presented by Sala et al. [12]. Specifically, we benchmark nine DE algorithms on a set of 50 test problems, following the random sampling equivalent expected run time (ERTRSE) performance metric. By conducting a numerical investigation, we demonstrate that the solution results of the MCDM problem obtained using the methods proposed in this study are quite competitive.


### 1.1. Contributions

This paper makes the following main contributions:(1)
The concept of the benchmarking context is introduced according to [2], and it is confirmed that a one-to-one correspondence exists between the set of benchmarking contexts and the set of MCDM problems(2)
The ranking-theory approach is proposed for solving MCDM problems corresponding to a given benchmarking context [3](3)
The approach proposed in this article is tested on a known literature dataset for benchmarking DE algorithms (see [12]), and the possibility of effectively solving benchmarking problems is fully confirmed


### 1.2. Related Literature

Without claiming to be a complete review, we present a brief overview of the literature on the benchmarking problem in the context of optimization problems. Generally, the consideration of a benchmarking problem is motivated by various reasons, such as selecting the best solver (algorithm, software, etc.) for some class of problems, testing the proposed novel solvers, and evaluating the solver performance for different option settings. For example, early contributions in the benchmarking of optimization algorithms are considered [13]. The results achieved at an early stage in the development of the subject can be judged according to work by the following researchers: Nash and Nocedal [14], Billups et al. [15], Conn et al. [16], Sandu et al. [17], Mittelmann [18], Vanderbei and Shanno [19], and Bondarenko et al. [20].The beginning of a new stage of development is associated with research work of Dolan and Moré [21], in which a performance profile comparison technique was proposed. This technique is now prevalent (but see, e.g., Gould and Scott [22]). Along with the performance profile comparison method, other more direct approaches have also been used in modern research. An idea of the modern research in the area under consideration can be obtained from the following research examples: Moles et al. [23], Mittelmann [24], Benson et al. [25], Kämpf et al. [26], Foster et al. [27], Rios and Sahinidis [28], Weise et al. [29], Sala et al. [12], and Cheshmi et al. [30]. A critical overview of the current state in the subject area was provided by Beiranvand et al. [1].At the end of this brief overview, this study focuses on benchmarking for solvers of only the optimization problem. However, the concept of benchmarking has a much broader context (see, e.g.,https://en.wikipedia.org/wiki/Benchmarking). The approach proposed in this article is quite general and can also be applied in other areas, but we do not consider this possibility here.


### 1.3. Notation

Throughout the article, the following general notation is used:ℕ is a set of natural numbers, and for a natural number n∈ℕ, we denote an n-dimensional vector space by ℝn and ⋅p is the lp−norm in ℝn. If not otherwise mentioned, we identify a finite set A with set ℕn=1,…,n, where n=A is the capacity of set A. We also introduce the following notations for special vectors and sets: for any n∈ℕ:0n=0,…,0︸n∈ℝn,1n=1,…,1︸n∈ℝn,Δn=ξ∈ℝ+n|∑k=1nξk, Δn∘=Δn∩intℝ+n, and ℝ+n⊂ℝn is a positive orthant. By necessity, we also identify the matrix Π∈ℝn×m with the map Π:ℕn×ℕm⟶ℝ. For a matrix Π∈ℝn×m, we denote its transpose by ΠT∈ℝm×n.


### 1.4. Outline

The remainder of this paper is structured as follows. In Section2, all necessary theoretical preliminaries regarding the MCDM problem (Section 2.1) and ranking-theory methods for solving MCDM problems are presented (Section 2.2). Section 3 introduces the concept of benchmarking contexts, and its relationship with the MCDM problem is discussed. In Section 4, the case-study problem of DE algorithm benchmarking is investigated numerically. Finally, the conclusions are presented in Section 5.


## 1.1. Contributions

This paper makes the following main contributions:(1)
The concept of the benchmarking context is introduced according to [2], and it is confirmed that a one-to-one correspondence exists between the set of benchmarking contexts and the set of MCDM problems(2)
The ranking-theory approach is proposed for solving MCDM problems corresponding to a given benchmarking context [3](3)
The approach proposed in this article is tested on a known literature dataset for benchmarking DE algorithms (see [12]), and the possibility of effectively solving benchmarking problems is fully confirmed


## 1.2. Related Literature

Without claiming to be a complete review, we present a brief overview of the literature on the benchmarking problem in the context of optimization problems. Generally, the consideration of a benchmarking problem is motivated by various reasons, such as selecting the best solver (algorithm, software, etc.) for some class of problems, testing the proposed novel solvers, and evaluating the solver performance for different option settings. For example, early contributions in the benchmarking of optimization algorithms are considered [13]. The results achieved at an early stage in the development of the subject can be judged according to work by the following researchers: Nash and Nocedal [14], Billups et al. [15], Conn et al. [16], Sandu et al. [17], Mittelmann [18], Vanderbei and Shanno [19], and Bondarenko et al. [20].The beginning of a new stage of development is associated with research work of Dolan and Moré [21], in which a performance profile comparison technique was proposed. This technique is now prevalent (but see, e.g., Gould and Scott [22]). Along with the performance profile comparison method, other more direct approaches have also been used in modern research. An idea of the modern research in the area under consideration can be obtained from the following research examples: Moles et al. [23], Mittelmann [24], Benson et al. [25], Kämpf et al. [26], Foster et al. [27], Rios and Sahinidis [28], Weise et al. [29], Sala et al. [12], and Cheshmi et al. [30]. A critical overview of the current state in the subject area was provided by Beiranvand et al. [1].At the end of this brief overview, this study focuses on benchmarking for solvers of only the optimization problem. However, the concept of benchmarking has a much broader context (see, e.g.,https://en.wikipedia.org/wiki/Benchmarking). The approach proposed in this article is quite general and can also be applied in other areas, but we do not consider this possibility here.


## 1.3. Notation

Throughout the article, the following general notation is used:ℕ is a set of natural numbers, and for a natural number n∈ℕ, we denote an n-dimensional vector space by ℝn and ⋅p is the lp−norm in ℝn. If not otherwise mentioned, we identify a finite set A with set ℕn=1,…,n, where n=A is the capacity of set A. We also introduce the following notations for special vectors and sets: for any n∈ℕ:0n=0,…,0︸n∈ℝn,1n=1,…,1︸n∈ℝn,Δn=ξ∈ℝ+n|∑k=1nξk, Δn∘=Δn∩intℝ+n, and ℝ+n⊂ℝn is a positive orthant. By necessity, we also identify the matrix Π∈ℝn×m with the map Π:ℕn×ℕm⟶ℝ. For a matrix Π∈ℝn×m, we denote its transpose by ΠT∈ℝm×n.


## 1.4. Outline

The remainder of this paper is structured as follows. In Section2, all necessary theoretical preliminaries regarding the MCDM problem (Section 2.1) and ranking-theory methods for solving MCDM problems are presented (Section 2.2). Section 3 introduces the concept of benchmarking contexts, and its relationship with the MCDM problem is discussed. In Section 4, the case-study problem of DE algorithm benchmarking is investigated numerically. Finally, the conclusions are presented in Section 5.


## 2. Methodology

### 2.1. Multicriteria Decision-Making Problems

We use the following notation from the general theory of multicriteria optimization theory [31]. We consider the MCDM problem A,C, where A=a1,…,am is a set of alternatives, and C=c1,…,cn is a set of criteria, that is, ci:A⟶ℝ,i=1,…,n. Hence, we introduce the following decision matrix:(1)X=x11x12⋯x1nx21x22⋯x2n⋮⋮⋱⋮xm1xm2⋯xmn,where xij=cjai is the performance measure of alternative i∈ℕm on criterion j∈ℕn. Without loss of generality, we assume that the lower value is preferable for each criterion (i.e., each criterion is not beneficial; see [32]), and the goal of the decision-making procedure is to minimize all criteria simultaneously. Furthermore, A is the set of admissible alternatives, and map c⟶=c1,…,cn:A⟶ℝn is the criterion map (correspondingly, c⟶A⊂ℝn is the set of admissible values of criteria). A point ξI=ξ1I,…,ξnI∈ℝn, where ξjI=mina∈Acja,j∈ℕn, is called the ideal point. An ideal point is considered attainable if alternative aI∈A exists such that ξI=c⟶aI. The following concepts are also associated with the criterion map and set of alternatives. An alternative a∗∈A is Pareto-optimal (efficient) if a∈A exists such that cja≤cja∗ for all j∈ℕn and cka<cka∗ for some k∈ℕn. The set of all efficient alternatives is denoted as Ae and is called the Pareto set. Correspondingly, fAe is called an efficient front.Pareto optimality is an appropriate concept for solutions to MCDM problems in general. However, the setAe of Pareto-optimal alternatives is very large, and all alternatives from Ae must be considered “equally good solutions.” However, the final decision must be unique. Hence, additional factors must be considered to aid in selecting specific or more favorable alternatives from the set Ae. We cannot provide a detailed analysis of these methods; however, interested readers can become acquainted with them through overviews [4–8]. Furthermore, we consider only the method proposed by Gogodze [3] without diminishing the value of more classical methods.


### 2.2. Ranking Methods and Their Applications to MCDM Problems

This section provides a brief overview of the basic concepts of the ranking theory (e.g., see [33] for further details) and presents the necessary formal definitions. For a natural number N, the matrix S=Sij,1≤i,j≤N is a score matrix if Sij≥0,Sii=0,1≤i,j≤N, and the pair ℕN,S is the ranking problem. We assume (conditionally) that the elements of ℕN are athletes (or sports teams) who compete in matches between themselves. Moreover, Mi,j denotes a joint match for each pair of athletes i,j,1≤i,j≤N, and we interpret entry Sij,1≤i,j≤N, of matrix S as the total score of athlete i against athlete j in match Mi,j. In addition, athlete i scored against athlete j in match Mi,j if Sij>0, and athlete i has beaten athlete j in match Mi,j if Sij>Sji. Based on the introduced notation, we define the following quantities:(2)G=S+ST,i.e.,G=GS=GijS,GijS=Sij+Sji,1≤i,j≤N;gS=g1S,…,gNS,giS=∑j=1NGijS,1≤i≤N.The weak order on the setℕN is transitive and the complete relation R⊂ℕN×ℕN. The relation RNS⊂ℕN×ℕN is a ranking method if, for any given ranking problem ℕN,S,RNS is a weak order on the set ℕN. Any vector r=r1,…,rN∈ℝN can be considered a rating vector for elements of ℕN, in the sense that each ri,1≤i≤N, can be interpreted as a measure of the performance of player i∈ℕN. For the ranking problem ℕN,S, a ranking method RNS is induced by the rating vector r∈ℝN if i,j∈RNS (i.e., RNS ranks i weakly above j) if and only if ri≥rj.For illustrative purposes, we consider only a few of the many ranking methods discussed in the literature. All of these methods are induced by their corresponding rating vectors. The considered ranking methods originate from different areas, such as athlete/team ranking in sports, citation indices, and website ranking. Hence, all of these reflect some (intuitive as a rule) human experience regarding the solution concept of the ranking problem. A brief overview of the ranking methods in this article is provided in Appendix.We can unite all the information described above and demonstrate that, for any MCDM problem, we can construct the necessary matrices (e.g.,S, PS,andAS) and, therefore, apply a suitable ranking method for the MCDM problem solution. To simplify the perception of the constructions described below, we use sports terminology. We assume that A,C is an MCDM problem (see Section 2.1) with a set of alternatives A=a1,…,am and a set of nonbeneficial criteria C=c1,…,cn and that the decision-making goal is to minimize the criteria simultaneously. We imagine that the number of athletes is N=m for constructing matrix S and that they are competing in an n-athlon (i.e., each match Mi⋅j includes competitions in n different disciplines, 1≤i,j≤n). For illustrative purposes, we introduce the simplest method for score calculation:(3)Sij=∑k∈ℕnsijk,wheresijk=1,ckai<ckaj0,ckai≥ckaj,k∈ℕn,i,j∈ℕm.Thus, for criterionk∈ℕn, the equality sijk=1 means that ckai<ckaj and the alternative ai (i.e., athlete i∈ℕm) receives one point (i.e., athlete i∈ℕm wins the competition in discipline k∈ℕn). Correspondingly, Sij indicates the number of total wins of athlete i∈ℕm in match Mi,j). Thus, m≥Sij≥0,Sii=0,∀i,j∈ℕm. An alternative ai (athlete i∈ℕm) has defeated an alternative aj (athlete j∈ℕm) if Sij>Sji. In addition, the result of match Mi,j is Sij wins by athlete i∈ℕm (losses of athlete j∈ℕm), Sji wins of athlete j∈ℕm (losses of athlete i∈ℕm), and the number of draws is m−Sij−Sji. The constructed matrix S=Sij,1≤i,j≤m, is the score matrix for a set of alternatives.Thus, we can define an auxiliary matrixΠS=ΠijS,1≤i,j≤m, where(4)ΠijS=Sij+m−Sij−Sji2,i≠j;0,i=j;,∀i,j∈ℕm.Furthermore, using matrixΠS and a well-known transformation, we can construct a (row) stochastic matrix P=PS as follows: PS=ΛΠS1m+πS−1ΠS+πSξT, where a vector ξ∈Δ∘m (usually ξ=1/m1m), and πS=π1S,…,πmS is a vector defined as follows:(5)πiS=1,ifithrow ofΠSis0m,0,otherwise.The introduced matrixΠS can be interpreted as an adjacency matrix for a directed graph ΓA,C (associated with the MCDM problem A,C), called the adjacency matrix for the MCDM problem A,C. Correspondingly, matrix PS can be interpreted as a transition probability matrix for the Markov chain determined by the graph ΓA,C. Moreover, we can construct a reciprocal matrix of pairwise comparisons AS=aij,i,j=1,…,m, for the MCDM problem A,C as follows:(6)aij=expΠij−m2i≠j;1,i=j;,i,j=1,…,m.Subject to the facts presented in this section, the following procedure for solving the MCDM problem under consideration,A,C, can be formulated:(i)
For the MCDM problemA,C, the score matrix S=Sij,1≤i,j≤m, is constructed(ii)
Using the score matrixS, the alternatives from set A are ranked using a ranking method R (R∈RS,RN,RB,RC,RK,RPF,RGM,…,; see, e.g., Appendix)(iii)
The alternative from the Pareto set,Ae, ranked best by method R is declared the R solution of the considered MCDM problem


## 2.1. Multicriteria Decision-Making Problems

We use the following notation from the general theory of multicriteria optimization theory [31]. We consider the MCDM problem A,C, where A=a1,…,am is a set of alternatives, and C=c1,…,cn is a set of criteria, that is, ci:A⟶ℝ,i=1,…,n. Hence, we introduce the following decision matrix:(1)X=x11x12⋯x1nx21x22⋯x2n⋮⋮⋱⋮xm1xm2⋯xmn,where xij=cjai is the performance measure of alternative i∈ℕm on criterion j∈ℕn. Without loss of generality, we assume that the lower value is preferable for each criterion (i.e., each criterion is not beneficial; see [32]), and the goal of the decision-making procedure is to minimize all criteria simultaneously. Furthermore, A is the set of admissible alternatives, and map c⟶=c1,…,cn:A⟶ℝn is the criterion map (correspondingly, c⟶A⊂ℝn is the set of admissible values of criteria). A point ξI=ξ1I,…,ξnI∈ℝn, where ξjI=mina∈Acja,j∈ℕn, is called the ideal point. An ideal point is considered attainable if alternative aI∈A exists such that ξI=c⟶aI. The following concepts are also associated with the criterion map and set of alternatives. An alternative a∗∈A is Pareto-optimal (efficient) if a∈A exists such that cja≤cja∗ for all j∈ℕn and cka<cka∗ for some k∈ℕn. The set of all efficient alternatives is denoted as Ae and is called the Pareto set. Correspondingly, fAe is called an efficient front.Pareto optimality is an appropriate concept for solutions to MCDM problems in general. However, the setAe of Pareto-optimal alternatives is very large, and all alternatives from Ae must be considered “equally good solutions.” However, the final decision must be unique. Hence, additional factors must be considered to aid in selecting specific or more favorable alternatives from the set Ae. We cannot provide a detailed analysis of these methods; however, interested readers can become acquainted with them through overviews [4–8]. Furthermore, we consider only the method proposed by Gogodze [3] without diminishing the value of more classical methods.


## 2.2. Ranking Methods and Their Applications to MCDM Problems

This section provides a brief overview of the basic concepts of the ranking theory (e.g., see [33] for further details) and presents the necessary formal definitions. For a natural number N, the matrix S=Sij,1≤i,j≤N is a score matrix if Sij≥0,Sii=0,1≤i,j≤N, and the pair ℕN,S is the ranking problem. We assume (conditionally) that the elements of ℕN are athletes (or sports teams) who compete in matches between themselves. Moreover, Mi,j denotes a joint match for each pair of athletes i,j,1≤i,j≤N, and we interpret entry Sij,1≤i,j≤N, of matrix S as the total score of athlete i against athlete j in match Mi,j. In addition, athlete i scored against athlete j in match Mi,j if Sij>0, and athlete i has beaten athlete j in match Mi,j if Sij>Sji. Based on the introduced notation, we define the following quantities:(2)G=S+ST,i.e.,G=GS=GijS,GijS=Sij+Sji,1≤i,j≤N;gS=g1S,…,gNS,giS=∑j=1NGijS,1≤i≤N.The weak order on the setℕN is transitive and the complete relation R⊂ℕN×ℕN. The relation RNS⊂ℕN×ℕN is a ranking method if, for any given ranking problem ℕN,S,RNS is a weak order on the set ℕN. Any vector r=r1,…,rN∈ℝN can be considered a rating vector for elements of ℕN, in the sense that each ri,1≤i≤N, can be interpreted as a measure of the performance of player i∈ℕN. For the ranking problem ℕN,S, a ranking method RNS is induced by the rating vector r∈ℝN if i,j∈RNS (i.e., RNS ranks i weakly above j) if and only if ri≥rj.For illustrative purposes, we consider only a few of the many ranking methods discussed in the literature. All of these methods are induced by their corresponding rating vectors. The considered ranking methods originate from different areas, such as athlete/team ranking in sports, citation indices, and website ranking. Hence, all of these reflect some (intuitive as a rule) human experience regarding the solution concept of the ranking problem. A brief overview of the ranking methods in this article is provided in Appendix.We can unite all the information described above and demonstrate that, for any MCDM problem, we can construct the necessary matrices (e.g.,S, PS,andAS) and, therefore, apply a suitable ranking method for the MCDM problem solution. To simplify the perception of the constructions described below, we use sports terminology. We assume that A,C is an MCDM problem (see Section 2.1) with a set of alternatives A=a1,…,am and a set of nonbeneficial criteria C=c1,…,cn and that the decision-making goal is to minimize the criteria simultaneously. We imagine that the number of athletes is N=m for constructing matrix S and that they are competing in an n-athlon (i.e., each match Mi⋅j includes competitions in n different disciplines, 1≤i,j≤n). For illustrative purposes, we introduce the simplest method for score calculation:(3)Sij=∑k∈ℕnsijk,wheresijk=1,ckai<ckaj0,ckai≥ckaj,k∈ℕn,i,j∈ℕm.Thus, for criterionk∈ℕn, the equality sijk=1 means that ckai<ckaj and the alternative ai (i.e., athlete i∈ℕm) receives one point (i.e., athlete i∈ℕm wins the competition in discipline k∈ℕn). Correspondingly, Sij indicates the number of total wins of athlete i∈ℕm in match Mi,j). Thus, m≥Sij≥0,Sii=0,∀i,j∈ℕm. An alternative ai (athlete i∈ℕm) has defeated an alternative aj (athlete j∈ℕm) if Sij>Sji. In addition, the result of match Mi,j is Sij wins by athlete i∈ℕm (losses of athlete j∈ℕm), Sji wins of athlete j∈ℕm (losses of athlete i∈ℕm), and the number of draws is m−Sij−Sji. The constructed matrix S=Sij,1≤i,j≤m, is the score matrix for a set of alternatives.Thus, we can define an auxiliary matrixΠS=ΠijS,1≤i,j≤m, where(4)ΠijS=Sij+m−Sij−Sji2,i≠j;0,i=j;,∀i,j∈ℕm.Furthermore, using matrixΠS and a well-known transformation, we can construct a (row) stochastic matrix P=PS as follows: PS=ΛΠS1m+πS−1ΠS+πSξT, where a vector ξ∈Δ∘m (usually ξ=1/m1m), and πS=π1S,…,πmS is a vector defined as follows:(5)πiS=1,ifithrow ofΠSis0m,0,otherwise.The introduced matrixΠS can be interpreted as an adjacency matrix for a directed graph ΓA,C (associated with the MCDM problem A,C), called the adjacency matrix for the MCDM problem A,C. Correspondingly, matrix PS can be interpreted as a transition probability matrix for the Markov chain determined by the graph ΓA,C. Moreover, we can construct a reciprocal matrix of pairwise comparisons AS=aij,i,j=1,…,m, for the MCDM problem A,C as follows:(6)aij=expΠij−m2i≠j;1,i=j;,i,j=1,…,m.Subject to the facts presented in this section, the following procedure for solving the MCDM problem under consideration,A,C, can be formulated:(i)
For the MCDM problemA,C, the score matrix S=Sij,1≤i,j≤m, is constructed(ii)
Using the score matrixS, the alternatives from set A are ranked using a ranking method R (R∈RS,RN,RB,RC,RK,RPF,RGM,…,; see, e.g., Appendix)(iii)
The alternative from the Pareto set,Ae, ranked best by method R is declared the R solution of the considered MCDM problem


## 3. Benchmarking Problem

We consider a setP of problems, a set S of solvers, and a function J:S×P⟶ℝ, the assessment function (performance metric). The terms “solver,” “problem,” and “assessment function” are used conditionally only to simplify interpretation, although this is not generally necessary (and, as we observe below, can even lead to terminological inconsistency). Furthermore, we assume for definiteness that the high and low values of J correspond to the worst and best cases, respectively, and for convenience, we interpret Js,p as the cost of solving the problem p∈P by the solver s∈S. Moreover, the following conditions are assumed:(i)
Slovers∈S solves problem p∈P better than solver s∗∈S,ifJs,p<Js∗,p(ii)
Problemp∈P is easier for solver s∈S than problem p∗∈P,ifJs,p<Js,p∗Thus, we can introduce the following definition, which is sufficient for many real-world applications.Definition 1.
A tripleS,P,J is in the (solvers) benchmarking context if and only if S and P are the finite sets (called a set of solvers and set of problems, respectively), J:S×P⟶ℝ is a function (called the assessment function, or performance evaluation metric), and the following assumptions hold:(7)A0P=ℕn,S=ℕm,A1Js,p≥0,∀s,p∈S×P.
The presented concept is quite general and, as mentioned, emphasizes that the set of solvers, set of problems, and assessment function must be considered closely related objects for the benchmarking goal and not independently. AssumptionA0 establishes that sets SandP have sizes m,n∈ℕ, respectively, and Assumption A1 establishes the nonnegativity of the assessment function. Moreover, because sets SandP are finite, Condition A1 does not limit the generality of our considerations. Generally, the selection of a benchmarking context S,P,J component is based on the research questions motivated by a benchmarking analysis goal. However, the choice of sets SandP is often a disputable issue in the practice of certain applications. In contrast, the situation is relatively straightforward in choosing the assessment function, J, at least in computer science (see, e.g., [34]). For example, the following indicators are often used in this case: running time (e.g., the CPU time [35]), reliability (i.e., the solver’s ability to successfully solve several problems, such as the success rate [36]), and others. Moreover, the case when assessment, J, is a mapping in ℝl,wherel∈ℕ (i.e., it is a multiple criterion), also can be considered but we do not delve into this issue. Next, we consider the benchmarking context S,P,J as given, and introduce the following definition:Definition 2.
For a given (solver) benchmarking contextS,P,J, we define function J∗:P×S⟶ℝ as follows: J∗p,s=Js,p,∀p∈P,∀s∈S. We call J∗ the adjoint (to J) assessment function, and P,S,J∗ is the adjoint to the S,P,J benchmarking context or problem benchmarking context (corresponding to the solver benchmarking context S,P,J).
Definition2 is easily validated as correct (i.e., J∗ is the assessment function in the sense of Definition 1). Terminological inconsistency appears, as noted above. In the benchmarking context P,S,J∗, the set of solvers is set P, which is the set of problems in the sense of the benchmarking context S,P,J. We hope that this does not create any problems in understanding the text below.
We assume now that a benchmarking contextS,P,J is given and build a corresponding MCDM problem A,C as follows: A=S is a set of alternatives, and C=cp|p∈P,cp⋅=J⋅,p:A⟶ℝ,∀p∈P is a set of criteria. Hence, we define the decision matrix as a matrix whose elements exhibit the performance of different alternatives (i.e., solvers) with respect to various criteria (i.e., problems) through the assessment function. From Property A1, cps≥0∀s∈S,0∀p∈P In contrast, we assume that A,C, where A=a1,…,am and C=c1,…,cn, is a given MCDM problem such that cka≥0∀a∈A=ℕnand∀k∈ℕn=C. Hence, for P=ℕn,S=ℕm, and Ji,k=ckai∀i∈ℕn,∀k∈ℕn, triplet S,P,J is a benchmarking context corresponding to the MCDM problem A,C. The correspondences described above are one-to-one and reciprocal. Thus, we prove that the following proposition holds.Proposition 1.
One-to-one mapping exists between the benchmarking contexts and MCDM problems with nonnegative criteria.
To summarize the results of this section and achieve greater clarity in the presentation, we formulated the proposed approach to solving benchmarking problems in an algorithmic form. Furthermore, we assumed that the considered benchmarking problem has already been formalized as a benchmarking contextS,P,J, where S is a set of solvers, P is a set of problems, and J is an assessment function. The flowchart of the algorithm is presented in Figure 1. All elements of the Pareto set, Ae, are considered equally “good” solvers (in the sense of Pareto optimality). However, the R ranking allows detailed classification to define the “best of the good,” “worst of the good,” and other intermediate “good” solvers.Figure 1
Algorithm flowchart for solving a benchmarking problem.


## 4. Case Study: Benchmarking Differential Evolution Algorithms

### 4.1. Data

In this section, we focus on an illustrative example of the proposed approach in Section2. Our consideration is based on the results of numerical experiments borrowed from Sala et al. [12], where nine optimization DE algorithms and 25 test functions were considered (see Table 1) for a short description of the test functions. The set of solvers in the benchmarking problem under consideration is the set of the following algorithms:(i)
S1-DE: rand/1/bin differential evolution [37],(ii)
S2-DE2: best/2/bin differential evolution [38],(iii)
S3-jDE: self-adapting differential evolution [39],(iv)
S4-JADE: adaptive differential evolution [40],(v)
S5-SaDE: strategy adaptation differential evolution [41],(vi)
S6-epsDE: ensemble parameter differential evolution [42],(vii)
S7-CoDe: composite trial vector strategy differential evolution [43],(viii)
S8-SQG: stochastic quasigradient search [44], and(ix)
S9-SQG-DE: stochastic quasigradient-based differential evolution [12].Table 1
Test functions.
Short descriptionF1Shifted sphere functionF2Shifted Schwefel’s problem 1.2F3Shifted rotated high conditioned elliptic functionF4Shifted Schwefel’s problem 1.2 (with noise in fitness function)F5Schwefel’s problem 2.6 with the global optimum on the boundsF6Shifted Rosenbrock’s functionF7Shifted rotated Griewank’s functionF8Shifted rotated Ackley’s function (with the global optimum on the bounds)F9Shifted Rastrigin’s functionF10Shifted rotated Rastrigin’s functionF11Shifted rotated Weierstrass functionF12Schwefel’s problem 2.13F13Expanded extended Griewank’s plus Rosenbrock’s functionF14Shifted rotated expanded Schaffer’sF6F15Hybrid composition functionF16Rotated hybrid composition functionF17Rotated hybrid composition function (with noise in fitness function)F18Rotated hybrid composition functionF19Rotated hybrid composition functions (with the global optimum on the bounds)F20Rotated hybrid composition function (with a narrow basin for the global optimum)F21Rotated hybrid composition functionF22Rotated hybrid composition function (with a high condition number matrix)F23Noncontinuous rotated hybrid composition functionF24Rotated hybrid composition functionF25Rotated hybrid composition functionNote:F1, …, F25 are the test functions. Source: Sala et al. [12].Thus,S=S1,…,S9 is a set of solvers. The set of problems P=P1,…,P50 comprises 50 problems, and each problem is defined by the dimension indicator d=30,50 and by the test function types F1,…,F25, as listed in Table 2.Table 2
Problem description.
ProblemDim-onTest functionProblemDim-onTest functionProblemDim-onTest functionProblemDim-onTest functionProblemDim-onTest functionP130F1P1130F11P2130F21P3150F6P4150F16P230F2P1230F12P2230F22P3250F7P4250F17P330F3P1330F13P2330F23P3350F8P4350F18P430F4P1430F14P2430F24P3450F9P4450F19P530F5P1530F15P2530F25P3550F10P4550F20P630F6P1630F16P2650F1P3650F11P4650F21P730F7P1730F17P2750F2P3750F12P4750F22P830F8P1830F18P2850F3P3850F13P4850F23P930F9P1930F19P2950F4P3950F14P4950F24P1030F10P2030F20P3050F5P4050F15P5050F25A description of the assessment function used by Sala et al. [12] is as follows: first, the expected running time (ERT), a widely used performance metric for optimization algorithms, is defined as follows:(8)ERTτ=meanMτ+1−qqNmax,q=NsuccesNtotal,where τ indicates a reference threshold value, Mτ is the number of function evaluations required to reach an objective value better than τ (e.g., successful runs), Nmax denotes the maximum number of function evaluations per optimization run,Nsucces represents the number of successful runs, Ntotal is the total number of runs, and q denotes the named success rate [45]. The ERT is interpreted as the expected number of function evaluations of an algorithm to reach an objective function threshold for the first time. A threshold or success criterion is required for the ERT performance measure. However, unlike conventional optimization problems (where the ERT criterion is usually related to reaching the value of the known global optimum within a specified tolerance), the probability of coming close to the global optimum is negligible for difficult optimization problems, and a more acceptable alternative success criterion is required. Moreover, all compared algorithms must meet the success criterion a few times to compare qualitative performance using ERT for difficult optimization problems. Correspondingly, Sala et al. [12] used the success criterion to reach the target value corresponding to the expected value of the best objective function value from the uniform random sampling (1000 samples). Next, the estimation of the expected objective value ERSEf for test function f is based on 100 repetitions. Finally, the ERT with respect to this objective function value limit was referred to as ERTRSE for test function f. The dataset of ERTRSE estimations [12] for the above-described solvers and problems is presented in Table 3.Table 3
ERTRSE metric.
S1S2S3S4S5S6S7S8S9P11165724049491264329904606202168P27401115677393093798943653137318P365363276360635651911481045135210P46182133265702853426621712694310P543424766536311527871564459160P6740411728491234315807603124168P725612448231059687916932365107P828773011178320842673272020821322771P91573524058467269380818726126193P101165824054474256320850630201172P1124141555196715021321154119793681949P121072934509342416931594128225P131570910150524224231723898161289P147497191742735173515092366637968991658P154373736683665658574581016185P16299911671490335615689616219179P176925116705143625728456939096178P1810171036501314460741341263143P1912711045533317551836389259148P20119010984913155451039384284154P21946624251498253327901597301175P222433288948928138973060213320202P231365024194474254325802586664181P247785444954427237691157310183187P252201154453045548551675321109P26190309054439205254674579192178P27905581455723163889082135127296P28381910317514289455764566121145P29190591017553834143492029311332310P309173190405682943669641418451214P311155713327491235244831609132182P3239418744328953688423124041109P3317322347209817922724252227401171960P341571919060482245295845738123194P352407124059456235306739661169188P3620242568218713241814182516753471331P37118312635603404181132774119224P38738190575142271936041139145336P397476158241792131011981296348247061808P40341291557354556852331205173P41750611568495320487738593260156P4211585323696403275157948095743192P4310264191356313193801071892352226P44243517387511290389866728307210P451930713407533321372915794380227P46135719089486243320871605325176P473311506856429143175572419048153P4874687544483248333880590537170P4915709133354982312457846888170201P50304163488315552103821013368109Note:S1, …, S9 are solvers, P1, …, P50 are problems, and ERTRSE metric is assessment function (as described in the main text of the article, see Section 4.1). Source: Sala et al. [12].Thus, the benchmarking contextS,P,J, where S=s1,…,s9,P=p1,…,p50, and J is the ERTRSE assessment, is fully defined. Hence, in Section 3, the MCDM problem associated with the benchmarking problem under consideration is fully defined with a set of alternatives A=S=ℕ9 a set of (nonbeneficial) criteria C=P=ℕ50, and a primary decision matrix obtained by transposing the matrix/table presented in Table 3, which is the transposed primary decision matrix Z=zij,i∈ℕ9,j∈ℕ50, for writing convenience. Hence, the MCDM problem associated with the benchmarking context S,P,J (i.e., the solver benchmarking problem) is fully defined. The benchmarking context P,S,J∗ is analogously defined, where the assessment function J∗ is obtained based on the decision matrix Z∗ (which is the transpose of the decision matrix Z defined above). Hence, the MCDM problem associated with this benchmarking context (i.e., the benchmark problem for the problems) is also fully defined.


### 4.2. Calculation Results

In this section, we present a brief description of the calculation results (all calculations related to the case study were calculated in the MATLAB environment using standard equipment: laptop with 2.59 GHz, 8 GB RAM, and a 64 bit operation system and required a few seconds (4.87 s for the solver benchmarking and 5.04 s for the problem benchmarking for calculating all considered rankings without special code optimization measures). First, we consider the solver benchmarking problem and explain the construction of the normalized decision matrix by transforming the primary dataset (see, e.g., [32]).For the primary decision matrixZ=zij, we define the normalized decision matrix X=xijasxij=zij−lj/uj−lj where uj=maxi∈ℕ9zij,lj=mini∈ℕ9zij,j∈ℕ50. For the solver benchmarking problem, we consider all criteria to be nonbeneficial (i.e., minimizable). We consider a solver to be better if it solves a given problem in less time ERTRSE.To illustrate this, we present the score matrix for the solver benchmarking problem in Table4. Table 5 presents the obtained RS,RN,RB,RC,RK,RPF,andRGM ranks for the solver benchmarking problem.Table 4
Score matrix for the solver benchmarking problem.Table 5
Solver ranking using the proposed methods.
RankingRSRNRBRCRKRPFRGMS18988888S29899999S35555555S42223322S54444434S67777777S76666666S83332243S91111111Note: the Pareto-optimal solvers are gray marked.Analogously, we consider the problem benchmarking but define the normalized decision matrixX=xij as follows: xij=zij∗−lj∗/uj∗−lj∗ where uj∗=maxi∈ℕ50zij∗,lj∗=mini∈ℕ50zij∗, and Z∗=zij∗, is the corresponding primary decision matrix. For the benchmarking problem, we also assume that all criteria are nonbeneficial (i.e., minimizable). Again, a problem is better (i.e., easier) for a given solver if it is solved in less time ERTRSE by this solver. Table 6 presents the RS,RN,RB,RC,RK,RPF,andRGM ranks for the problem benchmarking (the score matrix for the problem benchmarking is not presented).Table 6
Problem ranking using the proposed methods.
RankingRSRNRBRCRKRPFRGMP124252525272524P238373740383738P342434243434142P434343435343534P526262627262625P64447634P77775577P845444548454645P925242424232326P1018161812141818P1147474747474547P1222232228252122P1320202018172220P1450505050505050P1533323331323233P1627272723242827P1737383836363837P183334443P1991291513119P2013151314151513P2129302926302929P2214141422161314P2323212321222423P2431313132313331P252222222P261111111P2736363638373636P286666766P2948484844484848P3039393937393939P31888111088P325553355P3344404449424244P3419191919192019P351713178111717P3646464645464746P3732333233332732P3811911981411P3949494946494949P4016181620201015P4121222116211921P4241414142414341P4343454341444443P4435353534353435P4540424039404040P4615171517181616P4728282830293128P4810111013121210P4930293029283030P50121012109912Note: the Pareto-optimal problems are gray marked.


### 4.3. Discussion

As Table5 indicates, the results of solver ranking using the considered methods RS,RN,RB,RC,RK,RPF,andRGM are somewhat similar. This observation was confirmed quantitatively by considering the Spearman correlations between ranks (Table 7), where the correlations of the solver ranks for the RS,RN,RB,RC,RK,RPF,andRGM rankings are presented. As Table 7 demonstrates, the RS,RN,RB,RC,RK,RPF,andRGM ranks are strongly correlated with each other. Analogously, Table 8 reflects the interrelation between ranks for problem benchmarking. In particular, RS,RN,RB,RC,RK,RPF,andRGM ranks are strongly correlated with each other.Table 7
Spearman correlations for the solver benchmarking problem.
RanksRSRNRBRCRKRPFRGMRS1RN0.9831RB0.9990.9831RC0.9830.9670.9831RK0.9830.9670.9830.9991RPF0.9830.9670.9830.9500.9501RGM0.9990.9830.9990.9830.9830.9831Table 8
Spearman correlations for the benchmarking problem.
RanksRSRNRBRCRKRPFRGMRS1RN0.9961RB0.9990.9961RC0.9770.9800.9771RK0.9900.9960.9910.9891RPF0.9930.9890.9930.9680.9821RGM0.9990.9950.9990.9770.9900.9931Regarding the results of the correlation analysis, the observed similarity of the ranking results forRS,RN,RB,RC,RK,RPF,andRGM ranking methods appears very intriguing, given that these methods have completely different areas of origin and underlying ideas (see the corresponding scholium in Appendix). It is interesting to consider the Pareto optimization results (see the solvers and problems marked in gray in Table 5 and 4, respectively). In particular, from Table 5, all considered solvers were Pareto-optimal (i.e., they are considered “equally good” in the considered benchmarking context). We believe that this is due to the large (compared to the number of solvers) number of problems (i.e., too many criteria exist in the corresponding MCDM problem) and, accordingly, each solver is good in “its own way.” However, ranking methods enable the establishment of an appropriate hierarchy among solvers. Analogously, Table 6 demonstrates that Pareto-optimal problems are allocated to different groups or clusters, indicating similar problems belonging to the same clusters. Ranking methods also make it possible to establish an appropriate hierarchy among the problems.Summarizing the results of the case-study investigation, we conclude the following:(i)
The results of the calculations (Table5) confirm that the SQG-DE algorithm (solver S9) is the best in the considered benchmarking context (for comparison, see [12]), and this conclusion is correct for all rankings used in this study, despite their quite different natures. Moreover, the worst results are DE2 (solver S2) according to all considered ranking methods, excluding Neustadt’s method, and DE (solver S1) according to Neustadt’s ranking method.(ii)
Unlike Sala et al. [12], where the analysis of the problems was not carried out, our calculations also indicate (Table 6) that the best problems in the considered benchmarking context (in the sense of a lower value of the considered metric) are the shifted sphere function in Dimension 50 (problem 26) and the rotated hybrid composition function in Dimension 30 (problem 25). Accordingly, the worst ones are the shifted rotated expanded Schaffer’s function 6 in Dimension 30 (problem P14), and the next worst ones are the shifted rotated Ackley’s function in Dimension 50 (problem P33) (by the Colley ranking method) and the shifted rotated expanded Schaffer’s function 6 in Dimension 50 (problem P39) (for all other considered ranking methods).We stress that these results were obtained using only the ranking-theory methods without an analysis of any statistical indicators of the assessment function values, as currently practiced (see, e.g., the related literature overview in the Introduction section).


## 4.1. Data

In this section, we focus on an illustrative example of the proposed approach in Section2. Our consideration is based on the results of numerical experiments borrowed from Sala et al. [12], where nine optimization DE algorithms and 25 test functions were considered (see Table 1) for a short description of the test functions. The set of solvers in the benchmarking problem under consideration is the set of the following algorithms:(i)
S1-DE: rand/1/bin differential evolution [37],(ii)
S2-DE2: best/2/bin differential evolution [38],(iii)
S3-jDE: self-adapting differential evolution [39],(iv)
S4-JADE: adaptive differential evolution [40],(v)
S5-SaDE: strategy adaptation differential evolution [41],(vi)
S6-epsDE: ensemble parameter differential evolution [42],(vii)
S7-CoDe: composite trial vector strategy differential evolution [43],(viii)
S8-SQG: stochastic quasigradient search [44], and(ix)
S9-SQG-DE: stochastic quasigradient-based differential evolution [12].Table 1
Test functions.
Short descriptionF1Shifted sphere functionF2Shifted Schwefel’s problem 1.2F3Shifted rotated high conditioned elliptic functionF4Shifted Schwefel’s problem 1.2 (with noise in fitness function)F5Schwefel’s problem 2.6 with the global optimum on the boundsF6Shifted Rosenbrock’s functionF7Shifted rotated Griewank’s functionF8Shifted rotated Ackley’s function (with the global optimum on the bounds)F9Shifted Rastrigin’s functionF10Shifted rotated Rastrigin’s functionF11Shifted rotated Weierstrass functionF12Schwefel’s problem 2.13F13Expanded extended Griewank’s plus Rosenbrock’s functionF14Shifted rotated expanded Schaffer’sF6F15Hybrid composition functionF16Rotated hybrid composition functionF17Rotated hybrid composition function (with noise in fitness function)F18Rotated hybrid composition functionF19Rotated hybrid composition functions (with the global optimum on the bounds)F20Rotated hybrid composition function (with a narrow basin for the global optimum)F21Rotated hybrid composition functionF22Rotated hybrid composition function (with a high condition number matrix)F23Noncontinuous rotated hybrid composition functionF24Rotated hybrid composition functionF25Rotated hybrid composition functionNote:F1, …, F25 are the test functions. Source: Sala et al. [12].Thus,S=S1,…,S9 is a set of solvers. The set of problems P=P1,…,P50 comprises 50 problems, and each problem is defined by the dimension indicator d=30,50 and by the test function types F1,…,F25, as listed in Table 2.Table 2
Problem description.
ProblemDim-onTest functionProblemDim-onTest functionProblemDim-onTest functionProblemDim-onTest functionProblemDim-onTest functionP130F1P1130F11P2130F21P3150F6P4150F16P230F2P1230F12P2230F22P3250F7P4250F17P330F3P1330F13P2330F23P3350F8P4350F18P430F4P1430F14P2430F24P3450F9P4450F19P530F5P1530F15P2530F25P3550F10P4550F20P630F6P1630F16P2650F1P3650F11P4650F21P730F7P1730F17P2750F2P3750F12P4750F22P830F8P1830F18P2850F3P3850F13P4850F23P930F9P1930F19P2950F4P3950F14P4950F24P1030F10P2030F20P3050F5P4050F15P5050F25A description of the assessment function used by Sala et al. [12] is as follows: first, the expected running time (ERT), a widely used performance metric for optimization algorithms, is defined as follows:(8)ERTτ=meanMτ+1−qqNmax,q=NsuccesNtotal,where τ indicates a reference threshold value, Mτ is the number of function evaluations required to reach an objective value better than τ (e.g., successful runs), Nmax denotes the maximum number of function evaluations per optimization run,Nsucces represents the number of successful runs, Ntotal is the total number of runs, and q denotes the named success rate [45]. The ERT is interpreted as the expected number of function evaluations of an algorithm to reach an objective function threshold for the first time. A threshold or success criterion is required for the ERT performance measure. However, unlike conventional optimization problems (where the ERT criterion is usually related to reaching the value of the known global optimum within a specified tolerance), the probability of coming close to the global optimum is negligible for difficult optimization problems, and a more acceptable alternative success criterion is required. Moreover, all compared algorithms must meet the success criterion a few times to compare qualitative performance using ERT for difficult optimization problems. Correspondingly, Sala et al. [12] used the success criterion to reach the target value corresponding to the expected value of the best objective function value from the uniform random sampling (1000 samples). Next, the estimation of the expected objective value ERSEf for test function f is based on 100 repetitions. Finally, the ERT with respect to this objective function value limit was referred to as ERTRSE for test function f. The dataset of ERTRSE estimations [12] for the above-described solvers and problems is presented in Table 3.Table 3
ERTRSE metric.
S1S2S3S4S5S6S7S8S9P11165724049491264329904606202168P27401115677393093798943653137318P365363276360635651911481045135210P46182133265702853426621712694310P543424766536311527871564459160P6740411728491234315807603124168P725612448231059687916932365107P828773011178320842673272020821322771P91573524058467269380818726126193P101165824054474256320850630201172P1124141555196715021321154119793681949P121072934509342416931594128225P131570910150524224231723898161289P147497191742735173515092366637968991658P154373736683665658574581016185P16299911671490335615689616219179P176925116705143625728456939096178P1810171036501314460741341263143P1912711045533317551836389259148P20119010984913155451039384284154P21946624251498253327901597301175P222433288948928138973060213320202P231365024194474254325802586664181P247785444954427237691157310183187P252201154453045548551675321109P26190309054439205254674579192178P27905581455723163889082135127296P28381910317514289455764566121145P29190591017553834143492029311332310P309173190405682943669641418451214P311155713327491235244831609132182P3239418744328953688423124041109P3317322347209817922724252227401171960P341571919060482245295845738123194P352407124059456235306739661169188P3620242568218713241814182516753471331P37118312635603404181132774119224P38738190575142271936041139145336P397476158241792131011981296348247061808P40341291557354556852331205173P41750611568495320487738593260156P4211585323696403275157948095743192P4310264191356313193801071892352226P44243517387511290389866728307210P451930713407533321372915794380227P46135719089486243320871605325176P473311506856429143175572419048153P4874687544483248333880590537170P4915709133354982312457846888170201P50304163488315552103821013368109Note:S1, …, S9 are solvers, P1, …, P50 are problems, and ERTRSE metric is assessment function (as described in the main text of the article, see Section 4.1). Source: Sala et al. [12].Thus, the benchmarking contextS,P,J, where S=s1,…,s9,P=p1,…,p50, and J is the ERTRSE assessment, is fully defined. Hence, in Section 3, the MCDM problem associated with the benchmarking problem under consideration is fully defined with a set of alternatives A=S=ℕ9 a set of (nonbeneficial) criteria C=P=ℕ50, and a primary decision matrix obtained by transposing the matrix/table presented in Table 3, which is the transposed primary decision matrix Z=zij,i∈ℕ9,j∈ℕ50, for writing convenience. Hence, the MCDM problem associated with the benchmarking context S,P,J (i.e., the solver benchmarking problem) is fully defined. The benchmarking context P,S,J∗ is analogously defined, where the assessment function J∗ is obtained based on the decision matrix Z∗ (which is the transpose of the decision matrix Z defined above). Hence, the MCDM problem associated with this benchmarking context (i.e., the benchmark problem for the problems) is also fully defined.


## 4.2. Calculation Results

In this section, we present a brief description of the calculation results (all calculations related to the case study were calculated in the MATLAB environment using standard equipment: laptop with 2.59 GHz, 8 GB RAM, and a 64 bit operation system and required a few seconds (4.87 s for the solver benchmarking and 5.04 s for the problem benchmarking for calculating all considered rankings without special code optimization measures). First, we consider the solver benchmarking problem and explain the construction of the normalized decision matrix by transforming the primary dataset (see, e.g., [32]).For the primary decision matrixZ=zij, we define the normalized decision matrix X=xijasxij=zij−lj/uj−lj where uj=maxi∈ℕ9zij,lj=mini∈ℕ9zij,j∈ℕ50. For the solver benchmarking problem, we consider all criteria to be nonbeneficial (i.e., minimizable). We consider a solver to be better if it solves a given problem in less time ERTRSE.To illustrate this, we present the score matrix for the solver benchmarking problem in Table4. Table 5 presents the obtained RS,RN,RB,RC,RK,RPF,andRGM ranks for the solver benchmarking problem.Table 4
Score matrix for the solver benchmarking problem.Table 5
Solver ranking using the proposed methods.
RankingRSRNRBRCRKRPFRGMS18988888S29899999S35555555S42223322S54444434S67777777S76666666S83332243S91111111Note: the Pareto-optimal solvers are gray marked.Analogously, we consider the problem benchmarking but define the normalized decision matrixX=xij as follows: xij=zij∗−lj∗/uj∗−lj∗ where uj∗=maxi∈ℕ50zij∗,lj∗=mini∈ℕ50zij∗, and Z∗=zij∗, is the corresponding primary decision matrix. For the benchmarking problem, we also assume that all criteria are nonbeneficial (i.e., minimizable). Again, a problem is better (i.e., easier) for a given solver if it is solved in less time ERTRSE by this solver. Table 6 presents the RS,RN,RB,RC,RK,RPF,andRGM ranks for the problem benchmarking (the score matrix for the problem benchmarking is not presented).Table 6
Problem ranking using the proposed methods.
RankingRSRNRBRCRKRPFRGMP124252525272524P238373740383738P342434243434142P434343435343534P526262627262625P64447634P77775577P845444548454645P925242424232326P1018161812141818P1147474747474547P1222232228252122P1320202018172220P1450505050505050P1533323331323233P1627272723242827P1737383836363837P183334443P1991291513119P2013151314151513P2129302926302929P2214141422161314P2323212321222423P2431313132313331P252222222P261111111P2736363638373636P286666766P2948484844484848P3039393937393939P31888111088P325553355P3344404449424244P3419191919192019P351713178111717P3646464645464746P3732333233332732P3811911981411P3949494946494949P4016181620201015P4121222116211921P4241414142414341P4343454341444443P4435353534353435P4540424039404040P4615171517181616P4728282830293128P4810111013121210P4930293029283030P50121012109912Note: the Pareto-optimal problems are gray marked.


## 4.3. Discussion

As Table5 indicates, the results of solver ranking using the considered methods RS,RN,RB,RC,RK,RPF,andRGM are somewhat similar. This observation was confirmed quantitatively by considering the Spearman correlations between ranks (Table 7), where the correlations of the solver ranks for the RS,RN,RB,RC,RK,RPF,andRGM rankings are presented. As Table 7 demonstrates, the RS,RN,RB,RC,RK,RPF,andRGM ranks are strongly correlated with each other. Analogously, Table 8 reflects the interrelation between ranks for problem benchmarking. In particular, RS,RN,RB,RC,RK,RPF,andRGM ranks are strongly correlated with each other.Table 7
Spearman correlations for the solver benchmarking problem.
RanksRSRNRBRCRKRPFRGMRS1RN0.9831RB0.9990.9831RC0.9830.9670.9831RK0.9830.9670.9830.9991RPF0.9830.9670.9830.9500.9501RGM0.9990.9830.9990.9830.9830.9831Table 8
Spearman correlations for the benchmarking problem.
RanksRSRNRBRCRKRPFRGMRS1RN0.9961RB0.9990.9961RC0.9770.9800.9771RK0.9900.9960.9910.9891RPF0.9930.9890.9930.9680.9821RGM0.9990.9950.9990.9770.9900.9931Regarding the results of the correlation analysis, the observed similarity of the ranking results forRS,RN,RB,RC,RK,RPF,andRGM ranking methods appears very intriguing, given that these methods have completely different areas of origin and underlying ideas (see the corresponding scholium in Appendix). It is interesting to consider the Pareto optimization results (see the solvers and problems marked in gray in Table 5 and 4, respectively). In particular, from Table 5, all considered solvers were Pareto-optimal (i.e., they are considered “equally good” in the considered benchmarking context). We believe that this is due to the large (compared to the number of solvers) number of problems (i.e., too many criteria exist in the corresponding MCDM problem) and, accordingly, each solver is good in “its own way.” However, ranking methods enable the establishment of an appropriate hierarchy among solvers. Analogously, Table 6 demonstrates that Pareto-optimal problems are allocated to different groups or clusters, indicating similar problems belonging to the same clusters. Ranking methods also make it possible to establish an appropriate hierarchy among the problems.Summarizing the results of the case-study investigation, we conclude the following:(i)
The results of the calculations (Table5) confirm that the SQG-DE algorithm (solver S9) is the best in the considered benchmarking context (for comparison, see [12]), and this conclusion is correct for all rankings used in this study, despite their quite different natures. Moreover, the worst results are DE2 (solver S2) according to all considered ranking methods, excluding Neustadt’s method, and DE (solver S1) according to Neustadt’s ranking method.(ii)
Unlike Sala et al. [12], where the analysis of the problems was not carried out, our calculations also indicate (Table 6) that the best problems in the considered benchmarking context (in the sense of a lower value of the considered metric) are the shifted sphere function in Dimension 50 (problem 26) and the rotated hybrid composition function in Dimension 30 (problem 25). Accordingly, the worst ones are the shifted rotated expanded Schaffer’s function 6 in Dimension 30 (problem P14), and the next worst ones are the shifted rotated Ackley’s function in Dimension 50 (problem P33) (by the Colley ranking method) and the shifted rotated expanded Schaffer’s function 6 in Dimension 50 (problem P39) (for all other considered ranking methods).We stress that these results were obtained using only the ranking-theory methods without an analysis of any statistical indicators of the assessment function values, as currently practiced (see, e.g., the related literature overview in the Introduction section).


## 5. Conclusions

In this study, we presented a new MCDM technique for solving decision-making problems for benchmarking. Our investigation was based on the concept of a benchmarking context, presented in detail, and the observation that a benchmarking problem is an MCDM problem. Correspondingly, to solve benchmarking problems successfully, an extensive array of MCDM methods can be used. We also presented a new approach to the MCDM problem solution based on the ranking-theory methods. The corresponding ranks are obtained by constructing a special score matrix. We emphasize that this method defines the appropriate ranks directly from the decision matrix and does not use preliminary assessments conducted by external experts or other methods. Therefore, the technique presented in this study is useful when the relative importance of various criteria has not been evaluated in advance. As a case study, the benchmarking problem of DE algorithms was considered based on the data presented by Sala et al. [12]. A detailed numerical investigation was conducted using various ranking methods. Moreover, these ranks were also correspondingly compared for solvers and problems. The results demonstrate that the method presented in this study is competitive and generates relevant solutions.Referring to the analysis presented in this study, we conclude the following:(i)
The results of applying MCDM methods to aid benchmarking problem solutions based on the proposed approach are encouraging.(ii)
The proposed approach provides a constructive view of the benchmarking problem solution, identifying the “best” and “worst” cases and ordering all intermediate cases.(iii)
The proposed approach is easily implementable because of its simplicity and flexibility. Moreover, the approach is sufficiently general and can be successfully used to investigate benchmarking problems in other application areas.However, this study has limitations because we provided a tool for benchmarking only in the case in which the benchmarking context is given (i.e., when the sets of solvers (problems), problems (solvers), and performance metrics are given). However, issues regarding selecting benchmarking context components remain unresolved. The literature does not contain clear and direct recommendations regarding the correct selection of solvers, problems, and performance metrics. Hence, further investigation in this direction will be helpful.



---

*Source: 5513860-2021-07-13.xml*