×

The continuous maximum capacity path interdiction problem. (English) Zbl 1541.90105

Summary: This paper studies the continuous maximum capacity path interdiction problem, where two players, user and interdictor, compete in a capacitated network. The user wants to send the maximum possible amount of flow through a path, whose capacity is given by the minimum capacity among its arcs. The budget-constrained interdictor decreases arc capacities by any continuous amount to reduce the quality of the user’s chosen path. We present an efficient algorithm based on a discrete version of the Newton’s method, which helps us solve the problem in polynomial time. We also prove that the problem can be transformed into a zero-sum game, which has always a pure Nash equilibrium point. We demonstrate the performance of our algorithm over a set of randomly generated networks.

MSC:

90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks
91A65 Hierarchical games (including Stackelberg games)
Full Text: DOI

References:

[1] Acevedo, M. A.; Sefair, J. A.; Smith, J. C.; Reichert, B.; Fletcher Jr, R. J., Conservation under uncertainty: Optimal network protection strategies for worst-case disturbance events, Journal of Applied Ecology, 52, 6, 1588-1597 (2015)
[2] Ahuja, R.; Magnanti, T.; Orlin, J., Network flows: Theory, algorithms, and applications (1993), Prentice-Hall, Englewood Cliffs: Prentice-Hall, Englewood Cliffs NJ · Zbl 1201.90001
[3] Aiello, W.; Kushilevitz, E.; Ostrovsky, R.; Rosén, A., Adaptive packet routing for bursty adversarial traffic, Journal of Computer and System Sciences, 60, 3, 482-509 (2000) · Zbl 0961.68012
[4] Akgun, I.; Tansel, B. C.; Wood, R. K., The multi-terminal maximum-flow network-interdiction problem, European Journal of Operational Research, 211, 2, 241-251 (2011) · Zbl 1250.90021
[5] Allende, G. B.; Still, G., Solving bilevel programs with the KKT-approach, Mathematical Programming, 138, 1, 309-332 (2013) · Zbl 1280.90113
[6] Altner, D. S.; Ergun, O.; Uhan, N. A., The maximum flow network interdiction problem: Valid inequalities, integrality gaps, and approximability, Operations Research Letters, 38, 1, 33-38 (2010) · Zbl 1182.90014
[7] Alves Pessoa, A.; Di Puglia Pugliese, L.; Guerriero, F.; Poss, M., Robust constrained shortest path problems under budgeted uncertainty, Networks, 66, 2, 98-111 (2015) · Zbl 1387.90255
[8] Assimakopoulos, N., A network interdiction model for hospital infection control, Computers in Biology and Medicine, 17, 6, 413-422 (1987)
[9] Baier, G.; Köhler, E.; Skutella, M., The k-splittable flow problem, Algorithmica, 42, 3-4, 231-248 (2005) · Zbl 1086.90007
[10] Balas, E., An additive algorithm for solving linear programs with zero-one variables, Operations Research, 13, 4, 517-546 (1965) · Zbl 0133.42701
[11] Ball, M. O.; Golden, B. L.; Vohra, R. V., Finding the most vital arcs in a network, Operations Research Letters, 8, 2, 73-76 (1989) · Zbl 0679.90086
[12] Barabási, A. L.; Albert, R., Emergence of scaling in random networks, Science, 286, 5439, 509-512 (1999) · Zbl 1226.05223
[13] Batagelj, V.; Brandes, U., Efficient generation of large random networks, Physical Review E, 71, 3, 036113 (2005)
[14] Bayrak, H.; Bailey, M. D., Shortest path network interdiction with asymmetric information, Networks, 52, 3, 133-140 (2008) · Zbl 1171.90345
[15] Bazaraa, M. S.; Jarvis, J. J.; Sherali, H. D., Linear programming and network flows (2011), John Wiley & Sons
[16] Berman, O.; Handler, G. Y., Optimal minimax path of a single service unit on a network to nonservice destinations, Transportation Science, 21, 2, 115-122 (1987) · Zbl 0631.90023
[17] Bertsimas, D.; Sim, M., Robust discrete optimization and network flows, Mathematical Programming, 98, 1, 49-71 (2003) · Zbl 1082.90067
[18] Bertsimas, D.; Sim, M., The price of robustness, Operations Research, 52, 1, 35-53 (2004) · Zbl 1165.90565
[19] Bhavathankar, P.; Chatterjee, S.; Misra, S., Link-quality aware path selection in the presence of proactive jamming in fallible wireless sensor networks, IEEE Transactions on Communications, 66, 4, 1689-1704 (2017)
[20] Borrero, J. S.; Prokopyev, O. A.; Sauré, D., Sequential shortest path interdiction with incomplete information, Decision Analysis, 13, 1, 68-98 (2015) · Zbl 1398.91165
[21] Church, R. L.; Scaparra, M. P., Protecting critical assets: The r-interdiction median problem with fortification, Geographical Analysis, 39, 2, 129-146 (2007)
[22] Clímaco, J. C.N.; Pascoal, M. M.B.; Craveirinha, J. M.F.; Captivo, M. E.V., Internet packet routing: Application of a k-quickest path algorithm, European Journal of Operational Research, 181, 3, 1045-1054 (2007) · Zbl 1123.90009
[23] Forthcoming
[24] Dimitrov, N. B.; Gonzalez, M. A.; Michalopoulos, D. P.; Morton, D. P.; Nehme, M. V.; Popova, E.; Thoreson, G. G., Interdiction modeling for smuggled nuclear material, In Proceedings of the 49th annual meeting of the Institute of Nuclear Materials Management (2008)
[25] Edmonds, J.; Karp, R. M., Theoretical improvements in algorithmic efficiency for network flow problems, Journal of the ACMJ, 19, 2, 248-264 (1972) · Zbl 0318.90024
[26] Erdõs, P.; Rényi, A., On the evolution of random graphs, Selected Papers of Alfréd Rényi, 2, 482-525 (1976)
[27] Fischetti, M.; Ljubić, I.; Monaci, M.; Sinnl, M., A new general-purpose algorithm for mixed-integer bilevel linear programs, Operations Research, 65, 6, 1615-1637 (2017) · Zbl 1386.90085
[28] Fischetti, M.; Ljubić, I.; Monaci, M.; Sinnl, M., On the use of intersection cuts for bilevel optimization, Mathematical Programming, 172, 1-2, 77-103 (2018) · Zbl 1406.90082
[29] Frederickson, G. N.; Solis-Oba, R., Increasing the weight of minimum spanning trees, Journal of Algorithms, 33, 2, 244-266 (1999) · Zbl 0956.68113
[30] Fulkerson, D. R.; Harding, G. C., Maximizing the minimum source-sink path subject to a budget constraint, Mathematical Programming, 13, 1, 116-118 (1977) · Zbl 0366.90115
[31] Gabow, H. N., Scaling algorithms for network problems, In Proceedings of the IEEE 24th Annual Symposium on Foundations of Computer Science (SFCS), 248-258 (1983)
[32] Ghaffarinasab, N.; Motallebzadeh, A., Hub interdiction problem variants: Models and metaheuristic solution algorithms, European Journal of Operational Research, 267, 2, 496-512 (2018) · Zbl 1403.90475
[33] Ghare, P. M.; Montgomery, D. C.; Turner, W. C., Optimal interdiction policy for a flow network, Naval Research Logistics (NRL), 18, 1, 37-45 (1971) · Zbl 0216.54203
[34] Golden, B., A problem in network interdiction, Naval Research Logistics (NRL), 25, 4, 711-713 (1978) · Zbl 0394.90038
[35] Hu, T. C., The maximum capacity route problem, Operations Research, 9, 6, 898-900 (1961)
[36] Ichimori, T.; Ishii, H.; Nishida, T., Weighted minimax real-valued flows, Journal of the Operations Research Society of Japan, 24, 1, 52-60 (1981) · Zbl 0454.90081
[37] Israeli, E.; Wood, R. K., Shortest-path network interdiction, Networks, 40, 2, 97-111 (2002) · Zbl 1027.90106
[38] Kar, K.; Kodialam, M.; Lakshman, T. V., Minimum interference routing of bandwidth guaranteed tunnels with MPLS traffic engineering applications, IEEE Journal on Selected Areas in Communications, 18, 12, 2566-2579 (2000)
[39] Laroche, P.; Marchetti, F.; Martin, S.; Roka, Z., Bipartite complete matching vertex interdiction problem: Application to robust nurse assignment, In 2014 international conference on control, decision and information technologies (coDIT), 182-187 (2014), IEEE
[40] Liberatore, F.; Scaparra, M. P.; Daskin, M. S., Analysis of facility protection strategies against an uncertain number of attacks: The stochastic r-interdiction median problem with fortification, Computers & Operations Research, 38, 1, 357-366 (2011) · Zbl 1231.90268
[41] Liberatore, F.; Scaparra, M. P.; Daskin, M. S., Hedging against disruptions with ripple effects in location analysis, Omega, 40, 1, 21-30 (2012)
[42] Mageswari, R. U.; Baulkani, S., Routing technique for data transmission under jammer in multi-hop wireless network, Journal of Ambient Intelligence and Humanized Computing, 12, 3705-3713 (2020)
[43] Magnanti, T. L.; Wolsey, L. A., Optimal trees, Handbooks in Operations Research and Management Science, 7, 503-615 (1995) · Zbl 0839.90135
[44] Malaviya, A.; Rainwater, C.; Sharkey, T., Multi-period network interdiction problems with applications to city-level drug enforcement, IIE Transactions, 44, 5, 368-380 (2012)
[45] Martins, E. Q.V.; Santos, J. L.E., An algorithm for the quickest path problem, Operations Research Letters, 20, 4, 195-198 (1997) · Zbl 0881.90124
[46] Matuschke, J.; McCormick, S. T.; Oriolo, G.; Peis, B.; Skutella, M., Protection of flows under targeted attacks, Operations Research Letters, 45, 1, 53-59 (2017) · Zbl 1409.90042
[47] Mazalov, V., Mathematical game theory and applications (2014), John Wiley & Sons · Zbl 1309.91003
[48] McMasters, A. W.; Mustin, T. M., Optimal interdiction of a supply network, Naval Research Logistics (NRL), 17, 3, 261-268 (1970) · Zbl 0222.90017
[49] Medhi, D.; Ramasamy, K., Network routing: Algorithms, protocols, and architectures, second edition (2017), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers Cambrigde, MA
[50] 1950018.1-1950018.21 · Zbl 1423.90034
[51] Morton, D. P.; Pan, F.; Saeger, K., Models for nuclear smuggling interdiction, IIE Transactions, 39, 3-14 (2007)
[52] Othman, M. F.; Shazali, K., Wireless sensor network applications: A study in environment monitoring system, Procedia Engineering, 41, 1204-1210 (2012)
[53] Pan, F., Stochastic network interdiction: Models and methods (2005), PhD dissertation
[54] Pan, F.; Morton, D. P., Minimizing a stochastic maximum-reliability path, Networks, 52, 3, 111-119 (2008) · Zbl 1172.90345
[55] Pollack, M., The maximum capacity through a network, Operations Research, 8, 5, 733-736 (1960)
[56] Punnen, A. P., A linear time algorithm for the maximum capacity path problem, European Journal of Operational Research, 53, 3, 402-404 (1991) · Zbl 0732.90085
[57] Radzik, T., Fractional combinatorial optimization, In handbook of combinatorial optimization, 1311-1355 (2013), Springer: Springer New York, NY
[58] Ramamoorthy, P.; Jayaswal, S.; Sinha, A.; Vidyarthi, N., Multiple allocation hub interdiction and protection problems: Model formulations and solution approaches, European Journal of Operational Research, 270, 1, 230-245 (2018) · Zbl 1403.90488
[59] Ramaswamy, R.; Orlin, J. B.; Chakravarti, N., Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs, Mathematical Programming, 102, 2, 355-369 (2005) · Zbl 1079.90137
[60] Ramirez-Marquez, J. E., A bi-objective approach for shortest-path network interdiction, Computers & Industrial Engineering, 59, 2, 232-240 (2010)
[61] Rocco, S.; Claudio, M.; Ramirez-Marquez, J. E.; Salazar, A.; Daniel, E.; Zio, E., A flow importance measure with application to an italian transmission power system, International Journal of Performability Engineering, 6, 1 (2010)
[62] Royset, J. O.; Wood, R. K., Solving the bi-objective maximum-flow network-interdiction problem, INFORMS Journal on Computing, 19, 2, 175-184 (2007) · Zbl 1241.90139
[63] Salmeron, J.; Wood, R. K.; Baldick, R., Analysis of electric grid security under terrorist threat, IEEE Transactions on power systems, 19, 2, 905-912 (2004)
[64] Schrijver, A., Theory of linear and integer programming (1998), John Wiley & Sons · Zbl 0970.90052
[65] Schulze, M., A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method, Social Choice and Welfare, 36, 2, 267-303 (2011) · Zbl 1232.91185
[66] Sefair, J. A.; Smith, J. C., Dynamic shortest-path interdiction, Networks, 68, 4, 315-330 (2016) · Zbl 1390.90124
[67] Sefair, J. A.; Smith, J. C., Exact algorithms and bounds for the dynamic assignment interdiction problem, Naval Research Logistics, 64, 5, 373-387 (2017) · Zbl 1411.90207
[68] Sefair, J. A.; Smith, J. C.; Acevedo, M. A.; Fletcher, J. R.J., A defender-attacker model and algorithm for maximizing weighted expected hitting time with application to conservation planning, IISE Transactions, 49, 12, 1112-1128 (2017)
[69] Smith, J. C.; Prince, M.; Geunes, J., Modern network interdiction problems and algorithms, In handbook of combinatorial optimization, 1949-1987 (2013), Springer New York
[70] Smith, J. C.; Song, Y., A survey of network interdiction models and algorithms, European Journal of Operational Research, 283, 3, 797-811 (2020) · Zbl 1441.90048
[71] von Stackelberg, H., The theory of the market economy (1952), William Hodge and Co: William Hodge and Co London
[72] Tahernejad, S.; Ralphs, T. K.; DeNegre, S. T., A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation, Mathematical Programming Computation, 12, 4, 529-568 (2020) · Zbl 1458.90488
[73] Tragoudas, S., The most reliable data-path transmission, IEEE Transactions on Reliability, 50, 3, 281-285 (2001)
[74] Washburn, A.; Wood, R. K., Two-person zero-sum games for network interdiction, Operations Research, 43, 2, 243-251 (1995) · Zbl 0832.90124
[75] Wood, R. K., Deterministic network interdiction, Mathematical and Computer Modelling, 17, 2, 1-18 (1993) · Zbl 0800.90772
[76] Xu, N., A survey of sensor network applications, IEEE communications magazine, 40, 8, 102-114 (2002)
[77] Xu, P.; Wang, L., An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions, Computers & Operations Research, 41, 309-318 (2014) · Zbl 1348.90496
[78] Xue, Y.; Nahrstedt, K., Providing fault-tolerant ad hoc routing service in adversarial environments, Wireless Personal Communications, 29, 3-4, 367-388 (2004)
[79] http://www.optimization-online.org/DB_FILE/2014/07/4455.pdf
[80] Zenklusen, R., Matching interdiction, Discrete Applied Mathematics, 158, 15, 1676-1690 (2010) · Zbl 1208.05120
[81] Zenklusen, R., An \(o ( 1 )\)-approximation for minimum spanning tree interdiction, In Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science (SFCS), 709-728 (2015)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.