Publication:
The budget constrained r-interdiction median problem with capacity expansion

Placeholder

School / College / Institute

Program

KU-Authors

KU Authors

Co-Authors

Piyade, Nuray
Aras, Necati

Publication Date

Language

Embargo Status

Journal Title

Journal ISSN

Volume Title

Alternative Title

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.

Source

Publisher

Springer

Subject

Operations research, Management science

Citation

Has Part

Source

Central European Journal of Operations Research

Book Series Title

Edition

DOI

10.1007/s10100-009-0110-6

item.page.datauri

Link

Rights

Copyrights Note

Endorsement

Review

Supplemented By

Referenced By

0

Views

0

Downloads

View PlumX Details