Large-Scale Linear Programming (Continued)

Monday, September 9, 2002 - 10:30am - 11:15am
Keller 3-180
Daniel Bienstock (Columbia University)
Linear Programming is the central tool of Mathematical Programming. Linear programming models are flexible enough to adequately describe many realistic problems arising in modern industrial settings, while at the same time taking advantage of the considerable expertise on computational linear algebra that has been developed during the last fifty years. As a result, linear programming models are abundantly used in logistics, transportation, finance and many other practical applications.

Linear Programming has undergone profound changes during the last twenty years, resulting in codes that are thousands (and sometimes, millions) of times faster than what was available just fifteen years ago. Yet difficult challenges persist, in the form of large-scale linear programming problems arising in routing, network design, chip design and other settings. In fact, large problem instances render even the best of codes nearly unusable.

In this lecture we will survey fundamentals of Linear Programming theory, with special emphasis on recent developments, and in particular, on techniques geared to handling very large instances.