Professor Ellis L. Johnson

The Professor Emeritus and the Coca-Cola Chaired Professor in the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Institute of Technology in Atlanta, Georgia, he received a B.A. degree in Mathematics at Georgia Tech and earned his Ph.D. in Operations Research from the University of California at Berkeley in 1965. He was a student of George Dantzig, an American mathematical scientist who made important contributions to operations research, computer science, economics, and statistics. In 1980-1981, he visited the University of Bonn, Germany, as recipient of the Humboldt Senior Scientist Award. After several years at Yale University, he joined the IBM T.J. Watson Research Center where he worked for 26 years in Yorktown Heights, New York. In 1982, he founded the Modeling and Optimization Center and managed it until 1990. It was in 1990 that he was named IBM Fellow, the highest honor a scientist, engineer, or programmer at IBM can achieve. He retired from IBM in 1993 to move to the Coca-Cola Chair Professorship at Georgia Tech School of Industrial and Systems Engineering, where he co-founded and co-directed the Logistics Engineering Center with Professor George Nemhauser. His research interests in logistics include crew scheduling and real-time repair, fleet assignment and routing, distribution planning, network problems, and combinatorial optimization. In addition to the 1990 IBM Fellow award, he has received a number of other awards, including: the 2009 Fellow from the Society for Industrial and Applied Mathematics; the 2000 and 2002 Fellow from the Institute for Operations Research and the Management Sciences (INFORMS); in 1988, the National Academy of Engineers award; in 1985, the George B. Dantzig Prize for his research in mathematical programming; the 1983 Lanchester Prize for his paper with Crowder and Padberg; and in 1980, the Senior Scientist Award, Alexander von Humboldt Foundation. He also received the 2000 John von Neumann Theory Prize jointly with Manfred W. Padberg in recognition of his fundamental contributions to integer programming and combinatorial optimization. Their work combines theory with algorithm development, computational testing, and solution of hard real-world problems in the best tradition of Operations Research and the Management Sciences. In their joint work with Crowder and in subsequent work with others, they showed how to formulate and solve efficiently very large-scale practical 0-1 programs with important applications in industry and transportation. The selection committee cited among his contributions three important and influential papers he produced in the early seventies?two of them with Ralph Gomory?which developed and extended in significant ways the group theoretic approach to integer programming pioneered by Gomory. In particular, he showed how the approach can be extended to the case of mixed integer programs. As an outgrowth of this work, he contributed decisively to the development of what became known as the subadditive approach to integer programming. Still in the seventies, in a seminal paper co-authored with Jack Edmonds, he showed how several basic optimization problems defined on graphs can be solved in polynomial time by reducing them to weighted matching problems. One example is finding minimum T-joins (i.e., edge sets whose only endpoints of odd degree are those in a specified vertex set T). An important special case is the seemingly difficult problem of finding a shortest tour in a graph that traverses every edge at least once, known as the Postman problem. The stark contrast between the polynomial solvability of this problem and the intractability of the traveling salesman problem in which the tour is supposed to traverse vertices rather than edges, helped focus attention on the phenomenon so typical of combinatorial structures: two seemingly very similar problems turn out in reality to be vastly different.