TY - JOUR

T1 - Algorithms for discrete and continuous multicommodity flow network interdiction problems

AU - Lim, Churlzu

AU - Smith, J. Cole

N1 - Funding Information:
The authors gratefully acknowledge financial support from the Air Force Office of Scientific Research (F49620-03-1-0477), and from the Office of Naval Research (N66001-01-1-8925). The authors also thank two anonymous referees and an Associate Editor for their remarks, which improved the presentation of this paper.
Funding Information:
J. Cole Smith is an Associate Professor in the Department of Industrial and Systems Engineering at the University of Florida. He earned his Ph.D. from Virginia Tech in 2000, and has served as the Principal Investigator for grants sponsored by the Air Force Office of Scientific Research (AFOSR), the Defense Advanced Research Projects Agency (DARPA), and the Office of Naval Research (ONR). His research interests include integer and nonlinear optimization, network optimization, modeling and algorithmic approaches to games with adversarial players, and heuristic search algorithms. His research awards are highlighted by the Young Investigator Award from the ONR, and the Pritsker Doctoral Dissertation Award, given by the Institute of Industrial Engineers.

PY - 2007/1

Y1 - 2007/1

N2 - We consider a network interdiction problem on a multicommodity flow network, in which an attacker disables a set of network arcs in order to minimize the maximum profit that can be obtained from shipping commodities across the network. The attacker is assumed to have some budget for destroying (or "interdicting") arcs, and each arc is associated with a positive interdiction expense. In this paper, we examine problems in which interdiction must be discrete (i.e., each arc must either be left alone or completely destroyed), and in which interdiction can be continuous (the capacities of arcs may be partially reduced). For the discrete problem, we describe a linearized model for optimizing network interdiction that is similar to previous studies in the field, and compare it to a penalty model that does not require linearization constraints. For the continuous case, we prescribe an optimal partitioning algorithm along with a heuristic procedure for estimating the optimal objective function value. We demonstrate on a set of randomly generated test data that our penalty model for the discrete interdiction problem significantly reduces computational time when compared to that consumed by the linearization model.

AB - We consider a network interdiction problem on a multicommodity flow network, in which an attacker disables a set of network arcs in order to minimize the maximum profit that can be obtained from shipping commodities across the network. The attacker is assumed to have some budget for destroying (or "interdicting") arcs, and each arc is associated with a positive interdiction expense. In this paper, we examine problems in which interdiction must be discrete (i.e., each arc must either be left alone or completely destroyed), and in which interdiction can be continuous (the capacities of arcs may be partially reduced). For the discrete problem, we describe a linearized model for optimizing network interdiction that is similar to previous studies in the field, and compare it to a penalty model that does not require linearization constraints. For the continuous case, we prescribe an optimal partitioning algorithm along with a heuristic procedure for estimating the optimal objective function value. We demonstrate on a set of randomly generated test data that our penalty model for the discrete interdiction problem significantly reduces computational time when compared to that consumed by the linearization model.

KW - Bilinear programming

KW - Integer programming

KW - Multicommodity flows

KW - Network interdiction

UR - http://www.scopus.com/inward/record.url?scp=33750618042&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33750618042&partnerID=8YFLogxK

U2 - 10.1080/07408170600729192

DO - 10.1080/07408170600729192

M3 - Article

AN - SCOPUS:33750618042

VL - 39

SP - 15

EP - 26

JO - IIE Transactions (Institute of Industrial Engineers)

JF - IIE Transactions (Institute of Industrial Engineers)

SN - 2472-5854

IS - 1

ER -