Stochastic Network Interdiction

Operations Research - Tập 46 Số 2 - Trang 184-197 - 1998
Kelly J. Cormican1, David P. Morton2, R. Kevin Wood1
1Naval Postgraduate School, Monterey, California
2The University of Texas at Austin, Austin, Texas

Tóm tắt

Using limited assets, an interdictor attempts to destroy parts of a capacitated network through which an adversary will subsequently maximize flow. We formulate and solve a stochastic version of the interdictor's problem: Minimize the expected maximum flow through the network when interdiction successes are binary random variables. Extensions are made to handle uncertain arc capacities and other realistic variations. These two-stage stochastic integer programs have applications to interdicting illegal drugs and to reducing the effectiveness of a military force moving materiel, troops, information, etc., through a network in wartime. Two equivalent model formulations allow Jensen's inequality to be used to compute both lower and upper bounds on the objective, and these bounds are improved within a sequential approximation algorithm. Successful computational results are reported on networks with over 100 nodes, 80 interdictable arcs, and 180 total arcs.

Từ khóa


Tài liệu tham khảo

Ahuja R. K., 1993, Network Flows

10.1002/net.3230100105

10.1007/BF01585113

Birge J. R., 1987, COAL: Committee Algorithms Math. Programming Soc., 17, 1

10.1137/0326042

10.1007/BF01582286

10.1007/BFb0121114

10.1002/net.3230140111

10.1002/net.3230140307

10.1002/net.3230060208

10.1007/978-3-642-95696-6

10.1002/net.3230240403

10.1080/17442508308833273

10.1287/opre.25.2.315

IBM Corporation, 1991, Optimization Subroutine Library Guide and Reference, Release 2

10.1007/978-3-642-61370-8_2

10.1016/0167-6377(93)90002-X

10.1214/aoms/1177706203

10.1002/nav.3800170302

Steinrauf R. L. A network interdiction model. (1991) . M.S. thesis, Naval Postgraduate School, Monterey, CA

10.1137/0117061

10.1002/net.3230170108

10.1007/BF02604638

10.1287/opre.43.2.243

10.1137/0114008

Wollmer R. D., 1964, J. Opns. Soc. Amer., 12, 934

10.1007/BF01581648

10.1016/0895-7177(93)90236-R

Thông tin
Thông tin xuất bản

Operations Research

Tập 46 Số 2

184-197

Thông tin tác giả