Screaming Penguin - Source Does Matter

Two pioneers in linear programming analysis have died..

Leonid Khachiyan, a Russian-born mathematician who helped to advance the field of linear programming, which is used by computer scientists to schedule complex rosters of airline flights and to solve problems in finance and industry, died on April 29 at his home in South Brunswick, N.J. He was 52.

The cause was a heart attack, his family said.

Computer scientists and mathematicians say his work helped revolutionize his field.

Dr. Khachiyan (pronounced KA-tchee-an), who began his career at the Russian Academy of Sciences in Moscow, had been a professor of computer science at Rutgers since 1992.

In 1979, while a researcher at the academy, Dr. Khachiyan published a paper in a Russian mathematics journal that helped to demonstrate that certain problems in linear programming could be solved practically and in a reasonable amount of computing time. Computer scientists had previously relied on a method using the simplex algorithm to review and order vast stores of information.

In his paper "A Polynomial Algorithm in Linear Programming," Dr. Khachiyan proposed using an ellipsoid algorithm in approaching theoretical problems believed to be too demanding for the simplex method, and "turned the field on its head," said Dr. Michael D. Grigoriadis, a professor of computer science at Rutgers.

"The work required a new kind of thinking, and became a way to devise other algorithms, intended to solve even more complex problems." Dr. Grigoriadis continued. Dr. Khachiyan's algorithm was reported in The New York Times in 1979 and received widespread acclaim for its ingenuity. It was subsequently refined and improved by other mathematicians and computer scientists, and has applications in finance, engineering and industry, where it is employed to calculate transportation routes and cost-effective ways of allocating resources.

In later work, Dr. Khachiyan studied cyclic games, which have applications in artificial intelligence, matrix games and polytopes, which are regions of space defined by hyperplanes.

NYT

In spite of impressive developments in computational optimization in the last 20 years, including the rapid advance of interior point methods, the simplex method, invented by George B. Dantzig in 1947, has stood the test of time quite remarkably: It is still the pre-eminent tool for almost all applications of linear programming.

Dantzig, who turns 80 on November 8, is generally regarded as one of the three founders of linear programming, along with von Neumann and Kantorovich. Through his research in mathematical theory, computation, economic analysis, and applications to industrial problems, he has contributed more than any other researcher to the remarkable development of linear programming.

Dantzig's work has been recognized by numerous honors, among them the National Medal of Science (1975), the John von Neumann Theory Prize of the Operations Research Society of America and the Institute of Management Sciences (1974), and membership in the National Academy of Sciences, the National Academy of Engineering, and the American Academy of Arts and Sciences. But he has his own basis for judging his work: "The final test of any theory," he said in the opening sentence of his 1963 book Linear Programming and Extensions, "is its capacity to solve the problems which originated it."

Linear programming and its offspring (such as nonlinear constrained optimization and integer programming) have come of age and have demonstrably passed this test, and they are fundamentally affecting the economic practice of organizations and management. Computer scientist Laszlo Lovasz said in 1980, "If one would take statistics about which mathematical problem is using up most of the computer time in the world, then (not including database handling problems like sorting and searching) the answer would probably be linear programming." That same year, Eugene Lawler of Berkeley offered the following summary: "It [linear programming] is used to allocate resources, plan production, schedule workers, plan investment portfolios and formulate marketing (and military) strategies. The versatility and economic impact of linear programming in today's industrial world is truly awesome."

Dantzig's own assessment, set forth in the chapter he contributed to the History of Mathematical Programming: A Collection of Personal Reminiscences, is characteristically modest. In his words: "The tremendous power of the simplex method is a constant surprise to me." Citing the simple example of an assignment problem (70 people to 70 jobs) and the impossibly vast computing power that would be required to scan all the permutations to select the one that is best, he observed that "it takes only a moment to find the optimum solution using a personal computer and standard simplex or interior point method software."

Dantzig's unassuming nature and complete lack of pretension are the subject of countless anecdotes recounted by friends and colleagues. One researcher in optimization contributed his favorite George Dantzig story to SIAM News: About 15 years ago, having just completed his PhD, he found himself at a loss for words when, on meeting Dantzig for the first time, Dantzig enthusiasticaly responded to the introduction, "I've heard so much about you!"

Stanford