Decision Support
Uncertain Data Envelopment Analysis

https://doi.org/10.1016/j.ejor.2018.01.005Get rights and content

Highlights

  • Efficiency scores in Data Envelopment Analysis increase with increasing uncertainty.

  • Uncertain Data Envelopment Analysis leverages uncertainty for inefficient DMUs.

  • For ellipsoidal uncertainty sets we propose a first order algorithm.

  • A case study in radiotherapy is provided.

Abstract

Data Envelopment Analysis (DEA) is a nonparametric, data driven method to conduct relative performance measurements among a set of decision making units (DMUs). Efficiency scores are computed based on assessing input and output data for each DMU by means of linear programming. Traditionally, these data are assumed to be known precisely. We instead consider the situation in which data is uncertain, and in this case, we demonstrate that efficiency scores increase monotonically with uncertainty. This enables inefficient DMUs to leverage uncertainty to counter their assessment of being inefficient.

Using the framework of robust optimization, we propose an uncertain DEA (uDEA) model for which an optimal solution determines (1) the maximum possible efficiency score of a DMU over all permissible uncertainties, and (2) the minimal amount of uncertainty that is required to achieve this efficiency score. We show that the uDEA model is a proper generalization of traditional DEA and provide a first-order algorithm to solve the uDEA model with ellipsoidal uncertainty sets. Finally, we present a case study applying uDEA to the problem of deciding efficiency of radiotherapy treatments.

Section snippets

Introduction and Motivation

Data envelopment analysis (DEA) is a well established optimization framework to conduct relative performance measurements among a group of decision making units (DMUs). There are numerous reviews of DEA, see, e.g., Cooper, Seiford, and Tone (2007); Emrouznejad, Parker, and Tavares (2008); Liu, Lu, Lu, and Lin (2013); Zhu (2014), and Hwang, Lee, and Zhu (2016); and the concept has found a wide audience in both research and application. The principal idea is to solve an optimization problem for

General Data Envelopment Analysis

We assume the (standard) input oriented model with variable returns-to-scale from among the many DEA formulations, where the efficiency score Eı^ of DMU ı^ is defined by solving the linear program, Eı^=min{θı^:Yλyı^0,Xλθı^xı^0,eTλ=1,λ0},where e is the vector of ones. In this model, there are M outputs, indexed by m; N inputs, indexed by n; and D DMUs, indexed by i. The matrices Y and X are the nonnegative output and input matrices so that YmiisthemthoutputvalueforDMUi,andXniisthenthinput

Uncertain Data Envelopment Analysis

The reliability of a DMU’s efficiency score is jeopardized if the data is erroneous, which points to a desire to accommodate suspect data within a DEA application. Uncertain data fits seamlessly into the paradigm of robust linear optimization, and our overarching model adapts this robust perspective. Each constraint A¯kı^η0 is replaced with a set of constraints Akı^η0,Akı^Uk,which reduces to the original constraint if the uncertainty set is restricted to the singleton, Uk={A¯kı^}.

Our goal

Configurations of uncertainty

Both the analytical outcomes and the computational tractability of a uDEA problem rely on the type of uncertainty that is being considered and on how the amount of uncertainty is evaluated. Hence an analysis depends on the pair (Ω, m), which defines a configuration.

Definition 6

A configuration of uncertainty, or more simply a configuration, is the pair (Ω, m), where Ω is a universe of possible collections of uncertainty satisfying UoU for all UΩ, and m is an amount of uncertainty.

A configuration defines

Examples

Consider the three DMUs pictured in Fig. 1 and whose nominal data are listed in Table 1. DMU C is inefficient, and model (1) would scale C’s input of 2 by the efficiency score of 1/2 to identify A as C’s efficient target. The inefficiency of DMU C means that it has an interest in knowing if it is capable under a configuration of uncertainty. We divide the discussion into three examples with different configurations to help explore possible outcomes. This collection

  • demonstrates a capable,

Traditional DEA as a special case of uncertain DEA

A uDEA problem obviously reduces to its certain DEA progenitor if Ω={Uo}, in which case the optimal solution satisfies U*=Uo,γ*=Eı^(U*)=Eı^,andm(U*)=0.With Ω={Uo} the outer supremum over γ and the inner minimization over U are meaningless in the uncertain model (6), and the overhead of the uncertain paradigm is unwarranted with regard to solving the DEA problem. However, the traditional DEA model in (1) is essentially a parametric query that asks, how much do the inputs of the ı^th DMU need to

Solving uncertain DEA problems

Solving a uDEA problem is generally more difficult than is calculating the efficiency score of a DMU. Indeed, even if the configuration is designed to reasonably accommodate efficient calculations, computing γ* necessitates the layering of three optimization problems, which complicates algorithm design. We restrict ourselves here to the case in which the robust DEA problem defining Eı^(U) can be efficiently solved as a second-order cone problem, i.e. we assume in our algorithmic development

A case study in radiotherapy

External radiation therapy is one of the major cancer treatments along with surgery and chemotherapy, and about two thirds of all cancer patients undergo a course of radiotherapy. Radiotherapy exploits a therapeutic advantage in which cancerous cells are unable to recover as well as healthy cells from radiation damage. Moreover, radiotherapy has the advantage of delivering near conformal dose distributions to tumors with complex geometries. While radiotherapy is generally regarded as a

Conclusion

We investigated how DEA is affected by uncertain data. We first presented a robust DEA model that defines a robust efficiency score for known uncertainty sets. We then formally showed that an increase in the uncertainty harbored by a collection of uncertainty increases the efficiency score of a DMU. This led to the question of how much uncertainty is needed to classify a DMU as efficient. We introduced the definition of an amount of uncertainty, which allowed us to formulate an optimization

Acknowledgment

The authors thank Emma Stubington for her thoughtful conversations on several of the topics herein. They also thank three anonymous referees for their thorough and suggestive reviews. O. N. acknowledges the support of the NSF grant CMMI-1463489.

References (30)

  • D. Bertsimas et al.

    Theory and applications of robust optimization

    SIAM Review

    (2011)
  • D. Bertsimas et al.

    Nonconvex robust optimization for problems with constraints

    INFORMS Journal on Computing

    (2010)
  • D. Bertsimas et al.

    A robust optimization approach to inventory theory

    Operations Research

    (2006)
  • T. Bortfeld

    Review IMRT: A review and preview

    Physics in Medicine and Biology

    (2006)
  • R. Cambria et al.

    Planning study to compare dynamic and rapid arc techniques for postprostatectomy radiotherapy of prostate cancer

    Strahlentherapie und Onkologie

    (2014)
  • Cited by (45)

    • A box-uncertainty in DEA: A robust performance measurement framework

      2022, Expert Systems with Applications
      Citation Excerpt :

      Their method can be applied to evaluate the absolute efficiency score of units for different values of robustness levels in order to rank them. Ehrgott et al. (2018) used the framework of RO to propose a DEA model in case of data uncertainty. They provided a first-order algorithm to solve their model and showed that the optimal solution of it determined the maximum possible efficiency score of a unit.

    • Robustness of Farrell cost efficiency measurement under data perturbations: Evidence from a US manufacturing application

      2021, European Journal of Operational Research
      Citation Excerpt :

      It was accordingly discussed that the decision maker can catch the maximum possible efficiency of a DMU over all permissible uncertainties, and the minimal amount of uncertainty is required to achieve this efficiency. In this respect, Theorem 2 is in line with Definition 2 of Ehrgott et al. (2018, p. 233) showing that the maximal robust TE measure remains 1 under the polyhedral uncertainty set, and conforming to Proposition 1 of Ehrgott et al. (2018, p. 233), Theorem 3 demonstrates that the robust TE measure is non-decreasing when uncertainties increase. Despite the theoretical aspect, the applicability of these essential properties will be illustrated in an empirical application in Section 6.

    View all citing articles on Scopus
    View full text