Discrete Mathematics and Optimization Seminar

---

DANIEL BIENSTOCK
Columbia University
Monday November 12th at 4.30pm
Burnside 1205



Title. Combinatorial problems on power flows

Abstract. We consider a number of multi-stage combinatorial optimization problems related to the dynamics of a power
grid under stress. The development of a large blackout, in simplified form, is a multi-step process. In
each step some set of edges of the network (which happen to carry "too much flow") are turned off, resulting
in a smaller network. This smaller network is (typically) used to carry the same amount of demand, which
results in some new set of edges to be overloaded. This type of model, a form of which was initially
developed by Dobson et al, leads to a "cascade" behavior. The initial event that starts the process is
caused by natural, though unlikely, factors. The problems we consider are: (1) given a network, does it
have a small-cardinality weakness that would set off a catastrophic cascade, and (2) given a network with a
cascade under development, what is a good online strategy for stopping the cascade. We will discuss these
problems and related background.