Ellis L. Johnson
Encyclopedia
Ellis L. Johnson is the Coca-Cola Chaired Professor in the H. Milton Stewart School of Industrial and Systems Engineering
at Georgia Institute of Technology
in Atlanta, Georgia
.
from the University of California at Berkeley in 1965.
, 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 Corporate Fellow
. In 1980-1981, Johnson visited the University of Bonn
, Germany
, as recipient of the Humboldt Senior Scientist Award.
From 1990 to 1995, Johnson began teaching and conducting research at Georgia Tech, where he co-founded and co-directed the Logistics Engineering Center with Professor George Nemhauser. He joined the Georgia Tech faculty in 1995.
Johnson's research interests in logistics include crew scheduling and real-time repair, fleet assignment and routing, distribution planning, network problems, and combinatorial optimization.
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 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.
H. Milton Stewart School of Industrial and Systems Engineering
The H. Milton Stewart School of Industrial and Systems Engineering is a department in the Georgia Institute of Technology's College of Engineering dedicated to education and research in industrial engineering. The school is named after H. Milton Stewart, a local philanthropist and successful...
at Georgia Institute of Technology
Georgia Institute of Technology
The Georgia Institute of Technology is a public research university in Atlanta, Georgia, in the United States...
in Atlanta, Georgia
Georgia (U.S. state)
Georgia is a state located in the southeastern United States. It was established in 1732, the last of the original Thirteen Colonies. The state is named after King George II of Great Britain. Georgia was the fourth state to ratify the United States Constitution, on January 2, 1788...
.
Early life and education
Johnson received a B.A. in mathematics at Georgia Tech and earned his Ph.D. in operations researchOperations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
from the University of California at Berkeley in 1965.
Career
After several years at Yale UniversityYale University
Yale University is a private, Ivy League university located in New Haven, Connecticut, United States. Founded in 1701 in the Colony of Connecticut, the university is the third-oldest institution of higher education in the United States...
, 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 Corporate Fellow
IBM Fellow
An IBM Fellow is an appointed position at IBM made by IBM’s CEO. Typically only 4 to 9 IBM Fellows are appointed each year, at the annual Corporate Technical Recognition Event in May or June. It is the highest honor a scientist, engineer, or programmer at IBM can achieve.The IBM Fellows program...
. In 1980-1981, Johnson visited the University of Bonn
University of Bonn
The University of Bonn is a public research university located in Bonn, Germany. Founded in its present form in 1818, as the linear successor of earlier academic institutions, the University of Bonn is today one of the leading universities in Germany. The University of Bonn offers a large number...
, Germany
Germany
Germany , officially the Federal Republic of Germany , is a federal parliamentary republic in Europe. The country consists of 16 states while the capital and largest city is Berlin. Germany covers an area of 357,021 km2 and has a largely temperate seasonal climate...
, as recipient of the Humboldt Senior Scientist Award.
From 1990 to 1995, Johnson began teaching and conducting research at Georgia Tech, where he co-founded and co-directed the Logistics Engineering Center with Professor George Nemhauser. He joined the Georgia Tech faculty in 1995.
Johnson's research interests in logistics include crew scheduling and real-time repair, fleet assignment and routing, distribution planning, network problems, and combinatorial optimization.
Awards and honors
Johnson has received a number of awards, including the following:- 2009 Fellow, Society for Industrial and Applied MathematicsSociety for Industrial and Applied MathematicsThe Society for Industrial and Applied Mathematics was founded by a small group of mathematicians from academia and industry who met in Philadelphia in 1951 to start an organization whose members would meet periodically to exchange ideas about the uses of mathematics in industry. This meeting led...
- 2002 Fellow, INFORMS
- 2000 John von Neumann Theory PrizeJohn von Neumann Theory PrizeThe John von Neumann Theory Prize of the Institute for Operations Research and the Management Sciencesis awarded annually to an individual who has made fundamental and sustained contributions to theory in operations research and the management sciences.The Prize named after mathematician John von...
, INFORMS - 1990 IBM Fellow
- 1988 National Academy of Engineers
- 1985 George B. Dantzig Prize for his research in mathematical programming
- 1983 Lanchester Prize for his paper with Crowder and Padberg
- 1980 Senior Scientist Award, Alexander von Humboldt FoundationAlexander von Humboldt FoundationThe Alexander von Humboldt Foundation is a foundation set-up by the government of the Federal Republic and funded by the German Foreign Office, the Ministry of Education and Research, the Ministry of Economic Cooperation and Development and others for the promotion of international co-operation...
John von Neumann Theory Prize
Johnson received the John von Neumann Theory PrizeJohn von Neumann Theory Prize
The John von Neumann Theory Prize of the Institute for Operations Research and the Management Sciencesis awarded annually to an individual who has made fundamental and sustained contributions to theory in operations research and the management sciences.The Prize named after mathematician John von...
jointly with Manfred W. Padberg in recognition of his fundamental contributions to integer programming
Integer programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming.Integer programming is NP-hard...
and combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
. 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 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
Jack Edmonds
Jack R. Edmonds is a mathematician, regarded as one of the most important contributors to the field of combinatorial optimization...
, 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.