Efficient Algorithms for Data Envelopment Analysis

Data Envelopment Analysis (DEA) is a Management Science technique for performance analysis of comparable decision making units (DMU), such as branches of a bank, sports teams, hospitals, or universities to measure their efficiency in converting inputs to outputs.

It provides a measure for peer evaluation that allows each DMU to choose its own input and output weights so as to appear most efficient.

DEA analysis is normally done by solving a single linear programme for each DMU. Because linear programming is polynomial time solvable, this is in theory an efficient procedure. However, as the number of DMUs increases, so does the number of LPs to be solved, and computation times can be quite large.

In recent work we have exploited relationships between DEA and multi-objective linear programming to devise an algorithm that avoids solving LPs in DEA. From an abstract point of view DEA is also related other mathematical problems such as convex hull calculation. This project is about exploring and exploiting such relationships and finding algorithms that could be applied to DEA to speed up the computation of efficiency scores.

For further information contact Matthias Ehrgott.

Return to the Optimisation Research Group page.