Ellis L. Johnson

Ellis Lane Johnson (1938–2024) was 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.

In 1988, Johnson was elected a member of the National Academy of Engineering for fundamental contributions to discrete optimization and software design, and its practical applications to distribution and manufacturing systems.

Early life and education Johnson received a B.A. in mathematics at Georgia Tech and earned his Ph.D. in operations research from the University of California at Berkeley in 1965. He was student of George Dantzig.

Career In the 1950s, Johnson served as director of the Operations Research Office of the Johns Hopkins University. Later, after three years at Yale University, Johnson joined the IBM T.J. Watson Research Center in Yorktown Heights, where he founded and managed the Optimization Center from 1982 until 1990, when he was named IBM Fellow. He joined the Georgia Tech faculty in 1994.

Johnson's research interests in logistics included crew scheduling and real-time repair, fleet assignment and routing, distribution planning, network problems, and combinatorial optimization.

Awards and honors Johnson received a number of awards, including the following:

The selection committee cited among Johnson's contribution 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, Johnson showed how the approach can be extended to the case of mixed integer programs. As an outgrowth of this work, Johnson 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, Johnson 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.