Constructions of Input and Output Isoquants for Nonconvex Multidimensional Models Vladimir E. Krivonozhko, Andrey V. Lychev, Eugene A. Kalashnikov National University of Science and Technology MISiS Leninsky prospekt 4 119049 Moscow, Russia krivonozhkove@mail.ru, lychev@misis.ru, e.a.kalashnikov@mail.ru Abstract In this paper, we develop methods for frontier visualization of non- convex Free Disposal Hull (FDH) models. Our approach is based on constructions of input and output isoquants for multidimensional non- convex frontier. Our theoretical results are confirmed by computational experiments using real-life data sets from different areas. 1 Introduction Free Disposal Hull (FDH) models were proposed by Deprins, Simar and Tulkens [Deprins et al., 1984]. In these models the production possibility set is a nonconvex one. For this reason, it is required to develop special methods in order to calculate different characteristics of production unit’s behavior. These methods are divided into two groups. In the first group, methods are based on mathematical programming (MP) approach. The second group of methods involved enumeration algorithms. Kerstens and Vanden Eeckaut [Kerstens & Vanden, 1999] proposed a method for the estimation returns to scale (RTS) of decision making units in FDH models. In their method, one has to solve mixed integer nonlinear programming problems and to compare related efficiency scores. In paper [Podinovski, 2004] a method was proposed where one has to solve mixed integer linear programming problems instead of nonlinear ones. However, the size of LP-models is increased significantly. In the paper [Soleimani-damaneh et al., 2006] enumeration algorithms were proposed for estimating the RTS in FDH models. In the paper [Leleu, 2006], it was proposed to use linear programming framework in estimating RTS in FDH models. However, Cesaroni, Kerstens and Van de Woestyne [Cesaroni et al., 2017] noted the absence of papers devoted to methods for frontier visualization in FDH models. In this paper, we develop methods for frontier reconstruction in FDH models. Our approach is based on meth- ods that were proposed for convex DEA models [Krivonozhko et al., 2004]. We propose methods for constructions of input and output isoquants for multidimensional frontier using both optimization and enumeration methods. Our theoretical results are confirmed by computational experiments using real-life data sets from different areas. 2 Background 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 traditional Free Copyright ⃝ c by the paper’s authors. Copying permitted for private and academic purposes. In: Yu. G. Evtushenko, M. Yu. Khachay, O. V. Khamisov, Yu. A. Kochetov, V.U. Malkova, M.A. Posypkin (eds.): Proceedings of the OPTIMA-2017 Conference, Petrovac, Montenegro, 02-Oct-2017, published at http://ceur-ws.org 336 Disposal Hull technology proposed by Deprins, Simar and Tulkens [Deprins et al., 1984] is formulated as follows: { ∑n ∑n ∑n } T F DH = (X, Y ) j=1 Xj , λj ≤ X, j=1 Yj , λj ≥ Y, j=1 λj = 1, λj ∈ {0, 1}, j = 1, . . . , n , (1) where λj , j = 1, . . . , n are integer variables, taking on values 0 or 1. The FDH input-oriented model for evaluating unit (Xo , Yo ) under variable RTS assumption is written as follows θoF DH = ∑min θ n Xj λj ≤ θXo , ∑j=1 n Yj λj ≥ Yo , (2) ∑j=1 n j=1 λj = 1, λj ∈ {0, 1}, j = 1, . . . , n, where λj , j = 1, . . . , n are integer variables, taking on values 0 or 1. Define the two-dimensional plane in space E m+r as Pl(Xo , Yo , d1 , d2 ) = (Xo , Yo ) + αd1 + βd2 , (3) where (Xo , Yo ) ∈ T , α and β are any real numbers, directions d1 , d2 ∈ E m+r , and d1 is not parallel to d2 . The plane (3) goes through point (Xo , Yo ) in E m+r and is spanned by vectors d1 and d2 . Next, define two intersections of the frontier with two-dimensional planes { } Sec1 (Xo , Yo , ep , es ) = (X, Y ) (X, Y ) ∈ Pl(Xo , Yo , d1 , d2 ) ∩ WEff P T, d1 = (ep , 0), d2 = (es , 0) , (4) { } Sec2 (Xo , Yo , g1 , g2 ) = (X, Y ) (X, Y ) ∈ Pl(Xo , Yo , g1 , g2 ) ∩ WEff P T, g1 = (0, ēq ), g2 = (0, ēt ) , (5) where ep and es are m-identity vectors with a one in positions p and s, respectively, ēq and ēt are r-identity vectors with a one in positions q and t, respectively. Here WEff P T is a set of weakly efficient points of set T F DH . Using the same approach as in [Krivonozhko et al., 2004], we can prove that set WEff P T coincides with set Bound T , where Bound T denotes the set of boundary points of T F DH . By taking different directions d1 and d2 , g1 and g2 , we can obtain various sections going through unit (Xo , Yo ) and cutting the frontier. Moreover, we can construct the curves generalizing the well-known functions in macro- and microeconomics. Section (4) is a generalized input isoquant, and section (5) is a generalized output isoquant. 3 Main Results Now, consider an optimization algorithm for construction of the generalized input isoquant (4) for unit (Xo , Yo ). This isoquant is determined by directions ep ∈ E m and es ∈ E m , where ep and es are unity vectors. Algorithm 1. Step 1. Find a leftmost point on the input isoquant going through point (Xo , Yo ) and determined by directions ep ∈ E m and es ∈ E m , where ep and es are unity vectors. min ∑n θ xpj λj ≤ θxpo , ∑j=1 n xsj λj ≤ τ xso , ∑j=1 n x λ ≤ xko , k = 1, . . . , m, k ̸= p, k ̸= s, ∑nj=1 kj j (6) Y j λj ≥ Yo , ∑j=1 n j=1 λj = 1, λj ∈ {0, 1}, j = 1, . . . , n, τ is a free variable. Set α1 = θ∗ , l = 1. Step 2. Find two adjacent angular points on the input isoquant. Solve the following two optimization problems. 337 a) Problem A: min ∑n η xpj λj ≤ αl xpo , ∑j=1 n xsj λj ≤ ηxso , ∑j=1 n x λ ≤ xko , k = 1, . . . , m, k ̸= p, k ̸= s, (7) ∑nj=1 kj j Yj λj ≥ Yo , ∑j=1 n j=1 j = 1, λ λj ∈ {0, 1}, j = 1, . . . , n. Set βl = η ∗ . b) Problem B: min ∑n θ xpj λj ≤ θxpo , ∑j=1 n xsj λj ≤ τ xso , ∑j=1 n x λ ≤ xko , k = 1, . . . , m, k ̸= p, k ̸= s, ∑nj=1 kj j Y j λj ≥ Yo , (8) ∑j=1 n j=1 j = 1, λ τ ≤ βl (1 − ε), λj ∈ {0, 1}, j = 1, . . . , n, τ is a free variable. Here ε is a small parameter. Set l = l + 1. If the solution of problem (8) is infeasible, then αl = M , where M is a large number, go to Step 3. Else αl = θ∗ , go to the beginning of Step 2. Step 3. Stop. Points (αl , βl ), l = 1, . . . , L, are angular points of the stepwise input isoquant of FDH model for unit (Xo , Yo ) with directions ep and es , where L is a number of angular points of input isoquant. Next, proceed to description of an algorithm for construction of stepwise output isoquant (5) determined by directions ēq ∈ E r and ēt ∈ E r , where ēq and ēt are unity vectors with a one in position q and t, respectively. Algorithm 2. Step 1. Find a leftmost point on the output isoquant going through point (Xo , Yo ). For this purpose solve the following optimization problem max ∑n η X λ ≤ Xo , ∑nj=1 j j y λ ≥ yio , i = 1, . . . , r, i ̸= q, i ̸= t, ∑nj=1 ij j y λ ≥ ηyto , ∑nj=1 tj j (9) y λ ≥ τ yqo , ∑nj=1 qj j j=1 λj = 1, λj ∈ {0, 1}, j = 1, . . . , n, τ is a free variable. Set α1 = 0, β1 = η ∗ , l = 1. Step 2. Find two adjacent points on the output isoquant. Solve the following two optimization problems. a) Problem A: max ∑n θ X λ ≤ Xo , ∑nj=1 j j y λ ≥ yio , i = 1, . . . , r, i ̸= q, i ̸= t, ∑nj=1 ij j y λj ≥ βl yto , (10) ∑nj=1 tj y λ ≥ θy , ∑nj=1 qj j qo j=1 λj = 1, λj ∈ {0, 1}, j = 1, . . . , n. Set l = l + 1, αl = θ∗ . 338 b) Problem B: max ∑n η X λ ≤ Xo , ∑nj=1 j j y λ ≥ yio , i = 1, . . . , r, i ̸= q, i ̸= t, ∑nj=1 ij j y λ ≥ ηyto , ∑nj=1 tj j y λj ≥ τ yqo , (11) ∑nj=1 qj λ j=1 j = 1, τ ≥ αl (1 + ε), λj ∈ {0, 1}, j = 1, . . . , n, τ is a free variable. Here ε is a small parameter. If the solution of Problem B (11) is infeasible, then βl = 0, go to Step 3. Else βl = η ∗ , go to the beginning of Step 2. Step 3. Stop. Points (αl , βl ), l = 1, . . . , L, are angular points of the output stepwise isoquant of FDH model for unit (Xo , Yo ) with directions ēq and ēt , where L is a number of angular points of output isoquant. Main steps of Algorithm 2 are explained on the Figure 1. Figure 1: Construction of stepwise output isoquant for the FDH model At Step 1 of the algorithm some leftmost point F on the isoquant is found, where F = (0, η ∗ ). At Step 2a an angular point A = (α1 , β1 ) is calculated using the solution of Problem A (10). Thus, an angular point A on the curve is determined. Then, algorithm moves slightly out the production possibility set and takes point A′ . After this the algorithm moves the current point parallel to horizontal line until this point reaches the feasible point A′′ . The algorithm stops if it discovers an infinite horizontal line or, in other words, the solution of Problem B at some iteration will be infeasible. Now, we dwell on algorithms for construction of stepwise input and output isoquant for the nonconvex FDH model using enumeration approach. Again, let input isoquant for unit (Xk , Yk ) be determined by directions ep ∈ E m and es ∈ E m , where ep and es are unity vectors with a one in positions p and s, respectively. Algorithm 3. Step 1. Determine set { } Dps (k) = j xij ≤ xik , i = 1, . . . , m, i ̸= p, i ̸= s, yij ≥ yik , i = 1, . . . , r, j = 1, . . . , n . (12) Let xpj xsj α1p = min , β1s = min . (13) j∈Dps (k) xpk j∈Dps (k) xsk xpj =αp 1 Determine a vertical ray of isoquant from point (α1p , β1s ) { } S = (α1p , β1s ) + γ(0, 1), γ ≥ 0 . (14) 339 Let l = 1. { xpj xsj } Step 2. While D(l+1) = j > αlp , < βls , j ∈ Dps (k) ̸= ∅ xpk xsk do p xpj α(l+1) = min (15) j∈D(l+1) xpk Add a horizontal and vertical segments to the isoquant [ ] p S = S ∪ (αlp , βls ), (α(l+1) , βls ) , (16) s xsj β(l+1) = min , (17) j∈D(l+1) xsk xpj =αp (l+1) [ p p ] S = S ∪ (α(l+1) , βls ), (α(l+1) s , β(l+1) ) , (18) l = l + 1. (19) Step 3. Add a horizontal ray to the isoquant { } S = S ∪ (αlp , βls ) + γ(1, 0), γ ≥ 0 . (20) Step 4. Sec(Xk , Yk , ep , es ) = S. Construction of the isoquant is completed. Points (αlp , βls ), l = 1, . . . , L are angular points of the input isoquant, where L is a number of these points computed by the algorithm. Next, we proceed to construction of output stepwise isoquant using enumeration methods. Let this output isoquant be determined by production unit (Xk , Yk ) and directions ēq ∈ E r and ēt ∈ E r , respectively. Algorithm 4. Step 1. Determine set { } Dqt (k) = j xij ≤ xik , i = 1, . . . , m, yij ≥ yik , i = 1, . . . , r, i ̸= q, i ̸= t, j = 1, . . . , n . (21) Let ytj yqj β1t = max , α1q = max . (22) j∈Dqt (k) ytk j∈Dqt (k) yqk ytj =β1t Determine the first segment of the output isoquant [ ] S = (0, β1t ), (α1q , β1t ) . (23) Let l = 1. { yqj ytj } Step 2. While D(l+1) = j > αlq , < βlt , j ∈ Dqt (k) ̸= ∅ yqk ytk do t ytj β(l+1) = max (24) j∈D(l+1) ytk Add a horizontal and vertical segments to the output isoquant [ ] S = S ∪ (αlq , βlt ), (αlq , β(l+1) t ) , (25) q yqj α(l+1) = max , (26) j∈D(l+1) yqk t ytj =β(l+1) [ ] S = S ∪ (αlq , β(l+1) t q ), (α(l+1) t , β(l+1) ) , (27) l = l + 1. (28) Step 3. Add a vertical segment to the isoquant [ ] S = S ∪ (αlq , βlt ), (αlq , 0) . (29) Step 4. Sec(Xk , Yk , eq , et ) = S. Construction of the output stepwise isoquant is completed. 340 4 Conclusions Computational experiments were accomplished to check our algorithms using real-life data sets taken from different areas: Russian banks, Swedish electricity utilities and Norwegian municipalities. Original data sets are described in detail in papers [Krivonozhko et al., 2012, Forsund et al., 2007, Erlandsen & Førsund, 2002]. Computational experiments were conducted on the basis of personal computer with Intel Core i3 CPU 3.33 GHz and lp solve solver, version 5.5.2.0. Computational results are presented in Table 1 and Table 2. Table 1: Computations of efficiency scores Number of Number of Optimization methods Enumeration Real-life data sets input and production methods output units Time, s Number of Time, s indicators iterations Russian banks, 2008 6 200 1.0 37244 0.5 Swedish electricity utilities,1987 8 163 0.9 36096 0.1 Norwegian municipalities, 1997 13 469 20.1 564591 0.3 Table 2: Constructions of input and output isoquants Number of Number of Optimization methods Enumeration methods Real-life data sets input and production all input isoquants all output isoquants output units Time, s Avg. time Time, s Avg. time indicators per iso- per iso- quant, ms quant, ms Russian banks, 2008 6 200 15.2 30 0.14 0.235 Swedish electricity utilities,1987 8 163 10.9 20 0.187 0.234 Norwegian municipalities, 1997 13 469 254.7 180 17.48 0.828 It is well known in scientific literature that enumeration methods have a great computational advantage over optimization methods [Kerstens & Vanden, 1999]. Table 2 confirms that computational time for constructions of isoquants is much less for enumeration method than for the method based on optimization algorithms. However, there are a lot of standard optimization programs in scientific literature. For this reason it may be easier to interface a new model with standard optimization solver than to develop new enumeration methods. Acknowledgements The study is supported by Russian Science Foundation (project No. 17-11-01353). References [Deprins et al., 1984] Deprins, D., Simar, L., & Tulkens, H. (1984). Measuring labor efficiency in post offices. In M. Marchand, P. Pestieau, H. Tulkens (Eds.). The performance of public enterprises: Concepts and measurements (pp. 243-268). Amsterdam: North Holland. [Kerstens & Vanden, 1999] Kerstens, K., & Vanden Eeckaut, P. (1999). Estimating returns to scale using non- parametric deterministic technologies: A new method based on goodness-of-fit. European Journal of Operational Research 113(1), 206-214. [Podinovski, 2004] Podinovski, V. V. (2004). On the linearisation of reference technologies for testing returns to scale in FDH models. European Journal of Operational Research 152(3), 800-802. [Soleimani-damaneh et al., 2006] Soleimani-damaneh, M., Jahanshahloo, G. R., Reshadi, M. (2006). On the estimation of returns-to-scale in FDH models. European Journal of Operational Research 174(2), 1055- 1059. 341 [Leleu, 2006] Leleu, H. (2006). A linear programming framework for free disposal hull technologies and cost functions: Primal and dual models. European Journal of Operational Research 168(2), 340-344. [Cesaroni et al., 2017] Cesaroni, G., Kerstens, K., Van de Woestyne, I. (2017). Global and local scale charac- teristics in convex and nonconvex nonparametric technologies: A first empirical exploration. European Journal of Operational Research 259(2), 576-586. [Krivonozhko et al., 2004] Krivonozhko, V. E., Utkin, O. B., Volodin, A. V., Sablin, I. A., & Patrin, M. (2004). Constructions of economic functions and calculations of marginal rates in DEA using parametric optimization methods. Journal of the Operational Research Society, 55(10), 1049-1058. doi:10.1057/palgrave.jors.2601759 [Krivonozhko et al., 2012] Krivonozhko, V. E., Førsund, F. R., & Lychev, A. V. (2012). A note on imposing strong complementary slackness conditions in DEA. European Journal of Operational Research 220(3), 716-721. [Forsund et al., 2007] Førsund, F. R., Hjalmarsson, L., Krivonozhko, V. E., & Utkin, O. B. (2007). Calculation of scale elasticities in DEA models: direct and indirect approaches. Journal of Productivity Analysis 28, 45-56. [Erlandsen & Førsund, 2002] Erlandsen, E., & Førsund, F. R. (2002). Efficiency in the provision of municipal nursing-and home care services: the Norwegian experience. In: K. J. Fox (Eds.). Efficiency in the public sector (pp. 273-300). Boston/Dordrecht/London: Kluwer. 342