INFORMS News: Glover, Solver win Impact Prize
Prize Committee members Geert-Jan Houtum (far left) and Srinivas Bollapragada (third from left) and INFORMS President Susan Albin (far right) congratulate Impact Prize winners Fred Glover of OptTek Systems (second from left) and Dan Fylstra of Frontline (sixth from left) and the rest of the Solver team.
The 2010 INFORMS Impact Prize was awarded to Fred Glover for his seminal work on metaheuristic algorithms, and to Solver, developed by Daniel Fylstra, Leon Lasdon, Edwin Straver, Allan Waren and John Watson of Frontline Systems, Inc.
The INFORMS Impact Prize, awarded once every two years, is intended to recognize contributions that have had a broad impact on the field. The contribution could be an idea or technique that is widely used, or it could be someone who played a major role in bringing significant methodology into widespread use (e.g. by playing a major role in the design of a software package that is now widely used, or through extensive writings and lectures aimed at practitioners).
Fred Glover helped pioneer the field of metaheuristics (which he himself named) with his introduction of Scatter Search in his 1977 Decision Sciences paper, “Heuristics for Integer Programming Using Surrogate Constraints.” Over the next 10 years he continued his work in this nascent field, ultimately formalizing his revolutionary Tabu Search algorithm in his 1987 Computers and Operations Research paper, “Future Paths for Integer Programming and Links to Artificial Intelligence.” These two papers alone garnered more than 2,000 citations.
Since that time scores of other researchers have taken the original ideas of Professor Glover and used them to develop novel metaheuristic algorithms, sometimes by directly hybridizing elements of Scatter Search and Tabu Search. This academic legacy spreads across the decades and around the globe: Professor Glover delivered the keynote address at the inaugural Metaheuristics International Conference (MIC) in 1995; MIC IX will be held in Italy next year. One of the most dramatic testimonials to Professor Glover’s contribution to operations research is the fact that “Scatter Search,” “Tabu Search” and “Metahueristic” have become common keywords in the academic literature.
Even with this vast growth in the field of metaheuristics, Scatter Search and Tabu Search have remained two of the most prominent, most successful and most widely applied metaheuristic algorithms. Their impact can be seen in almost any field which features extremely difficult problems of a combinatorial nature, including knapsack problems, telecommunications, network design, scheduling, financial planning, DNA sequencing, logistics and computational biology. Despite the fact that these problems typically defy standard exact solution methods, Professor Glover’s work has shown that optimal solutions can often be found relatively quickly through application of intelligent search methods.
Professor Glover’s contributions to the popularization of metaheuristics includes not only his original research, but also through the publication of a textbook, the founding of the Journal of Heuristics and his role in development of the OptQuest software package by OptTek Systems, a company he co-founded in 1992. OptQuest continues to enjoy significant popularity worldwide, as do many other commercial optimization packages containing Tabu Search and Scatter Search algorithms, such as CPLEX.
Arguably, over the last 20 years no single tool (or family of tools) has done more to bring operations research into the hands of students, researchers and practitioners than Solver. Flystra, Lasdon, Straver, Waren and Watson share the credit for the overwhelming success and impact of Solver.
Solver was developed by Frontline systems, the company founded by Fylstra, using the GRG2 algorithms and code developed by Professors Lasdon and Waren. This code enabled Solver to accurately solve both linear and nonlinear models. These capabilities were later augmented by a Simplex method and Branch and Bound Algorithm for linear and mixed integer programs, implemented by Watson. This set of algorithms formed the backbone of the optimization engine in all successive versions of Solver products developed at Frontline by Fylstra and Straver. The most recent versions of Excel for Windows and Macintosh have added a hybrid Evolutionary algorithm, written by Fylstra and enhanced by Straver, which uses genetic algorithms, the GRG method and the Simplex method in combination on arbitrary Excel models.
Solver’s success began with Frontline’s victory in a worldwide competition to supply a Solver for Microsoft Excel 3.0; this was quickly followed by contracts to install Solver in Borland’s Quattro Pro in 1992 and Lotus 1-2-3 in 1996. By 1996 the vast majority of spreadsheet optimization was executed using Solver. Since that time Solver has been included in every copy of Microsoft Excel, and currently enjoys an installed base of approximately a half a billion users. In addition, advanced Solver tools have been licensed to more than 5,000 companies in fields such as aerospace, automotive, banking, chemical, consumer goods, defense, financial services, health care and pharmaceuticals, oil and gas, mining, utilities and many types of manufacturing.
These successes have also made their way into the academic literature and education: A special issue of Interfaces was devoted to “Spreadsheet O.R. Applications” in 2008, and a 1998 Interfaces article about Solver, “Design and Use of the Microsoft Excel Solver” by Fylstra, Lasdon, Watson and Waren has garnered more than 200 citations.
