Evaluation of the applicability of the network flow approach to the emergency service restoration problem

The graph theory/network flow approach to the emergency-service restoration problem is discussed. The mixer integer programming formulation looks rigorous and concise. However, its usefulness appears to be very limited due to computational difficulties. By introducing artificial branches and a source and sink, the problem may be formulated as a maximal-flow problem in a restricted sense. In this case, zero-one decision variables representing switch status should be handled separately after the solution to the completely connected network is obtained. It is shown that the straight-forward application of the graph theory/network flow approach is not suitable for the problem. This simply points out difficulties associated with the problem and also suggests that heuristic algorithms need to be used to handle problems of this nature.<>