Optimization Online


Reformulation and Sampling to Solve a Stochastic Network Interdiction Problem

Udom Janjarassuk (udj2***at***lehigh.edu)
Jeff Linderoth (jtl3***at***lehigh.edu)

Abstract: The Network Interdiction Problem involves interrupting an adversary's ability to maximize flow through a capacitated network by destroying portions of the network. A budget constraint limits the amount of the network that can be destroyed. In this paper, we study a stochastic version of the network interdiction problem in which the successful destruction of an arc of the network is a Bernoulli random variable, and the objective is to minimize the maximum expected flow of the adversary. Using duality and linearization techniques, an equivalent deterministic mixed integer program is formulated. The structure of the reformulation allows for the application of decomposition techniques for its solution. Using a parallel algorithm designed to run on a distributed computing platform known as a computational grid, we give computational results showing the efficacy of a sampling-based approach to solving the problem.

Keywords: Stochastic Network Interdiction, Sample Average Approximation, Computational Grid

Category 1: Stochastic Programming

Category 2: Applications -- OR and Management Sciences (Other )

Citation: Technical Report 06T-001, Lehigh University, Department of Industrial and Systems Engineering, January, 2006

Download: [PDF]

Entry Submitted: 01/31/2006
Entry Accepted: 02/01/2006
Entry Last Modified: 01/31/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society