1995 'Research Excellence' Prize Awarded to Engineering's Goldfarb

Photograph: Donald Goldfarb. Photo Credit: Joe Piniero.

Donald Goldfarb, acting dean of the School of Engineering and Applied Science and professor of industrial engineering and operations research, has been awarded a prestigious management science prize for a method he developed to dramatically cut the time computers take to solve certain complex problems.

The 1995 Prize for Research Excellence in the Interface Between Operations Research and Computer Science was awarded by the Computer Science Technical Section of the Institute for Operations Research and the Management Sciences (INFORMS) at its national meeting in Los Angeles Apr. 23-26.

INFORMS is a professional organization with more than 13,500 members.

The prize was given for a paper Goldfarb authored in collaboration with J.J. Forrest, a senior research scientist at IBM Corp.

The paper, "Steepest edge simplex algorithms for linear programming," appeared in 1992 in the journal Mathematical Programming, of which Goldfarb was recently named editor-in-chief.

It describes a method devised by the Columbia scientist to more easily solve linear programming problems.

Such problems involve the optimization of extremely complex systems, such as determining the most efficient production schedule for a refinery or finding the smallest crew to cover all an airline's flights.

These problems, which typically have hundreds of thousands of variables and tens of thousands of constraints, consume more of industry's computer time than any other class of problems.

From 5 Days to 20 Minutes

Goldfarb's method, which was inspired by the work more than 50 years ago of the mathematician George Dantzig, reduces the computer running time needed to solve many of these problems from as long as five days to as little as 20 minutes.

The steepest edge simplex method has been incorporated into the code of the linear programming software sold by such companies as IBM, and is now widely used in the manufacturing, telecommunications and transportation industries, among others.

Tremendous Impact

"Without a doubt, the steepest edge simplex method is the single most important tool developed in the last 20 years for the solution of difficult linear programs," said Daniel Bienstock, professor of industrial engineering and operations research at Columbia. "It has had a tremendous impact in many large-scale industrial applications."

Goldfarb, who has also served as chairman of the department of industrial engineering and operations research since 1984, has been acting dean of Columbia's engineering school since July 1994.

He received a B.S.Ch.E. from Cornell in 1962 and the M.A. and Ph.D. from Princeton in 1965 and 1966 respectively.

Before joining the Columbia faculty in 1982, he was a professor in the department of computer sciences at the CCNY, where he served as chairman during the 1978-79 academic year.

He has served as editor or associate editor of five academic journals and has published more than 50 research papers.

In addition to his duties as acting dean, he continues to teach and to conduct research, supervising three doctoral students and one post-doctoral student.

Columbia University Record -- May 26, 1995 -- Vol. 20, No. 30