March 15 2002, University of California at Davis

This mini-workshop is concerned with the use of stochastic models to study network interdiction problems and the study of solution methods for stochastic integer programs. This workshop will bring together a diverse group of researchers.

A tentative list of participants: Rudiger Schulz (Duisburg), Raymond Hemmecke (UC Davis), Julie Higle (Arizona), Alan Laub (UC Davis), Suvrajeet Sen (Arizona), Kevin Wood (Naval Postgraduate School), David Morton (Austin), Charles Martel (UC Davis), Serkan Hosten (San Francisco State), Shmuel Onn (Technion, Haifa), Cynthia Phillips (Sandia National Labs.),

An schedule for talks will be announced shortly. the workshop will be held in AOB IV, room 261. The building is on the SW corner of 1st and A and the parking lot is on the SE corner of 1st and A. We can provide parking passes for those who need them. Check out this map of campus

Here you can find driving directions to UC Davis campus.:

For more information please contact the organizers, David Woodruf ( or Jesus De Loera ( There will not be any registration fee, but ALL participants are kindly requested to send a message if planning to attend.

Here is all travel and hotel information .

This event is funded in part by the Air Force Office of Scientific Research through a grant to the Department of Applied Science, UC Davis.

Schedule for Workshop on Network Interdiction and Stochastic Integer Programming

Room 174, AOB IV (SW Corner of 1st and A)

8:30 Coffee, juice and rolls

9:00 Kevin Wood - Naval Postgraduate School Network Interdiction

10:00 Cynthia Phillips - Sandia National Laboratories Network Interdiction

11:00 Raymond Hemmecke - UC Davis Network Interdiction


1:30 Higle - University of Arizona Stochastic Programming

2:15 Sen - Univerisity of Arizona Stochastic Programming

3:00 Morton and Pan - University of Texas Network Interdiction

4:00 Schultz - University of Duisburg Stochastic programming



Titles and abstracts:

Kevin Wood Naval Postgraduate School

Network Interdiction

This talk will cover a number of techniques for solving, and related to solving, deterministic and stochastic network interdiction problems: Efficient enumeration of s-t cuts; an optimization-based heuristic for the max-flow interdiction problem; and a "covering algorithm" for both deterministic and stochastic interdiction problems. New avenues of research on interdicting and hardening communications networks will also be discussed.


Cynthia Phillips Sandia National Laboratories

Pseudoapproximation algorithm for the (flow) inhibition problem

Abstract: In the network inhibition problem, we wish to expend a limited budget removing edges or pieces of edges so as to minimize the resulting maximum s-t flow. The problem is strongly NP-hard. In this talk, I will summarize previous results on the structure and complexity of this problem (e.g. fully polynomial-time approximation schemes for planar graphs). I will then present a simple polynomial-time pseudoapproximation algorithm, based on a linear-programming relaxation of an integer program. This algorithm returns either a (1, 1 + 1/epsilon)-approximation or a (1+\epsilon, 1)-pseudoapproximation for epsilon > 0, but we do not know which a priori. The parameter epsilon biases the nature of the solution, but does not effect the running time.

This is joint work with Carl Burch (College of St Benedict and St John's University), Bob Carr (Sandia National Laboratories), Sven Krumke (Konrad-Zuse-Zentrum), Madhav Maranthe (Los Alamos National Laboratory), and Eric Sundberg (Rutgers).


Raymond Hemmecke - UC Davis with Jesus De Loera, David L. Woodruff, and Ruriko Yoshida

Interdiciton and Hardening of Computer Networks

Abstract: Reliance on computer networks gives rise to the problem of allocating resources to the task of hardening them against interdiction. In this talk we describe models for optimal hardening against an optimal network interdiction that can involve attacks on both arcs and nodes. Preliminary computational results are presented.


David Morton University of Texas

Stochastic Network Interdiction of Nuclear Material Smuggling

Abstract: The U.S. Department of Energy collaborates with the Russian Federation State Customs Committee, and other countries of the former Soviet Union, to help strengthen the overall capability of preventing the illicit trafficking of sensitive nuclear materials, equipment, and technology. We describe a stochastic network interdiction model designed to help select sites for installing detection equipment. Multiple variants of our basic stochastic integer program are developed to handle smugglers with different levels of information. (This is joint work with Bill Charlton and Feng Pan.)


Julie Higle - University of Arizona The $C^3$ Theorem and a $D^2$ Algorithm for Stochastic Integer Programming A Branch-and-Price Algorithm For SMIP and its Applications in Stochastic Batch-Sizing Problems"


Ruediger Schultz University of Duisburg

Mean-risk models in two-stage stochastic integer programming

Abstract: The traditional mean-value-based linear stochastic program with recourse can be extended towards risk aversion by adding suitable dispersion terms to the objective. This leads to new questions regarding structure and algorithmics of such models. With accent on excess probabilities as dispersion terms we will report some first results along these lines. Special attention is paid to integer models.