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 methods 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.

Consider a set of n observations of actual production units (X j , Y j ), j = 1, . . . , n, where the vector of outputs Y j = (y 1j , . . . , y rj ) > 0 is produced from the vector of inputs X j = (x 1j , . . . , x mj ) > 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.

The FDH input-oriented model for evaluating unit (X o , Y o ) under variable RTS assumption is written as follows

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

where e p and e s 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 d 1 and d 2 , g 1 and g 2 , we can obtain various sections going through unit (X o , Y o ) 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.

Now, consider an optimization algorithm for construction of the generalized input isoquant (4) for unit (X o , Y o ). This isoquant is determined by directions e p ∈ E m and e s ∈ E m , where e p and e s are unity vectors.

Algorithm 1.

Step 1. Find a leftmost point on the input isoquant going through point (X o , Y o ) and determined by directions e p ∈ E m and e s ∈ E m , where e p and e s are unity vectors.

Step 2. Find two adjacent angular points on the input isoquant. Solve the following two optimization problems. a) Problem A:

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 (X o , Y o ) with directions e p and e s , 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 (X o , Y o ). For this purpose solve the following optimization problem max η

Step 2. Find two adjacent points on the output isoquant. Solve the following two optimization problems. a) Problem A: max

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 (X o , Y o ) 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. 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 (X k , Y k ) be determined by directions e p ∈ E m and e s ∈ E m , where e p and e s are unity vectors with a one in positions p and s, respectively.

Algorithm 3.

Step 1. Determine set

Determine a vertical ray of isoquant from point (α p 1 , β s 1 )

x pj x pk (15)

Add a horizontal and vertical segments to the isoquant

Step 3. Add a horizontal ray to the isoquant

Step 4. Sec(X k , Y k , e p , e s ) = S. Construction of the isoquant is completed. Points (α p l , β s l ), 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 (X k , Y k ) and directions ēq ∈ E r and ēt ∈ E r , respectively.

Algorithm 4.

Step 1. Determine set

Determine the first segment of the output isoquant

Add a horizontal and vertical segments to the output isoquant

Step 3. Add a vertical segment to the isoquant

Step 4. Sec(X k , Y k , e q , e t ) = S. Construction of the output stepwise isoquant is completed.

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.