Abstract
In this article, we elaborate on a budget constrained extension of the r-interdiction median problem with fortification (RIMF). The objective in the RIMF is to find the optimal allocation of protection resources to a given service system consisting of p facilities so that the disruptive effects of r possible attacks to the system are minimized. The defender of the system needs to fortify q facilities of the present system to offset the worst-case loss of r non-fortified facilities due to an interdiction in which the attacker’s objective is to cause the maximum possible disruption in the service level of the system. The defender-attacker relationship fits a bilevel integer programming (BIP) formulation where the defender and attacker take on the respective roles of the leader and the follower. We adopt this BIP formulation and augment it with a budget constraint instead of a predetermined number of facilities to be fortified. In addition, we also assume that each facility has a flexible service capacity, which can be expanded at a unit cost to accommodate the demand of customers who were serviced by some other interdicted facility before the attack. First, we provide a discrete optimization model for this new facility protection planning scenario with a novel set of closest assignment constraints. Then, to tackle this BIP problem we use an implicit enumeration algorithm performed on a binary tree. For each node representing a different fortification scheme, the attacker’s problem is solved to optimality using Cplex 11. We report computational results obtained on a test bed of 96 randomly generated instances. The article concludes with suggestions for future research.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aras N, Aksen D (2008) Locating collection centers for distance- and incentive-dependent returns. Int J Prod Econ 111(2): 316–333
Bard JF (1999) Practical bilevel optimization: algorithms and applications. Nonconvex optimization and its applications, vol 30. Kluwer, Dordrecht
Church RL (2003) COBRA: a new formulation of the classic p-median location problem. Ann Oper Res 122(1/4): 103–120
Church RL, Cohon JL (1976) Multiobjective location analysis of regional energy facility sitting problems. Report prepared for the US energy research and development administration (BNL 50567)
Church RL, ReVelle C (1974) The maximal covering location problem. Pap Reg Sci Assoc 32(1): 101–118
Church RL, Scaparra MP (2007) Protecting critical assets: the r-interdiction median problem with fortification. Geogr Anal 39(2): 129–146
Church RL, Scaparra MP, Middleton RS (2004) Identifying critical infrastructure: the median and covering facility interdiction problems. Ann Assoc Am Geogr 94(3): 491–502
Colson B, Marcotte B, Savard G (2007) An overview of bilevel optimization. Ann Oper Res 153(1): 235–256
Dempe S (2002) Foundations of bilevel programming. Nonconvex optimization and its applications, vol 61. Kluwer, Dordrecht
Gerrard RA, Church RL (1996) Closest assignment constraints and location models: properties and structure. Location Sci 4(4): 251–270
Murray AT, Grubesic TH (eds) (2007) Critical infrastructure: reliability and vulnerability. Advances in spatial sciences. Springer, Berlin
Moore JT, Bard JF (1990) The mixed-integer linear bilevel programming problem. Oper Res 38(5): 911–921
Rojeski P, ReVelle CS (1970) Central facilities location under an investment constraint. Geogr Anal 2(4): 343–360
Scaparra MP, Church RL (2008) A bilevel mixed integer program for critical infrastructure protection planning. Comput Oper Res 35(6): 1905–1923
Scaparra MP, Church RL (2008) An exact solution approach for the interdiction median problem with fortification. Eur J Oper Res 189(1): 76–92
Snyder LV, Daskin MS (2004) Reliability models for facility location: the expected failure cost case. Technical Report, Department of Industrial & Systems Engineering, Lehigh University
Snyder LV, Scaparra MP, Daskin MS, Church RL (2006) Planning for disruptions in supply chain networks. In: Greenberg HK (eds) Tutorials in operations research. INFORMS, Baltimore, pp 234–257
Teixeira JC, Antunes AP (2008) A hierarchical location model for public facility planning. Eur J Oper Res 185(1): 92–104
Verter V, Lapierre SD (2002) Location of preventive health care facilities. Ann Oper Res 110(1/4): 123–132
Wen UP, Yang YH (1990) Algorithms for solving the mixed-integer two-level linear programming problem. Comput Oper Res 17(2): 133–142
Wen UP, Huang AD (1996) A simple tabu search method to solve the mixed-integer linear bilevel programming problem. European Journal of Operational Research 88(3): 563–571
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Aksen, D., Piyade, N. & Aras, N. The budget constrained r-interdiction median problem with capacity expansion. Cent Eur J Oper Res 18, 269–291 (2010). https://doi.org/10.1007/s10100-009-0110-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10100-009-0110-6