Ellis L. Johnson

July 26, 1938

Brief Biography

Ellis L. Johnson is a John von Neumann Theory Prize recipient who has made fundamental contributions to integer programming and combinatorial optimization. Growing up on a farm outside of Athens, Georgia, Johnson followed his older brother’s footsteps and attended the Georgia Institute of Technology. He originally studied aerospace engineering and spent two academic quarters at the National Advisory Committee for Aeronautics. Johnson switched to mathematics and received his Bachelors of Science degree in 1960 before pursuing graduate study at the University of California, Berkeley. Johnson worked under George B. Dantzig and wrote his dissertation on network flows, graphs, and integer programming.

After receiving a PhD in 1965, Johnson worked at Yale University for three years before joining the IBM Thomas J. Watson Research Center in Yorktown Heights. He was offered a position at Stanford University that would reunite him and Dantzig but chose instead to enter a more research driven environment. In 1982, he founded IBM’s Optimization Center. The following year, he, Mandred Padberg, and Harlan Crowder, published a paper on solving large-scale zero-one linear programming in Operations Research. The publication was awarded the Frederick W. Lanchester Prize for its combination of then-recent results in problem processing, constraint generation, and branch-and-bound techniques. By showing that large problems can be solved exactly, their paper greatly expanded the range of integer programming applications.

Johnson worked closely with Jack Edmonds, publishing a series of papers in the 1970s. The pair co-authored a seminal paper that showed how several basic optimization problems defined on graphs can be solved in polynomial time by reducing them to weighted matching problems. In their proof, Edmonds and Johnson demonstrated how two seemingly very similar problems turn out to be vastly different in reality.

In 1985, the Society for Industrial and Applied Mathematics (SIAM), along with the Mathematical Optimization Society, awarded Johnson the George B. Dantzig Prize, recognizing the significant impact his research has had on the field of mathematical optimization. Johnson continued to manage the Optimization Center until 1990, when he was named an IBM Fellow, the highest honor a scientist, engineer, or programmer at IBM can achieve. That year he began teaching at his alma mater, Georgia Tech. There, Johnson co-established and co-directed the university’s Logistics Engineering Center with George Nemhauser. He joined the faculty there full-time in 1994.

Johnson has received a number of other honors in addition to the John von Neumann Theory and George B. Dantzig Prizes. In 2002, his worked with Delta Airlines on qualification training for airplane pilots was named a finalist for that year’s Daniel H. Wagner Prize for Excellence in Operations Research Practice. He is an elected member of the National Academy of Engineering and an inaugural Fellow of the Institute for Operations Research and the Management Sciences. In 2009, he was named a Fellow of SIAM.

Other Biographies

Wikipedia Entry for Ellis L. Johnson

Georgia Tech College of Engineering. H. Milton Steward School of Industrial & Systems Engineering: Ellis Johnson. Accessed May 11, 2015. (link

Georgia Tech College of Engineering. H. Milton Steward School of Industrial & Systems Engineering Items: Ellis Johnson: Deep Roots at Georgia Tech. Published September 7, 2010. Accessed July 1, 2015. (link)


Georgia Institute of Technology, BS 1960

University of California, Berkeley, PhD 1965 (Mathematics Genealogy


Academic Affiliations
Non-Academic Affiliations
  • IBM
  • Delta Airlines

Key Interests in OR/MS

Application Areas

Awards and Honors

Frederick W. Lanchester Prize 1983

SIAM George B. Dantzig Prize 1985

National Academy of Engineering 1988

John von Neumann Theory Prize 2000

Daniel H. Wagner Prize for Excellence in Operations Research Practice 2002

Institute for Operations Research and the Management Sciences Fellow 2002

Society for Industrial and Applied Mathematicians Fellow 2009

Selected Publications

Johnson E. L. (1966) Networks and basic solutions. Operations Research, 14(4): 619-623.

Edmonds J. & Johnson E. L. (1970) Matching: a well-solve class of integer linear programs. Junger M., Reinelt G., & Rinaldi G., eds. in Combinatorial Optimization – Eureka, You Shrink!, 27. Springer: New York.

Edmonds J. & Johnson E. L. (1973) Matching, Euler tours and the Chinese postman. Mathematical Programming, 5(1): 88-124.

Hammer P. L., Johnson E. L., & Peled U. N. (1975) Facet of regular 0-1 polytopes. Mathematical Programming, 8(1): 179-206.

Crowder H., Johnson E. L., & Padberg M. (1983) Solving large-scale zero-one linear programming problems. Operations Research, 31(5): 803-834.

Barnhart C., Hane C. A., Johnson E. L., Marsten R. E., Nemhauser G. L., & Sigismondi G. (1995) The fleet assignment problem: solving a large-scale integer program. Mathematical Programming, 70(1-3): 211-232.

Barnhart C., Boland N. L., Clarke L. W., Johnson E. L., Nemhauser G. L., & Shenoi R. G. (1998) Flight string models for aircraft fleeting and routing. Transportation Science, 32(3): 208-220.

Barnhart C., Johnson E. L., Nemhauser G. L., Savelsbergh M. W., & Vance P. H. (1998) Branch-and-price: column generation for solving huge integer programs. Operations Research, 46(3): 316-329.

Beecham S., Gamble R., Johnson E. L., Searle W. A., & Wyeth-Ayerst J. (2000) Recommendations for the medical management of osteoarthritis of the hip and knee. Arthritis & Rheumatism, 43(9): 1905-1915.

Barnhart C., Cohn A. M., Johnson E. L., Klabjan D., Nemhauser G. L., & Vance P. H. (2003) Airline crew scheduling. Hall R. W., ed. in Handbook of Transportation Science, 516-560. Springer: New York.