=Paper=
{{Paper
|id=Vol-1987/paper49
|storemode=property
|title=Constructions of Input and Output Isoquants for Nonconvex Multidimensional Models
|pdfUrl=https://ceur-ws.org/Vol-1987/paper49.pdf
|volume=Vol-1987
|authors=Vladimir E. Krivonozhko,Andrey V. Lychev,Eugene A. Kalashnikov
}}
==Constructions of Input and Output Isoquants for Nonconvex Multidimensional Models==
https://ceur-ws.org/Vol-1987/paper49.pdf
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