|
| |
 |
|
Dr. Robert E. Bixby. |
|
A noted authority on optimization theory and practice, Bob Bixby has been responsible for some of the discipline's biggest breakthroughs. His research includes solution of large-scale linear programming problems; application of linear programming methods to integer programming; parallel methods for integer and linear programming; and algorithms for combinatorial optimization problems.
"Optimization has become increasingly powerful during the past decade. Today's computers allow optimization alogrithms to solve business problems previously considered impossible. Now, optimization has unlimited potential for increasing profitability and reducing costs. The challenge is to realize that potential, making optimization an indispensible business tool."
Cofounding CPLEX
In 1987, Bixby cofounded CPLEX Optimization, Inc., a software company marketing algorithms for linear and mixed-integer programming. In addition to its primary uses in commercial applications, the CPLEX optimizers are employed by universities throughout the world for
education and research in linear and integer programming. In 1997, CPLEX was sold to ILOG, where Bixby has served in a number of positions. He is currently president of the ILOG Technical Advisory Board.
Revolutionizing crew-and-fleet scheduling
Transportation is among optimization's most successful applications. The airline industry regularly employs linear and integer programming for key operations like crew-and-fleet scheduling. Bixby and the CPLEX team pioneered a crucial component of present-day fleet assignment solutions, developing robust implementations of the dual simplex algorithm. In 1992, Bixby and researchers from Princeton, Rutgers and Cray Research implemented a new hybrid algorithm to solve the linear-programming relaxation of a 13 million-variable crew scheduling model. Total solution time was under five minutes.
Solving the Traveling Salesman Problem
The Traveling Salesman Problem (TSP) has challenged scientists, mathematicians and engineers for decades, serving as an important proving ground for practical advances in integer programming. The problem is to find the shortest possible route between a given set of points (or "cities"), starting at a fixed point and visiting every other point exactly once. When Bixby and his colleagues began working on the problem in 1990, the largest solved "real" instance contained 2,329 cities. In 1992, they increased that number to 3,038. That year, Discover magazine selected their work as one of its top 10 stories in science. Most recently, the team solved a 15,112-city instance to provable optimality. The computation was carried out on a network of 110 processors at Rice University and Princeton Univeristy. Total computer time consumed was 22.6 years.
|
