Estonian Winter Schools in Computer Science    
Eesti arvutiteaduse talvekoolid
EWSCS 2006
EATTK 2006

11th Estonian Winter School in Computer Science (EWSCS)
XI Eesti Arvutiteaduse Talvekool

Palmse, Estonia, March 5-10, 2006

under the auspices of European Educational Forum

Yvo Desmedt

Dept. of Computer Science
University College London
London, United Kingdom

Robust Operations Research


In the 1950s, Harris-Ross, of the US Air Force, analyzed the rail network that linked the Soviet Union to its satellite countries in Eastern Europe using graph theory. They used it to evaluate the maximum flow of goods via rail from the Soviet Union to Eastern Europe and which rail links to blow up to disrupt the network.

Today, terrorist have the capability to destroy parts of our critical infrastructure. Heuristic methods to study the vulnerabilities of these are inadequate. We discuss scientific methods to analyze this and to obtain operations robust against an adversary with limited resources.

The first lecture starts from a historical perspective. It briefly surveys the heuristics used by the by the US President's Commission on Critical Infrastructure Protection during the Clinton administration. It also explains how to evaluate vulnerabilities in distribution networks (electricity, food, fuel, water). Data communication networks can also be analyzed in a similar matter. However, two issues make these different: the adversary can automate the attack and can take over a node without destroying it.

The second part focuses on production networks. These can be studied using PERT graphs. However, they do not model available redundancy, which is critical to achieve robustness. AND/OR graphs can be used to describe one production network involving different parts of the economy. The question how to analyze the vulnerabilities is addressed. Economic models can be used to study the problem at a macro scale. The topics are discussed during the second lecture and part of the third lecture.

Above approaches rely on graph theory. However, not all aspects of our live can be modeled this way. Operational research addresses this in its generality. When operations are potentially under attack, the question how robust they are is addressed by transforming the problem into a robust operation problem. This topic is addressed during the last lecture.

Algorithms for and computational complexity of some of the issues above are given.

Course materials

About the Lecturer


Modified Apr 09, 2006 0:14 by ewscs06(at)