Skip to main content
Kent Academic Repository

An exact solution approach for the interdiction median problem with fortification

Scaparra, Maria Paola, Church, Richard L. (2008) An exact solution approach for the interdiction median problem with fortification. European Journal of Operational Research, 189 (1). pp. 76-92. ISSN 0377-2217. (doi:10.1016/j.ejor.2007.05.027) (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided) (KAR id:3138)

The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided.
Official URL:
http://dx.doi.org/10.1016/j.ejor.2007.05.027

Abstract

Systematic approaches to security investment decisions are crucial for improved homeland security. We present an optimization modeling approach for allocating protection resources among a system of facilities so that the disruptive effects of possible intentional attacks to the system are minimized. This paper is based upon the p-median service protocol for an operating set of p facilities. The primary objective is to identify the subset of q facilities which, when fortified, provides the best protection against the worst-case loss of r non-fortified facilities. This problem, known as the r-interdiction median problem with fortification (IMF), was first formulated as a mixed-integer program by Church and Scaparra [R.L. Church, M.P. Scaparra, Protecting critical assets: The r-interdiction median problem with fortification, Geographical Analysis 39 (2007) 129-146]. In this paper, we reformulate the IMF as a maximal covering problem with precedence constraints, which is amenable to a new solution approach. This new approach produces good approximations to the best fortification strategies. Furthermore, it provides upper and lower bounds that can be used to reduce the size of the original model. The reduced model can readily be solved to optimality by general-purpose MIP solvers. Computational results on two geographical data sets with different structural characteristics show the effectiveness of the proposed methodology for solving IMF instances of considerable size.

Item Type: Article
DOI/Identification number: 10.1016/j.ejor.2007.05.027
Uncontrolled keywords: logistics; security investment; protection models; integer programming
Subjects: H Social Sciences > HD Industries. Land use. Labor > HD29 Operational Research - Applications
Divisions: Divisions > Kent Business School - Division > Department of Analytics, Operations and Systems
Depositing User: Suzanne Duffy
Date Deposited: 14 May 2008 07:11 UTC
Last Modified: 19 Sep 2023 15:04 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/3138 (The current URI for this page, for reference purposes)

University of Kent Author Information

Scaparra, Maria Paola.

Creator's ORCID: https://orcid.org/0000-0002-2725-5439
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.