Pls, anyone with contributions on how i can use DEA to solve Graph Algorithms problems such, Network flow, Project management, Scheduling, Routing.etc
Majorly I need information on how to identify the input and output variables in this kind of problems(where there is no complete knowledge of the I/O ).
I think I can identify my DMUs.
I shall be glad to receive contributions on the appropriate general DEA model approach for solving Combinatorial Optimization problems of these kind.
Thanks
DEA is generally applied to assess the relative performance a set of decision making units (DMUs) that consume inputs to produce outputs under a similar production technology. This may be valid whenever the systems under consideration fit within such a structure. In graph related problems such as scheduling, routing, etc., the objectives are completely different. Although there is a flow of material over the network, which may suggest that a node can be assimilated to a DMU, here, we are more concerned with finding an optimal route that satisfies constraints that may be as complex as the practical problem under study. In large scale problems, one may think of DEA for building clusters of nodes so that to reduce the problem size and, hence, related computational cost. I think that this aspect is worth to be investigated.
DEA is a very special kind of model, specifically designed for performance evaluation. Running the model involves the solution of some linear programs, and these LPs themselves have a very special structure.
So... I don't see any natural connection between DEA and network optimisation. Unless anyone can think of some problems that involve a network structure *and* performance measurement simultaneously, I guess.
By the way, you probably already know this, but, for many standard network optimization problems, efficient solution algorithms are already available. Examples include the shortest-path, minimum spanning tree, minimum spanning arborescence, maximum flow, minimum-cost flow, assignment, transportation and matching problems.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs