In data envelopment analysis, methods for constructing sections of the frontier have been recently proposed to visualize the production possibility set. The aim of this paper is to develop, prove and test the methods for the visualization of production possibility sets using distributed computations. In this article a general scheme of the algorithm for constructing sections (visualization) of production possibility set is proposed. An algorithm for constructing a generalized production function is described in detail. Also, the possibilities of implementing certain schemes in a distributed computing environment are considered.
Copyright ⃝c by the paper's authors. Copying permitted for private and academic purposes.
The founders of the DEA approach were famous scientists A. Charnes, W. Cooper, E. Rhodes, R. Banker and some others [Charnes et al., 1978, Banker et al., 1984]. At present the number of publications on this approach makes up several thousand units in the international scientific journals [Emrouznejad & Yang, 2017].
The ideas contained in the DEA approach have turned out to be much more seminal and far-reaching than the simple computation of efficiency scores of complex systems. The DEA approach has close links with the neoclassical theoretical economics, systems analysis, and multicriteria optimization. This approach allows one to analyze the behavior of complex systems in the multidimensional space, to find optimal paths of development in it, to model various scenarios.
However, the whole process of calculation in the DEA approach is hidden from the user. Every mathematical model is just an approximation of the real-life processes and phenomena. For this reason some inadequacies may arise in models. In the DEA scientific literature, some reports appeared that DEA results do not always coincide with experts’ opinion. In our previous papers an approach for visualization of multidimensional production possibility sets and investigation of the behavior of complex units is proposed. The visualization of production possibility sets allows us to correct the DEA models using the frontier improving methods, reliably calculate important indicators of complex units (scale elasticity, marginal rates, etc.). Moreover, the visualization can reveal previously unexplored relationships between the variables in the model.
Visualization methods have been currently applied to the models that have a convex production possibility set: BCC (Banker, Charnes, Cooper) model with variable returns to scale, IRS (increasing returns to scale) model, DRS (decreasing returns to scale) model, etc. For a wide class of production models with nonconvex production possibility set, such methods and visualization algorithms are not developed. This paper aims to develop, prove and test the methods for the visualization of production possibility sets using distributed computations. 2
Consider a set of n observations of actual production units (Xj ; Yj ), j = 1; : : : ; n, where the vector of outputs Yj = (y1j ; : : : ; yrj ) ≥ 0 is produced from the vector of inputs Xj = (x1j ; : : : ; xmj ) ≥ 0. The input-oriented model [Banker et al., 1984] is written as follows min n ∑ Xj j + S− = X0; j=1 n ∑ Yj j − S+ = Y0; j=1 n ∑ j = 1; j ≥ 0; j = 1; : : : ; n; j=1 sk− ≥ 0; k = 1; : : : ; m; si+ ≥ 0; i = 1; : : : ; r; (1) where S− = (s1−; ; : : : ; s−m) and S+ = (s1+; : : : ; sr+) are slack variables. In model (1) the optimal value ∗ describes the efficiency score of unit (Xo; Yo), where (Xo; Yo) is a unit from the set of production units (Xj ; Yj ), j = 1; : : : ; n.
Notice that we do not use an infinitesimal constant explicitly in the DEA models, since we suppose that each model is solved in two stages in order to separate efficient and weakly efficient units [Cooper et al., 2007].
De nition 1. [Cooper et al., 2007] Unit (Xo; Yo) ∈ T is called BCC-efficient with respect to the input-oriented BCC model if and only if any optimal solution of (1) satisfies: a) ∗ = 1, b) all slacks sk−, k = 1; : : : ; m, si+, i = 1; : : : ; r are zero.
If condition (a) in Definition 1 is satisfied, then unit (Xo; Yo) is called input weakly efficient with respect to the BCC model.
De nition 2. [Cooper et al., 2007] Unit (X′; Y ′) ∈ T is Pareto efficient if and only if there is no (X; Y ) ∈ T and (X; Y ) ̸= (X′; Y ′) such that X ≤ X′ and Y ≥ Y ′.
The production possibility set T for BCC model is formulated as follows
T BCC = {(X; Y ) ∑jn=1 Xj ; j ≤ X; ∑jn=1 Yj ; j ≥ Y; ∑jn=1 j = 1; j ≥ 0; j = 1; : : : ; n}: (2) It was proved in [Krivonozhko et al., 2009] that the BCC model generalize a wide class of DEA models. Therefore, in this paper, we dwell mainly on this model.
Define the intersection of the frontier with two-dimensional plane [Krivonozhko et al., 2004] Sec(Xo; Yo; d1; d2) = {(X; Y ) (X; Y ) ∈ Pl(Xo; Yo; d1; d2) ∩ WEffP T }; (3) where Pl(Xo; Yo; d1; d2) is two-dimensional plane going through point (Xo; Yo) and spanned by vectors d1, d2 ∈ Em+r, WEffP T is a set of weakly Pareto efficient points of set T . It is proved in [Krivonozhko et al., 2005; JORS] that WEff P T coincides with a set of boundary points of T .
Define three types of two-dimensional sections that we will use in this paper.
1. Input isoquant, section S1. In this case, we take the following direction vectors d1 = (ep; 0) ∈ Em+r, d2 = (es; 0) ∈ Em+r, where ep and es are m-identity vectors with a one in positions p and s, respectively.
2. Output isoquant, section S2. For this section the direction vectors are chosen as d1 = (0; ep) ∈ Em+r, d2 = (0; es) ∈ Em+r, ep and es are r-identity vectors with a one in positions p and s, respectively.
3. Section S3 is a generalized production function for unit (Xo; Yo). For this case we use the following directions: d1 = (Xo; 0) ∈ Em+r, d2 = (0; Yo) ∈ Em+r.
Next, we describe the algorithm for constructing a generalized production function.
Algorithm Step 1. Find a leftmost point on a curve.
Let d1 = (Xo; 0) ∈ Em+r, d2 = (0; Yo) ∈ Em+r, a) solve the following optimization problem where is a free variable.
Set Z1 = Zo + 1∗d1 + ∗d2, where 1∗ and ∗ are optimal variables in problem (4).
b) Find a leftmost vertex on a curve. Solve the following optimization problem Set Z11 = Z1 + 2∗d2, where 2∗ is the optimal value of the objective function in (5).
Step 2. Find a topmost point on a curve. Solve two following optimization problems.
a) Solve Set Z2 = Zo + ∗d1 + 2∗d2, where 2∗ and ∗ are optimal variables in (6).
b) Solve min 1 (Zo + 1d1 + d2) ∈ T; max 2 (Z1 + 2d2) ∈ T max 2 (Zo + d1 + 2d2) ∈ T min 1 (Z2 + 1d1) ∈ T max 1 (G + 1d1 + d2) ∈ T; (4) (5) (6) (7) (8) Set Z21 = Z2 + 1∗d1, where 1∗ is the optimal value of the objective function in (7).
Step 3. Set l = 1, k = 1, i1 = 1, i2 = 2. Create flow Fkl , containing points Zil1 = Z11, Zil2 = Z21 of production possibility set T .
Define set M = {Z11; Z21}.
Step 4. While exist unprocessed flows Fkl , perform the following computations.
For each flow solve optimization problem of the following type where is a free variable,
G = 1 (Zil1 + Zil2 );
2 vector d1 is perpendicular to the vector d2, it lies in the plane of the section, and is directed to the upper left corner of a two-dimensional section, vector d2 = Zl i2 − Zil1 .
If optimal objective value of problem (8) 1∗ > 0, then start new flows Fkl+11 and Fkl+21 to solve optimization sub-problems.
Flow Fkl+11 contains points where 1∗ and ∗ are optimal values of variables in problem (8).
l+1 contains points Flow Fk2 The described algorithm for constructing sections reduces the solution of the original problem to the solution of recursively generated sub-problems, similarly to the known “divide and conquer” scheme [Dasgupta, 2006]. Since the sub-problems available at each moment can be solved independently, it is possible to speed up the algorithm by parallel execution of these problems. In the case of a large amount of computations required, it is promising to use the resources of many computers with the help of distributed computing technologies.
This divide and conquer technique is the basis of many efficient algorithms in optimization theory. For example, Branch-and-Bound (B&B) algorithm use this scheme. The implementation of B&B method on desktop grid systems is considered in paper [Posypkin et al., 2017]. This distributed B&B implementation relies on BNB-Solver [Evtushenko et al., 2009]. A tool for simulating parallel B&B method and different load balancing strategies are considered in [Golubeva et al., 2016].
Consider the general scheme of algorithm implementation in the distributed computing environment. The implementation of the algorithm consists of two parts: the control part and the working part. The first part controls the calculation process, implementing the entire internal logic of the algorithm, except the solution of flow problems. The problems generated at the iterations of the algorithm are sent to solve the working part. After this the results are returned back to the algorithm and then combined to give a solution to the original problem. The working part implements the solution of flow problems. While the control part is a single process, the working part can consist of a many workflows running on various distributed computational resources.
An important part of the implementation of the control process is the strategy of distributing flow tasks to workers. This strategy largely determines the efficiency of the entire algorithm in a distributed environment. The strategy should minimize overhead, for example, not send workers small tasks, which can be solved locally more quickly. It is also necessary to ensure a balanced load of work processes, for example, based on an assessment of the complexity of tasks or the dynamic distribution of tasks.
To implement the algorithm for constructing sections in a distributed computing environment, it is planned to use the Everest platform [10]. Everest is a cloud-based software platform that supports the publication, execution, and composition of computing applications in a distributed environment. The advantage of using the Everest platform to implement the described algorithm is the availability of tools for creating distributed computing applications and integration with computing resources that do not require additional platform installation. In particular, the platform supports the implementation of multi-task applications that dynamically generate computational tasks that are processed on remote resources using the platform. 5
In this article one algorithm for constructing section, a generalized production function, is described in detail. The algorithms for constructing other sections differ mainly in the way the direction vectors d1 and d2 are selected at each iteration of the algorithm. Computational experiments using real-life datasets confirmed that the algorithm works reliably and construct sections correctly.
The general scheme of the algorithm for constructing sections (visualization) of a set T is described. Also, the possibilities of implementing certain schemes in a distributed computing environment are considered. Acknowledgements This work was supported by the Russian Science Foundation (project No. 17-11-01353).