In this paper, we develop methods for frontier visualization of nonconvex Free Disposal Hull (FDH) models. Our approach is based on constructions of input and output isoquants for multidimensional nonconvex frontier. Our theoretical results are confirmed by computational experiments using real-life data sets from different areas.
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 Disposal Hull technology proposed by Deprins, Simar and Tulkens [Deprins et al., 1984] is formulated as follows: where j, j = 1; : : : ; n are integer variables, taking on values 0 or 1.
Define the two-dimensional plane in space Em+r as
Pl(Xo; Yo; d1; d2) = (Xo; Yo) + d1 + d2; where (Xo; Yo) ∈ T , and are any real numbers, directions d1; d2 ∈ Em+r, and d1 is not parallel to d2. The plane (3) goes through point (Xo; Yo) in Em+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) ∩ WEffP T; d1 = (ep; 0); d2 = (es; 0)}; Sec2(Xo; Yo; g1; g2) = {(X; Y ) (X; Y ) ∈ Pl(Xo; Yo; g1; g2) ∩ WEffP T; g1 = (0; e¯q); g2 = (0; e¯t)}; where ep and es are m-identity vectors with a one in positions p and s, respectively, e¯q and e¯t are r-identity vectors with a one in positions q and t, respectively. Here WEffP 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 macroand microeconomics. Section (4) is a generalized input isoquant, and section (5) is a generalized output isoquant. 3
Now, consider an optimization algorithm for construction of the generalized input isoquant (4) for unit (Xo; Yo). This isoquant is determined by directions ep ∈ Em and es ∈ Em, 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 ∈ Em and es ∈ Em, where ep and es are unity vectors.
∑jn=1 Yj j ≥ Yo; j=1 j = 1; j ∈ {0; 1}; j = 1; : : : ; n; is a free variable. min ∑n ∑jn=1 xpj j ≤ xpo;
xso; ∑jn=1 xsj j ≤ ∑jn=1 xkj j ≤ xko; k = 1; : : : ; m; k ̸= p; k ̸= s; (2) (3) (4) (5) (6) Set 1 = ∗, l = 1.
Step 2. Find two adjacent angular points on the input isoquant. Solve the following two optimization problems. max ∑n ∑jn=1 Xj j ≤ Xo; ∑jn=1 yij j ≥ yio; i = 1; : : : ; r; i ̸= q; i ̸= t; yto; yqo; ∑jn=1 ytj j ≥ ∑jn=1 yqj j ≥ j=1 j = 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 e¯q ∈ Er and e¯t ∈ Er, where e¯q and e¯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
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: Set l = l + 1, l = ∗.
max ∑n ∑jn=1 Xj j ≤ Xo; ∑jn=1 yij j ≥ yio; i = 1; : : : ; r; i ̸= q; i ̸= t; ∑jn=1 ytj j ≥ lyto; ∑jn=1 yqj j ≥ yqo; j=1 j = 1; j ∈ {0; 1}; j = 1; : : : ; n: (7) (8) (9) (10) Determine a vertical ray of isoquant from point ( 1p; 1s)
S = {( 1p; 1s) + (0; 1);
≥ 0}: (11) (12) (13) (14) Add a horizontal and vertical segments to the output isoquant Step 3. Add a vertical segment to the isoquant
S = S ∪ [( lq; lt); ( lq; (tl+1))]; q (l+1) =
max j∈D(l+1) ytj= (tl+1) yqj ; yqk S = S ∪ [( lq; (tl+1)); ( (ql+1); (tl+1))];
l = l + 1:
S = S ∪ [( lq; lt); ( lq; 0)]: Step 4. Sec(Xk; Yk; eq; et) = S. Construction of the output stepwise isoquant is completed. 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 e¯q ∈ Er and e¯t ∈ Er, 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 : } 1t =
max ytj ; j∈Dqt(k) ytk 1q =
max j∈Dqt(k) yqk ytj= 1t yqj : Let do Determine the first segment of the output isoquant Let l = 1.
Step 2. While D(l+1) = {j yqj > yqk q; ytj < lt; j ∈ Dqt(k)} ̸= ∅ l ytk
S = [(0; 1t ); ( 1q; 1t )]: (tl+1) = j∈mDa(lx+1) ytk ytj (15) (16) (17) (18) (19) (20) (21) (22) (23) (24) (25) (26) (27) (28) (29)
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.
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).