2.7 Data Envelopment Analysis

Operations research (OR) is a mish-mash of various mathematical methods used to solve complex industrial problems, especially optimization problems, which are being tackled in management and other non-industrial contexts.

Data Envelopment Analysis (DEA), based on linear programming, is used to measure the relative performance of units in an organization such as a government department, a school, a company, etc. Typically, a unit’s efficiency is defined as the quotient of its outputs (activities of the organization such as service levels or number of deliveries) by its inputs (the resources supporting the organization’s operations, such as wages or value of the in-store stock).

In an organization with only one type of input and one type of output, the comparison is simple. For instance, a fictional organization could have the simple input/out data in the table below:

Unit Input Output Efficiency
A 10 10 100%
B 10 20 200%
C 5 15 300%
D 15 10 67%

However, if there are more than one input or output, the comparisons are less obvious: in the table below, is unit \(A\) more efficient than unit \(B\)?

Unit Input 1 Input 2 Output 1 Output 2
A 10 5 10 20
B 10 15 20 5
C 5 15 15 15
D 15 5 10 20

Unit \(A\) has fewer total inputs than unit \(B\) (as well as fewer outputs of type 1), but it has a substantially more outputs of type 2. Without a system in place to measure relative efficiency, comparison between (potentially incommensurate) units is unlikely to be fruitful.

The relative efficiency of unit \(k\) is defined by \[\text{RE}_k = \frac{\sum_j w_{k,j}O_{k,j}}{\sum_i v_{k,i}I_{k,i}},\] where

  • \(\{O_{k,j}\mid j=1,\ldots,n\}\) represent the \(n\) outputs from unit \(k\),

  • \(\{I_{k,i}\mid i=1,\ldots,m\}\) represent the \(m\) inputs from unit \(k\),

  • \(\{w_{k,j}\mid j=1,\ldots,n\}\) and \(\{v_{k,i}\mid i=1,\ldots, m\}\) are the associated unit weights.

For a specific unit \(k\), the DEA model maximizes the weighted sum of outputs for a fixed weighted sum of inputs (usually set to 100), subject to the weighted sum of outputs of every unit being at most equal to the weighted sum of its inputs when using the DEA weights of unit \(k\).

In other words, the optimal set of weights for a given unit could not give another unit a relative efficiency greater than 1.

This is equivalent to solving the following linear program for each unit \(k_0\): \[\begin{array}{|rlll} \text{max } & \sum_{j=1}^n w_{k_0,j}O_{k_0,j} & &\ \\ \text{s.t. } & \sum_{i=1}^m v_{k_0,i}I_{k_0,i} = 100 &\ & \\ & \sum_{j=1}^n w_{k_0,j}O_{\ell,j}-\sum_{i=1}^m v_{k_0,i}I_{\ell,i}\leq 0,\quad 1\leq \ell\leq K\\ & (w_{k_0,j},v_{k_0,i})\geq \boldsymbol{\varepsilon},\quad 1\leq j\leq n,\ 1\leq i\leq m & \end{array}\] where \(\boldsymbol{\varepsilon}\geq 0\) is a parameter vector to be modified by the user.

If we define \(\mathbf{w}_{\ell}\), \(\mathbf{v}_{\ell}\), \(\mathbf{O}_{\ell}\) and \(\mathbf{I}_{\ell}\) as the vectors of output weights, input weights, outputs and inputs, respectively, for unit \(\ell\), while \(\mathbf{O}\) and \(\mathbf{I}\) represent the row matrix of outputs and the row matrix of inputs for all the units, then the linear problem can be re-written simply as \[\begin{array}{|rl} \text{max } & \mathbf{w}_{k_0}^{\!\top}\mathbf{O}_{k_0} \ \\ \text{s.t. } & \mathbf{v}_{k_0}^{\!\top}\mathbf{I}_{k_0} = 100 \\ & \mathbf{w}_{k_0}^{\!\top}\mathbf{O}-\mathbf{v}_{k_0}^{\!\top}\mathbf{I}\leq \mathbf{0} \\ & -\left(\mathbf{w}_{k_0},\mathbf{v}_{k_0}\right)\leq -\boldsymbol{\varepsilon} \end{array}\]

This problem can be solved by the method of Lagrange multipliers or by using dedicated numerical solvers. With the data from the example above,the DEA program for unit \(A\), for instance, becomes \[\begin{array}{|rrlrlrlrll} \text{max } & 10w_{A,1} &+&20w_{A,2} & \\ \text{s.t. } & & & & & 10v_{A,1}&+&5v_{A,2} &=& 100 \\ & 10w_{A,1}&+&20w_{A,2}&-&10v_{A,1}&-&5w_{A,2}&\leq &0 \\ & 20w_{A,1}&+&5w_{A,2}&-&10v_{A,1}&-&15w_{A,2}&\leq &0 \\ & 15w_{A,1}&+&15w_{A,2}&-&5v_{A,1}&-&15w_{A,2}&\leq &0 \\ & 10w_{A,1}&+&20w_{A,2}&-&15v_{A,1}&-&5w_{A,2}&\leq &0 \\ & w_{A,1}&,& w_{A,2}&,&v_{A,1}&,&v_{A,2}&\geq& \varepsilon \end{array}\]

2.7.1 Challenges and Pitfalls

By allowing non-universal (unit-specific) weights, DEA allows each unit to present itself in the best possible light, which could potentially lead most units to be deemed efficient. This issue is mitigated to some extent when the number of units \(K\) is greater than the product of the number of outputs by the number of inputs \(n\cdot m\).

When the number of units is small, a lack of differentiation among units is uninformative since all units could benefit from the best-case scenario described above. When there is differentiation, however, it can be quite telling: units with low DEA relative efficiency have achieved a low score even when given a chance to put their best foot forward.

Another concern is that a unit could artificially seem efficient by completely eliminating unfavourable outputs or inputs (i.e.if the associated input/output weights are \(0\)). Constraining the weights to take values in some fixed range can help avoid this issue.

In the example that was discussed above, when we set \(\varepsilon=0\), all units have a relative efficiency of 100. If we set \(\varepsilon = 2\), however, the relative efficiency for each unit is \[\mbox{RE}_A=100,\quad \mbox{RE}_B=67.7,\quad \mbox{RE}_C=100, \quad\mbox{and}\quad \mbox{RE}_D=90.\] Evidently, insisting that all the factors be considered may affect the results.

External factors can easily be added to the model as either inputs or outputs. Available resources are classified as inputs; activity levels or performance measures are classified as outputs.

When units can also be assessed according to some other measure (such as profitability, average rate of success for a task, or environmental cleanliness, say), it can be tempting to solely use the second metric to rank the units.

The combination of efficiency and profitability (or of any two measures, really) can however offer insights and suggestions:

Flagships

are units who score high on both measures and that can provide examples of good operating practices (as long as it is recognized that they are also likely beneficiaries of favourable conditions).

Sleepers

score low on efficiency but high on the other measure, which is probably more a consequence of favourable conditions than good management; as such, they become candidates for efficiency drives.

Dogs

score high on efficiency but low on the other measure, which indicates good management but unfavourable conditions. In extreme case, these units are candidates for closures, their staff members could be re-assigned to other units.

Question Marks

are units who score low on both measures; they are subject to unfavourable conditions, but this could also be a consequence of bad management. Attempts should be made to increase the efficiency of these units so that they become Sleepers or Flagships.

Finally, note that in any reasonable application, the linear program to be solved (or its dual) can be fairly complicated and sophisticated software can be required to obtain a solution. That is emblematic of industrial optimization problems.

2.7.2 Advantages and Disadvantages

The main benefits of DEAs are that:

  • there is no need to explicitly specify a mathematical form for the production function;

  • they have been proven to be useful in uncovering relationships that remain hidden from other methodologies;

  • they are capable of handling multiple inputs and outputs;

  • they can be used with any input-output measurements, and

  • the sources of inefficiency can be analysed and quantified for every evaluated unit.

On the other hand, there are also disadvantages to using DEAs:

  • the results are known to be sensitive to the selection of inputs and outputs;

  • it is impossible to test for the best specification, and

  • the number of efficient units on the frontier tends to increase with the number of inputs and output variables.

As is the case for all applications of quantitative methods to real-world problems, DEAs will ultimately prove useless unless users understand how they function and how to interpret their results.

2.7.3 SAS, Excel, and R DEA Solvers

For small problems, the numerical cost of solving the problem is not too onerous. Consequently, such problems can typically be solved without having to purchase a commercial solver.

As an illustration, consider the problem of finding the relative efficiency of unit \(D\) in the example arising from the data presented above (using a minimal weight threshold of \(\varepsilon=2\), say). Thus, we are looking for the solution to \[\begin{array}{|rrlrlrlrll} \text{max } & 10w_{D,1} &+&20w_{D,2} & \\ \text{s.t. } & & & & & 15v_{D,1}&+&5v_{D,2} &=& 100 \\ & 10w_{D,1}&+&20w_{D,2}&-&10v_{D,1}&-&5w_{D,2}&\leq &0 \\ & 20w_{D,1}&+&5w_{D,2}&-&10v_{D,1}&-&15w_{D,2}&\leq &0 \\ & 15w_{D,1}&+&15w_{D,2}&-&5v_{D,1}&-&15w_{D,2}&\leq &0 \\ & 10w_{D,1}&+&20w_{D,2}&-&15v_{D,1}&-&5w_{D,2}&\leq &0 \\ & w_{D,1}&,& w_{D,2}&,&v_{D,1}&,&v_{D,2}&\geq& 2 \end{array}\]

This is a small problem, and Excel’s numerical solver can be used to yield a relative efficiency of \(90\%\) (see Figure 2.2 for an illustration).

Excel's numerical solver for unit D.

Figure 2.2: Excel’s numerical solver for unit D.

There are a number of non-technical issues with the solver, including the fact that a different worksheet has to be created for every single unit. With larger datasets, this approach may not be practical.

SAS’s proc optmodel, available in version 9.2+ as part of the OR(R) suite, can also be used; but some additional work has to be done to automate the descriptions of the programs to be solved. R’s rDEA and deaR packages provide other options.

2.7.4 Case Study: Barcelona Schools

In this section, we present an illustration of a resource utlization model which uses a DEA-like approach to illustrate how these are used in practice.

  • Title: On centralized resource utilization and its re-allocation by using DEA [24]

  • Authors: Cecilio Mar-Molinero, Diego Prior, Maria-Manuela Segovia, Fabiola Portillo

  • Date: 2012

  • Methods: Data envelopment analysis, simulations

Abstract

The standard DEA model allows different Decision-Making Units (DMUs) to set their own priorities for the inputs and outputs that form part of the efficiency assessment. In the case of a centralized organization with many outlets, such as an education authority that is responsiblef or many schools, it may be more sensible to operate in the most efficient way, but under a common set of priorities for all DMUs. The centralized resource allocation model does just this; the optimal resource reallocation is found for Spanish public schools and it is shown that the most desirable operating unit is a by-product of the estimation.

Data

The data consists of 54 secondary public schools in Barcelona during the year 2008, each with three discretionary inputs (teaching hours per week, \(x_1\); specialized teaching hours per week, \(x_2\); capital investments in the last decade, \(x_3\)), one non-discretionary input (total number of students present at the beginning of the academic year, \(X\)) and two outputs (number of students passing their final assessment, \(y_1\), and number of students continuing their studies at the end of the academic year, \(y_2\)).

A subset of the data is shown below:

Sample from the Barcelona public school data set used with the radial and simplified models.

Figure 2.3: Sample from the Barcelona public school data set used with the radial and simplified models.

Challenges

A first challenge is that the machinery of DEA cannot directly be brought to bear on the problem since the models under consideration are at best DEA-like. Another challenge is that the number of unknowns to be estimated in the original model is quadratic in the number of units. Consequently, the original model must be simplified to avoid difficulties when the number of units is large. Fortunately, the proposed simplifications can be interpreted logically in the context of re-allocation of resources.

Finally, there are situations where a solution to the simplified problem can be obtained even when the constraints on the total number of units is relaxed, allowing for the possibility of reaching the similar output levels with fewer inputs, in effect advocating for the closure of some units.

While this is a technically-correct solution, it might could prove to be an unadvisable one for a variety of non-technical reasons: closing schools is not usually a politically and/or societally palatable strategy. This latter factor should also be incorporated in the decision-making process.

Project Summary and Results

In the standard DEA model, each unit sets its own priorities, and is evaluated using unit-specific weights. In a de-centralized environment, the standard approach is reasonable, but under a central authority where a common set of priorities needs to be met by all units (such as the branches of a bank, or recycling collection vehicles in a city), that approach needs to be modified.

In a school setting, school board administrators may wish to evaluate teachers in a similar manner independently of the school at which they work. Centralized assessment imposes a common set of weights. For weakly centralized management, it is a further assumption that any input excess of inefficient units can be re-allocated among the efficient units, but only as long as this does not contravene the built-in inflexibility of the system, which may make re-allocation rather difficult.

Strongly centralized management, on the other hand, allow for re-allocation of the majority of inputs and outputs among all the units (inefficient or efficient) with the aim of optimizing the performance of the entire system. The original radial model of Lozano and Villa [25] is not, strictly speaking, a data envelopment model: \[\begin{aligned} \text{min } & \theta \text{ (objective)}\ \\ \text{s.t. } & \sum_{r=1}^{54}\sum_{j=1}^{54} \lambda_{j,r}x_{i,j}-\theta \sum_{j=1}^{54}x_{i,j} \leq 0, \quad\text{for }i=1,2,3 & & \\ & \text{ (discretionary inputs)} \\ & \sum_{r=1}^{54}\sum_{j=1}^{54} \lambda_{j,r}X_{j}- \sum_{j=1}^{54}X_j \leq 0 , & & \\ &\text{ (non-discretionary input)} \\ & \sum_{r=1}^{54}y_{kr}-\sum_{r=1}^{54}\sum_{j=1}^{54} \lambda_{j,r}y_{k,j}\leq 0, \quad \text{for }k=1,2 & & \\ & \text{ (outputs)}\\ & \sum_{j=1}^{54}\lambda_{j,r}=54,\quad \text{for }r=1,\ldots,54 & &\\ & -\lambda_{j,r}\leq 0, \quad\text{ for }j,r=1,\ldots,54, \quad \theta \text{ free} & & \end{aligned}\]

Indeed, this model is not asking every unit to select the weights that make it look as good as possible when comparing itself to the remaining units under the same assessment; rather, it is asking for the system as a whole to find the weights that present it in the best possible light possible, then it assesses the performance of the units separately, using the optimal system weights.

This conceptual shift leads to proposed closures.The main drawback of the radial model is the large number of weights to estimate. A simplification is proposed: if some of the units can be cloned, or equivalently, if some of the units can be closed and their resources re-allocated to other units, then the radial model becomes substantially simpler, and the number of weights to estimate is linear in the number of units (as opposed to quadratic).

The new problem is DEA-like: \[\begin{aligned} \text{min } & \theta \text{ (objective)}\ \\ \text{s.t. } & \sum_{j=1}^{54} \lambda_{j}x_{i,j}-\theta \sum_{j=1}^{54}x_{i,j} \leq 0, \quad\text{for }i=1,2,3 & \\ & \text{ (discretionary inputs)} \\ & \sum_{j=1}^{54} \lambda_{j}X_{j}- \sum_{j=1}^{54}X_j \leq 0 & & \\ & \text{ (non-discretionary inputs)} \\ & \sum_{r=1}^{54}y_{k}-\sum_{j=1}^{54} \lambda_{j}y_{k,j}\leq 0, \quad \text{for }k=1,2 & & \\ & \text{(outputs)}\\ & \sum_{j=1}^{54}\lambda_{j}=54 & &\\ & -\lambda_{j}\leq 0, \quad\text{ for }j=1,\ldots,54, \quad \theta \text{ free} & & \end{aligned}\]

The numerical solution to the radial model shows a group efficiency of 66%, meaning that the outputs of the system could be produced while reducing the discretionary inputs by \(\theta=34\%\). The simplified model reaches the same group efficiency by cloning units 25 (24.26 times), 26 (20.02 times), 36 (4.71 times), 17 (2.69 times), and 44 (1.70 times).

The re-allocation of inputs and outputs among the 54 schools would produce the aforementioned reduction of the 34% in discretionary inputs.

A simulation experiment shows the effect of dropping the constraint on the number of units: the group efficiency obtained by solving the simplified system for various values of \(n\) from 32 to 81 is seen below:

Results of the re-allocation process in the Barcelona public school dataset.

Figure 2.4: Results of the re-allocation process in the Barcelona public school dataset.

Sure enough, the original solution is good, appearing near the minimum, which reaches \(\theta=0.64\) at \(n = 50.36\). This group efficiency corresponds to cloning units 25 (23.96 times), 26 (17.62 times), and 29 (7.87 times), Obviously, schools (and their resources) cannot be cloned, so what are we to make of this result?

It could be argued that unit 25 and 26, for instance, are ideal schools under the common priorities imposed by the system: should new schools have to be built, attempts could be made to emulate the stars. Of course, in practice, other factors could come into play.

References

[24]
C. Mar-Molinero, D. Prior, M.-M. Segovia, and F. Portillo, On centralized resource utilization and its reallocation by using DEA,” Ann. Oper. Res., vol. 221, no. 1, pp. 273–283, 2014.
[25]
S. Lozano and G. Villa, Centralized resource allocation using data envelopment analysis,” Journal of Productivity Analysis, vol. 22, no. 1, pp. 143–161, 2004.