Robert Bixby

Professor of Computational and Applied Mathematics, Rice University


Robert Bixby earned his B.S. in Industrial Engineering from the University of California, Berkeley (1968) and his M.S. and Ph.D. in Operations Research from Cornell University (1971 and 1972). He began his career as a mathematics instructor at Cornell in 1971, then joined the faculty at the University of Kentucky as assistant professor of mathematics. In 1974, he spent a year as visiting assistant professor at the University of Wisconsin-Madison, then returned to Kentucky, where he was promoted to associate professor with tenure in 1976. Bixby spent the next year as visiting associate professor at Cornell before moving to Northwestern University in 1977. In 1983, Bixby joined the Rice University faculty as professor of computational and applied mathematics, with periodic leaves to teach at major research institutes and universities in Bonn, Berlin, and Augsburg, West Germany.

Bixby's research interests include the solution of large-scale linear programming problems, the application of linear programming methods to integer programming, parallel methods for integer and linear programming, and algorithms for combinatorial optimization problems. "I'm simply fascinated by being able to solve numerically intensive, real-world problems, especially ones that were previously unsolved," he says. "I find great satisfaction in looking at large volumes of numerical data and deducing new, generally applicable solution strategies and algorithms."

In one real-world application, Bixby and researchers from Princeton and Rutgers implemented a new algorithm for the solution of the linear programming relaxation of a 13-million-variable airline crew scheduling model. Total solution time for this model was less than three minutes on a four-processor Silicon Graphics Power Challenge workstation.

Bixby and colleagues have also broken the record for the Traveling Salesman Problem (TSP) by finding provably optimal solutions for specific 3,038-, 4,461- and 7,397-city instances, and are currently working on the solution for a 13,509-city instance. The TSP involves finding an optimal path for a salesman to take when traveling through a specified number of cities, and has applications in science and engineering, including the manufacture of circuit boards.

Of such problem-solving breakthroughs, Bixby explains, "In linear programming alone, the last 10 years have seen an estimated six orders of magnitude speed improvement. When you add the fact that the basic integer programming algorithms all use linear programming in such a way that the overall search can be parallelized, we're looking at at least eight orders of magnitude improvement--the difference in speed between a year and a fraction of a second! It's pretty clear that we will be learning a lot about how these large-scale problems behave, as we have with the TSP."

In addition to his academic work, Bixby co-founded a software company in 1988 called CPLEX Optimization, Inc. that markets algorithms for linear and mixed-integer programming. Apart from its primary uses in commercial applications like the airline crew scheduling model, the CPLEX optimizer is employed by universities throughout the world in education and research in integer and linear programming.

Affiliated with many scientific organizations, committees, and publications throughout his career, Bixby is currently a member of the Mathematical Programming Society, the Operations Research Society of America, the Society for Industrial and Applied Mathematics (SIAM), and the Association for Computing Machinery (ACM), and is chairman of the Mathematical Programming Society Publications Committee. He has published more than 60 papers and technical reports.

Also a CRPC Technical Steering Committee member, Bixby says, "For me, the CRPC has been important in a number of ways, not only by making funds and resources available for our work, but by creating an atmosphere in which the computational sciences are valued and supported in a fundamental way."

Table of Contents