Fall 2008 Seminar Series

DATE: October 30, 2008
LOCATION: E40-298
TIME: 4:15pm
Reception immediately following in the ORC ConferenceRoom, E40-106

SPEAKER:
Thomas Magnanti

TITLE
The Good, The Bad, and The Ugly: Progress and Challenges in Designing Optimal Networks

ABSTRACT
Network design problems are deceptively easy to describe, but are often very difficult to solve. Given a set of available (perhaps capacitated) edges, the problem seeks a least cost network, composed of both variable flow costs and edge fixed costs, that meets prescribed multicommodity flow requirements.

This talk will summarize some progress and challenges in solving these problems, usually approximately, drawing a distinction between problems that are uncapacitated (relatively easy), that impose capacities on individual commodities (have intermediate difficulty), and that impose joint capacities across the commodities (are hard). The easiest (uncapacitated) class includes the uncapacitated facility location problem, the intermediate class includes network connectivity and network restoration problems, and the most difficult class includes the network loading (private leasing) problem as well as many scheduling and routing applications.