Abstract
In this paper, we model and solve the network interdiction problem of minimizing the maximum flow through a network from a given source node to a terminus node, while incorporating different forms of superadditive synergy effects of the resources applied to the arcs in the network. Within this context, we examine linear, concave, and convex–concave synergy relationships, illustrate their relative effect on optimal solution characteristics, and accordingly develop and test effective solution procedures for the underlying problems. For a concave synergy relationship, which yields a convex programme, we propose an inner-linearization procedure that significantly outperforms the competitive commercial solver SBB by improving the quality of solutions found by the latter by 6.2% (within a time limit of 1800 CPU s), while saving 84.5% of the required computational effort. For general non-concave synergy relationships, we develop an outer-approximation-based heuristic that achieves solutions of objective value 0.20% better than the commercial global optimization software BARON, with a 99.3% reduction in computational effort for the subset of test problems for which BARON could identify a feasible solution within the set time limit.
Similar content being viewed by others
References
Bazaraa MS, Jarvis JJ and Sherali HD (2010). Linear Programming and Network Flows. 4th edn, John Wiley and Sons: New York, NY.
Bier VM, Haphuriwat N, Menoyo J, Zimmerman R and Culpen AM (2008). Optimal resource allocation for defense of targets based on differing measures of attractiveness. Risk Analysis 28 (3): 763–770.
Carrigy A, Rocco CM and Ramirez-Marquez JE (2010). Multistate stochastic network interdiction via reliability modelling and evolutionary optimization. Journal of Risk and Reliability 224 (1): 27–42.
Chern M and Lin K (1995). Interdicting the activities of a linear program—A parametric analysis. European Journal of Operational Research 86 (3): 580–591.
Cormican KJ (1995). Computational Methods for Deterministic and Stochastic Network Interdiction Problems. Master's Thesis, US Naval Postgraduate School.
Ford LR and Fulkerson DR (1955). A simple algorithm for finding maximal network flows and an application to the hitchcock problem. Research Memorandum RM-160. The Rand Corporation: Santa Monica, CA.
Ford LR and Fulkerson DR (1956). Maximal flow through a network. Canadian Journal of Mathematics 8: 399–404.
Fulkerson DR and Harding GC (1977). Maximizing the minimum source-sink path subject to a budget constraint. Mathematical Programming 13 (1): 116–118.
Ghare PM, Montgomery DC and Turner WC (1971). Optimal interdiction policy for a flow network. Naval Research Logistics Quarterly 18 (1): 37–45.
Golden B (1978). A problem in network interdiction. Naval Research Logistics Quarterly 25 (4): 711–713.
Harris TE and Ross FS (1955). Fundamentals of a method for evaluating rail net capacities. Research Memorandum RM-1573. The Rand Corporation: Santa Monica, CA.
Israeli E and Wood RK (2002). Shortest-path network interdiction. Networks 40 (2): 97–111.
Levitin G and Hausken K (2010). Separation in homogeneous systems with independent identical elements. European Journal of Operational Research 203 (3): 625–634.
Lim C and Smith JC (2007). Algorithms for discrete and continuous multicommodity flow network interdiction problems. IIE Transactions 39 (1): 15–26.
Lunday BJ (2010). Resource allocation on networks: Nested event tree optimization, network interdiction, and game theoretic methods. PhD Dissertation, Virginia Polytechnic Institute and State University, Blacksburg, VA.
Lunday BJ and Sherali HD (2010). A dynamic network interdiction problem. Informatica 21 (4): 553–574.
Lunday BJ, Sherali HD and Glickman TS (2010). The nested event tree model with application to combating terrorism. INFORMS Journal on Computing 22 (4): 620–634.
McMasters AW and Mustin TM (1970). Optimal interdiction of a supply network. Naval Research Logistics Quarterly 17 (3): 261–268.
Napier RW and Gershenfeld MK (1993). Groups: Theory and Experiences. Houghton Mifflin Company: Boston, MA.
Phillips CA (1993). The network inhibition problem. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing. San Diego, CA, pp 776–785.
Ramirez-Marquez JE, Rocco CM and Levitin G (2011). Optimal network protection against diverse interdictor strategies. Reliability Engineering and System Safety 96 (3): 374–382.
Rocco CM and Ramirez-Marquez JE (2009). Deterministic network interdiction optimization via an evolutionary approach. Reliability Engineering and System Safety 94 (2): 568–576.
Rocco CM and Ramirez-Marquez JE (2011). Vulnerability metrics and analysis for communities in complex networks. Reliability Engineering and System Safety 96 (10): 1360–1366.
Rocco CM, Ramirez-Marquez JE and Salazar DE (2010). Bi and tri-objective optimization in the deterministic network interdiction problem. Reliability Engineering and System Safety 95 (8): 887–896.
Royset RO and Wood RK (2007). Solving the bi-objective maximum-flow network-interdiction problem. INFORMS Journal on Computing 19 (2): 175–184.
von Eye A, Schuster C and Rogers WM (1998). Modelling synergy using manifest categorical variables. International Journal of Behavioral Development 22 (3): 537–557.
Wollmer RD (1964). Removing arcs from a network. Operations Research 12 (6): 934–940.
Wollmer RD (1969). Algorithms for targeting strikes in a lines-of-communication network. Research Memorandum RM-5864-PR. The Rand Corporation: Santa Monica, CA.
Wood RK (1993). Deterministic network interdiction. Mathematical and Computer Modeling 17 (2): 1–18.
Acknowledgements
This work is partially supported by the National Science Foundation under Grant No. CMMI-0969169, acknowledge Dr Nick Sahinidis of the Sahinidis Optimization Group at Carnegie an Omar Nelson Bradley Fellowship in Mathematics, and by the Army Research Office. The authors gratefully Mellon University for permitting the use of the AlphaECP, BARON, CoinBonmin, DICOPT, and SBB solvers. The authors also thank the Associate Editor and three referees for their detailed and constructive comments that have greatly helped improve the presentation of this paper.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Lunday, B., Sherali, H. Minimizing the maximum network flow: models and algorithms with resource synergy considerations. J Oper Res Soc 63, 1693–1707 (2012). https://doi.org/10.1057/jors.2012.8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2012.8