Past Awards
The 2007 Lanchester Prize of INFORMS is awarded to David L. Applegate, Robert E. Bixby, Vašek Chvátal, and William J. Cook for their book, The Traveling Salesman Problem: A Computational Study, Princeton University Press, Princeton, New Jersey, 2006.
The traveling salesman problem (TSP) is to find the least expensive way to visit a collection of cities and return to the beginning. This simply stated problem combined with its seeming intractable solution has, over the past century, made the TSP the defining problem for computational optimization and even for computational science in general. While the TSP is now well-known in popular culture as well as in OR/MS, its history, the applications beyond the routing of itinerant vendors, and the variety of solution methodologies had not been assembled until now. Applegate, Bixby, Chvátal, and Cook’s book, The Traveling Salesman Problem: A Computational Study combines the history, the applications and the most advanced methods for solution in a definitive treatment of this definitive problem.
In presenting solution methods, the book describes in clear and instructive terms how to build efficient procedures for the basic optimization mechanisms of linear programming, branch-and-bound, cutting planes, and iterative improvement. The authors then show how to combine these myriad processes into a powerful optimization machine capable of solving to optimality problems with tens of thousands of cities. They also provide challenges for improvements and sources for new directions to the TSP and other large combinatorial problems. To allow future researchers the chance to examine and build on their work directly, the authors have made publicly available their entire computer code.
Besides providing a comprehensive view of all that is involved in solving the TSP, the book’s flowing narrative blends the pieces together in a steady progression that captivates the reader. In describing the latest applications, such as gene sequencing, data mining, and X-ray crystallography, the book also shows the reach of OR/MS into multiple new domains. In all respects, The Traveling Salesman Problem: A Computational Study represents the best of OR/MS history, present, and future.
Award presented by John Birge, Chair, and Brenda Dietrich, President, November 4, 2007.
Bob Bixby and Janet Lowe
In 1987, Bob Bixby created a code for solving linear programming problems, using the relatively novel C programming language. Recognizing that there may be commercial applications for the code, he approached Janet Lowe to put together a business to market the code. From this partnership, CPLEX has emerged as a tool used by thousands of professionals in industry and academia.
The success of CPLEX is due to a combination of technical and marketing contributions. Bob created the initial version of CPLEX as a callable library that would allow other developers to embed CPLEX in applications. Bob then drew on his own research and an extensive literature to ensure that CPLEX contained the most advanced algorithms that had a demonstrable contribution to the speed, accuracy and stability of the software. He discovered how to implement stable versions of steepest-edge pricing for the dual simplex method, and developed new techniques for computing initial bases for the simplex method. Just as important, he built up a first-rate team of developers to bring the latest research into the code.
A good product will not be widely used without a successful business plan. Janet Lowe surveyed the market and developed a strategy to market CPLEX. There were three dimensions to her plan. The first was to create an academic sales and marketing program that provided commercial grade software at reduced prices to academics for research purposes. A measure of the success of CPLEX in academia is that at any conference where papers are presented, 95 percent of the papers that mention a solver mention CPLEX.
The second key aspect of the business plan was the creation of an independent software vendor channel that allowed CPLEX partners to embed CPLEX in applications and pay a royalty to the company every time they sold their application. As a result of this model, CPLEX has become the standard solver used in supply-chain applications. The third aspect of the business plan was the creation of a telesales model for the sales and support of the product.
There are thousands of CPLEX licenses in use. Industry leaders including SAP, Oracle, i2, JD Edwards, and Manugistics depend on CPLEX to provide fast and reliable answers to large-scale supply chain planning problems. Most of the major airlines including United, American, Delta, Continental, Northwest, and Southwest depend on CPLEX to schedule their crews and solve their fleet assignment problems. CPLEX is also packaged with academic editions of popular modeling languages such as AMPL, MPL, OPL Studio, and GAMS.
For the creation and widespread dissemination of CPLEX, the Informs Impact Prize Committee is pleased to recognize Robert Bixby and Janet Lowe with the 2004 INFORMS Impact Prize.
–
Paul Green is often called “the father of conjoint analysis,” a powerful statistical technique widely used in market research to help the developers of products and services determine which features are most important to the marketplace. He has used conjoint analysis to help Marriott create the original concept for its Courtyard hotels for business travelers, as well as for AT&T’s first cellular phone system, the E-Z Pass automated toll collection system, and the design and pricing for IBM’s Risc 6000 and AS400 computer systems. He and his colleagues have applied conjoint analysis to financial services, industrial and consumer goods, health care and pharmaceuticals, business strategy and transportation.
In addition to his own projects, he has helped to disseminate the theory and application of conjoint analysis through numerous books and papers. The technique is widely taught in market research courses around the country, and is now standard material in textbooks on market research. It is also imbedded in commercial software packages.
From its roots in market research, the technique has emerged as a powerful analysis tool in a variety of problem settings in medical research, psychiatry, public policy, and industrial engineering, among others.
Generations of students have learned and applied conjoint analysis in their work. For this reason, the INFORMS Impact Prize Committee is pleased to recognize a lifetime of contributions by giving the 2004 INFORMS Impact Prize to Paul E. Green.