*************************************************************************

                Department of Mathematical Sciences                       
                   The Johns Hopkins University                           
                                                                        
             THE SECOND ANNUAL ALAN J. GOLDMAN LECTURE
                                                                        
*************************************************************************

Thomas L. Magnanti                                November 30, 2000
Institute Professor and Dean of Engineering       110 MARYLAND HALL
Massachusetts Institute of Technology             NO PRESEMINAR
                                                  Refreshments: 3:30 p.m.
                                                  Seminar: 4:00 p.m.
                                                
*************************************************************************

                  THE GOOD, THE BAD, AND THE UGLY:
            MODELING AND SOLVING NETWORK DESIGN PROBLEMS

*************************************************************************

                            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.

Several decades ago, applied mathematicians and operations researchers
developed several core results concerning the optimal design of
telecommunication and other networks, particularly solution 
procedures for the minimal spanning tree problem and several of its
variants and the solution to the classical network synthesis problem (the
multi-terminal network flow problem).  Since then, the operations research
and computer science communities have developed an impressive array of new
theories and solution methods, including the design and analysis of
heuristics, Lagrangian relaxation, dual ascent methods, and polyhedral
combinatorics.  Researchers and practitioners have successfully applied
these techniques to many network design problems.  Nevertheless, the
general network design problem remains computationally elusive and
continues to pose significant challenges to the research community.

This talk will summarize some of these contributions, drawing a 
distinction between problems that are uncapacitated (are 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 problems that arise in
scheduling and routing.

*************************************************************************

Professor Alan Goldman is an expert in operations research -- the use of
mathematics to improve decisions on the design and operation of complex
systems -- whose favorite application areas include facility siting,
transportation systems, and mathematical game theory.  He has been a
faculty member in the Department of Mathematical Sciences since 1979, and
is now Professor Emeritus.  Professor Goldman holds several awards,
including a U. S. Department of Commerce Gold Medal presented in 1976
and election in 1989 to the highly prestigious National Academy of
Engineering.

The Alan J. Goldman Lecture Fund, established in 1999 upon the occasion
of his retirement from full-time status, honors Professor Goldman and his
many accomplishments and supports a visit and lecture each fall by a
distinguished mathematical scholar in the fields of operations research
and optimization.  Professor Goldman himself gave the inaugural Goldman
Lecture in 1999.