Finding Most Vital Links over Time in a Flow Network
This paper deals with finding most vital links of a network which carries flows over time (also called ”dynamic flows”). Given a network and a time horizon T, Single Most Vital Link Over Time (SMVLOT) problem looks for a link whose removal results in greatest decrease in the value of maximum flow over time (dynamic maximum flow) up to time horizon T between two terminal nodes. SMVLOT problem is formulated as a mixed binary linear programming problem. This formulation is extended to a general case called k-Most Vital Links Over Time (KMVLOT) problem, in which we look for finding those k links whose removal makes greatest decrease in the value of maximum flow over time. A Benders decomposition algorithm is proposed for solving SMVLOT and KMVLOT problems. For the case of SMVLOT problem, the proposed algorithm is improved to a fully combinatorial algorithm by adopting an iterative method for solving existing integer programming problem. However, our experimental results showed the superiority of proposed methods.
[1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows: theory, algorithms, and applications. PrenticeHall, Inc., Upper Saddle River, NJ, USA, 1993.
[2] D. S. Altner, zlem Ergun, and N. A. Uhan. The maximum flow network interdiction problem: Valid inequalities, integrality gaps, and approximability. Operations Research Letters, 38:33–38, 2010.
[3] E. Anderson, P. Nash, and A. Philpott. A class of continuous network flow problems. Mathematics of Operations Research, 7:501–514, 1982.
[4] E. J. Anderson and A. B. Philpott. Optimisation of flows in networks over time. In F. P. Kelly, editor, Probability, Statistics and Optimisation, chapter 27, pages 369–382. Wiley, New York, 1994.
[5] A. Bar-Noy, S. Khuller, and B. Schieber. The complexity of finding most vital arcs and nodes. Technical Report CS-TR-3539, University of Maryland, Institute of Advanced Computer Studies, College Park, MD, 1995.
[6] J. Benders. Partioning procedures for solving mixed integer variables programming problems. Numerische Mathamatik, 4:238252., 1962.
[7] R. E. Burkard, K. Dlaska, and B. Klinz. The quickest flow problem. ZOR Methods and Models of Operations Research, 37(1):3158, 1993.
[8] H. Corley and D. Sha. most vital links and nodes in weighted networks. Operations Research Letters, 1 (4):157–160, 1982.
[9] L. Fleischer and . Tardos. Efficient continuous-time dynamic network flow algorithms. Operations Research Letters, 23(3-5):71 – 80, 1998.
[10] L. Ford and D. Fulkerson. Constructing maximal dynamic flows from static flows. Operations Research, 6:419–433, 1958.
[11] B. Hoppe and . Tardos. The quickest transshipment problem. Mathematics of Operations Research, 25(1):3662, 2000.
[12] K.-C. Lin and M.-S. Chern. The fuzzy shortest path problem and its most vital arcs. Fuzzy Sets and Systems, 58:343–353, 1993.
[13] K. Malik, A. Mittal, and S. Gupta. The k most vital arcs in the shortest path problem. Operations Research Letters, 8:223–227, 1989.
[14] K. G. Murty. Linear Programming. John Wiley and Sons, New York, 1983.
[15] A. Orda and R. Rom. On continuous network flows.
[16] M. Skutella. An introduction to network flows over Operations Research Letters, 17:27–36, 1995. time. In W. Cook, L. Lovasz, and J. Vygen, editors, Research Trends in Combinatorial Optimization. Springer, Berlin, 2009.
[17] R. D. Wollmer. Some methods for determining the most vital link in a railway network. RAND Memorandum RM-3321-ISA, 1963.
[18] R. K. Wood. Deterministic network interdiction. Mathematical and Computer Modelling, 17:1–18, 1993