الگوریتم تقریبی برای مساله ممانعت از بیشترین جریان شبکه

Iranian Journal of Numerical Analysis and Optimization

Article 1, Volume 10, Issue 1 - Serial Number 17, January 0, Pages 1-18   

Document Type: Research Article

DOI: 10.22067/ijnao.v10i1.75392

Abstract

در این مقاله به بررسی مساله ممانعت از بیشترین جریان شبکه می‌پردازیم. نخست تعبیر جدیدی از مساله را ارائه داده و سپس مفهوم "برش بهینه" را تعریف می‌کنیم. یک الگوریتم ابتکاری برای یافتن تقریبی از برش بهینه پیشنهاد می‌کنیم. در نهایت نشان خواهیم داد که روش ابتکاری پیشنهادی برای نوع خاصی از شبکه‌ها، تبدیل به یک الگوریتم آلفا-تقریب خواهد شد. با اجرای الگوریتم بر روی سه نوع شبکه مختلف، برتری این روش را نسبت به حل مستقیم مدل بااستفاده از CPLEX نشان خواهیم داد.

Keywords

ممانعت; الگوریتم تقریبی; جریان شبکه; برش با کمترین ظرفیت

References

[1] Afsharirad, M. and Taghizadeh, H. Maximum dynamic network flow interdiction problem: New formulation and solution procedures, Comput. Ind. Eng. 65(4) (2013), 531–536.

[2] Afsharirad, M. and Taghizadeh, H. Two extended formulations for car dinality maximum flow network interdiction problem, Networks, 69(4)(2017), 367–377.

[3] Altner, D.S., Ergun, O. and Uhan, N.A., The maximum flow network interdiction problem: valid inequalities, integrality gaps and approximability, Oper. Res. Lett., 38 (2010), 33–38.

[4] Assimakopoulos, N. A network interdiction model for hospital infection control, Computers in Biology and Medicine, 17 (1987), 413–422.

[5] Brown, G., Carlyle, M., Salmeron, J. and Wood, R.K. Defending critical infrastructure, Interfaces, 36(6) (2005), 530–544.

[6] Burch, C., Carr, R., Krumke, S., Marathe, M., Phillips, C. and Sundberg, E. A decomposition-based pseudoapproximation algorithm for network flow inhibition, Network interdiction and stochastic integer pro

gramming (Davis, CA, 2002), 51–68, Oper. Res./Comput. Sci. InterfacesSer., 22, Kluwer Acad. Publ., Boston, MA, 2003.

[7] Chestnut, S.R. and Zenklusen, R. Hardness and approximation for network flow interdiction, Networks, 69(4) (2017), 378-387.

[8] Church, R.L., Scaparra, M.P. and Middleton, R.S. Identifying critical infrastructure: The median and covering facility interdiction problems, Annals of the Association of American Geographers, 94 (2004), 491–502.

[9] Cormican, K.J., Morton, D.P., and Wood, R.K. , Stochastic network interdiction, Oper. Res., 46 (1998), 184–197.

[10] Durbin, E.P. An interdiction model of highway transportation, Santa Monica, CA: RAND Corporation, 1966.

[11] Granata, D., Steeger, G. and Rebennack, S. Network interdiction via a critical disruption path: Branch-and-price algorithms, Comput. Oper. Res., 40(11) (2013), 2689–2702.

[12] Lim, C. and Smith, J.C. Algorithms for discrete and continuous multi commodity flow network interdiction problems, IIE Transactions, 39(2007),15–26.

[13] Lunday, B.J. and Sherali, H.D. A dynamic network interdiction problem, Informatica, 21(4) (2010), 553–574.

[14] Lunday, B.J. and Sherali, H.D. Network interdiction to minimize the maximum probability of evasion with synergy between applied resources, Ann. Oper. Res. 196 (2012), 411–42.

[15] Miller, L.E. (2011), Catalog of network connectivity models, http://w3.antd.nist.gov/wctg/netanal/netanal-netmodels.html. Accessed 14 July 2011.

[16] Morton, D.P., Pan, F. and Saeger, K.J. Models for nuclear smuggling interdiction, IIE Transactions 38 (2007), 3–14

[17] Nandi, A.K. and Medal H.R. Methods for removing minimize the spread of infections, Comput. Oper. Res., 69 (2016), 10–24.

[18] Orlin, J. Max flows in O(nm) time, or better. STOC’13—Proceedings of the 2013 ACM Symposium on Theory of Computing, 765–774, ACM, New York, 2013.

[19] Pan, F. Stochastic network interdiction: Models and methods, Ph.D. thesis, University of Texas at Austin, 2005.

[20] Philips, C.A. The network inhibition problem, Proceeding of 25th ACM Symposium of Theory of Computing, San Diego, CA. (1993), 776–785.

[21] Salmeron, J. (2012), Deception tactics for network interdiction: A multi objective approach, Networks, 60(1), 45–58.

[22] Sullivan, K.M., Morton, D.P., Pan, F. and Smith, J.C. (2011), Securing a border under asymmetric information, Naval Res. Logist. 61(2) (2014), 91–100.

[23] Sullivan, K.M., Smith J.C. and Morton, D.P. Convex hull representation of the interdiction problem, Math. Program. 145(1-2) (2014), 349–376.

[24] Towle, E. and Luedtke, J. New solution approaches for the maximum reliability stochastic network interdiction problem, Comput. Manag. Sci. 15(3-4) (2018), 455–477.

[25] Wollmer, R.D. Removing arcs from a Network, Oper. Res. , 12 (1964), 934–940.

[26] Wood, R.K. Deterministic network interdiction problem, Math. Comp. Model., 17 (1993), 1–18