Title: Determining Network Arc Capacities when Node Supplies and Demands Are Uncertain

Speaker: Amy Cohn, University of Michigan, College of Engineering

Date/Time: Wednesday, February 16, 2011, 10:00 am (CA), 11:00 am (NM)             

Location: CSRI Building/Room 279 (NM), 915/S101 (CA)

Brief Abstract: In this talk, we consider the problem of designing a minimum-cost network (i.e. assigning optimal arc capacities) given uncertain supplies and nodes, such that the arc capacities permit a feasible network flow for any one of a finite and known set of possible supply/demand scenarios. We first present a straightforward linear programming formulation and show that this becomes intractable when the number of possible scenarios is large. Then we present an alternative linear programming formulation whose size does not depend on the number of scenarios, but has an exponential number of constraints. Finally we present an algorithm that uses delayed constraint generation and can quickly solve for the minimum cost set of arc capacities even when the number of possible scenarios is large. Additionally, we explore algorithmic approaches for the case where only a fraction of the scenarios are required to be satisfied.

Dr. Amy Cohn is an Associate Professor in the Department of Industrial and Operations Engineering at the University of Michigan. She holds the AB in Applied Mathematics from Harvard University, magna cum laude, and the Ph.D. in Operations Research from MIT. Her main research interest is in applied network design and discrete optimization problems, primarily in the areas of aviation, healthcare, and energy. Dr. Cohn is the Director of the Engineering for Global Leadership program at the University of Michigan. She is also former Chair of the INFORMS Aviation Applications Section and an active member of AGIFORS and the Industry Studies Association.

CSRI POC: Richard Li-Yang Chen, (925) 294-2087