Buradasınız

Anasayfa » Content

Finding Most Vital Links over Time in a Flow Network

Journal Name:

  • An International Journal of Optimization and Control: Theories & Applications

Publication Year:

  • 2012

Keywords (Original Language):

Author NameUniversity of Author

AMS Codes:

Bookmark/Search this post with
Abstract (Original Language): 
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.
FULL TEXT (PDF): 
PDF icon arastirmax-finding-most-vital-links-over-time-flow-network.pdf
  • 2
173
186
  • English

REFERENCES

References: 

[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.
Operations Research Letters, 17:27–36, 1995.
[16] M. Skutella. An introduction to network flows over
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.

Thank you for copying data from http://www.arastirmax.com