Finding Most Vital Links over Time in a Flow Network
DOI:
https://doi.org/10.11121/ijocta.01.2012.0098Keywords:
Most vital link, Flows over time, Mixed integer programmingAbstract
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.Downloads
References
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows: theory, algorithms, and applications. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1993.
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. CrossRef
E. Anderson, P. Nash, and A. Philpott. A class of continuous network flow problems. Mathematics of Operations Research, 7:501–514, 1982. CrossRef
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.
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.
J. Benders. Partioning procedures for solving mixed integer variables programming problems. Numerische Mathamatik, 4:238252., 1962. CrossRef
R. E. Burkard, K. Dlaska, and B. Klinz. The quickest flow problem. ZOR Methods and Models of Operations Research, 37(1):3158, 1993.
H. Corley and D. Sha. most vital links and nodes in weighted networks. Operations Research Letters, 1 (4):157–160, 1982. CrossRef
L. Fleischer and . Tardos. Efficient continuous-time dynamic network flow algorithms. Operations Research Letters, 23(3-5):71 – 80, 1998. CrossRef
L. Ford and D. Fulkerson. Constructing maximal dynamic flows from static flows. Operations Research, 6:419–433, 1958. CrossRef
B. Hoppe and . Tardos. The quickest transshipment problem. Mathematics of Operations Research, 25(1):3662, 2000.
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. CrossRef
K. Malik, A. Mittal, and S. Gupta. The k most vital arcs in the shortest path problem. Operations Research Letters, 8:223–227, 1989. CrossRef
K. G. Murty. Linear Programming. John Wiley and Sons, New York, 1983.
A. Orda and R. Rom. On continuous network flows. Operations Research Letters, 17:27–36, 1995. CrossRef
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. CrossRef
R. D. Wollmer. Some methods for determining the most vital link in a railway network. RAND Memorandum RM-3321-ISA, 1963.
R. K.Wood. Deterministic network interdiction. Mathematical and Computer Modelling, 17:1–18, 1993. CrossRef
Downloads
Published
How to Cite
Issue
Section
License
Articles published in IJOCTA are made freely available online immediately upon publication, without subscription barriers to access. All articles published in this journal are licensed under the Creative Commons Attribution 4.0 International License (click here to read the full-text legal code). This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available.
Under the Creative Commons Attribution 4.0 International License, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles in IJOCTA, so long as the original authors and source are credited.
The readers are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material
- for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
under the following terms:
- Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
This work is licensed under a Creative Commons Attribution 4.0 International License.
