Obtaining all extreme rays of a special cone using spanning trees in a complete digraph: Application in DEA

Abstract

This paper presents a new method which can be used in two different situations: Firstly, for converting certain polyhedral cones of intersection form to cones of sum form, this method identifies all the extreme rays of a cone of intersection form by enumerating all spanning trees in a complete digraph without solving any mathematical programming problems. Secondly, in the existing data envelopment analysis models, the lower bound of cost efficiency measure can be calculated by using weights restrictions in the form of input cone assurance region. In such cases, all vertices are obtained by enumerating all potential bases. In fact, for determining the lower bound of cost efficiency measure, the vertices of a polyhedral set should be calculated. Because obtaining all vertices by enumerating all potential bases is not actually affordable, in this paper we obtain the vertices by enumerating all spanning trees in a complete digraph. This method has computational advantages over the previous ones. At the end of this paper, two numerical examples are provided to demonstrate the advantage of the proposed method.

Keywords:

• Data envelopment analysis
• cost efficiency
• imprecise data
• complete graph
• spanning tree

Acknowledgements

The author (Najmeh Malekmohammadi) would like to thank Islamic Azad University, South Tehran Branch, for financial support in the research project entitled Performance Evaluation and Resource Allocation in Data Envelopment Analysis with Stochastic Data. The authors would like to appreciate the useful comments of the Editors, J. Crook, T. Archibald and the two anonymous referees, who helped us in improving the quality of this paper

Notes

Please note this paper has been re-typeset by Taylor & Francis from the manuscript originally provided to the previous publisher.