Past Awards
The 2010 INFORMS IMPACT PRIZE is awarded to Fred Glover and Solver, developed by Daniel Fylstra, Leon Lasdon, Edwin Straver, Allan Waren, and John Watson of Frontline Systems, Inc.
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 ten 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 over 2000 citations, paving the way for the explosive development of metaheuristic research in the following decades.
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 Searach,” “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.
For his seminal work on metaheuristic algorithms, specifically the development of Scatter Search and Tabu Search, and for his work popularizing these techniques as effective solution methods for previously intractable problems, INFORMS is delighted to award the 2010 Impact Prize to Professor Fred Glover.
__
Arguably, over the last twenty 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. Mr. Flystra, Professor Lasdon, Mr. Straver, Professor Waren and Dr. Watson share the credit for the overwhelming success and impact of Solver.
Solver was developed by Frontline systems, the company founded by Mr. 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 Dr. Watson. This set of algorithms formed the backbone of the optimization engine in all successive versions of Solver products developed at Frontline by Mr. Fylstra and Mr. Straver. The most recent versions of Excel for Windows and Macintosh have added a hybrid Evolutionary algorithm, written by Mr. Fylstra and enhanced by Mr. 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. Thus 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 over 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 OR Applications in 2008, and a 1998 Interfaces article about Solver, “Design and Use of the Microsoft Excel Solver” by Mr. Fylstra, Professor Lasdon, Dr. Watson, and Professor Waren has garnered over 200 citations. Moreover, Premium Solver for Education has been licensed for inclusion in over 35 textbooks and has become a core tool in MBA education.
2004
INFORMS SPECIAL RECOGNITIONS PRIZE
FOR CONTRIBUTIONS TO OPERATIONS RESEARCH
Awarded to
Fred Glover
This prize is awarded to Fred Glover in recognition of the impact of his long list of contributions to the field of operations research. His body of work has been widely adopted in the research community and has seen widespread use in industry. For example, Fred’s work on modeling and solution methodologies in network flow programming has motivated a wealth of research as well as industrial applications in revenue management software for airlines, telecommunication networks, transportation and distribution, supply chain management and logistics, to name a few. Advances in solving integer programming in practice include the early development of primal-dual approaches and the general application of heuristics based on surrogate constraint relaxations. Fred’s tabu search methodology has seen extensive use in the research community, where it has been recognized as a powerful tool for tackling a broad range of hard problems. Also, developers have embedded tabu search in commercial optimization software, enabling practitioners to exploit the effectiveness of this methodology when applied to a wide variety of real-world problems.
There are several important themes in Fred’s body of work that make it exceptional. He has developed new methodologies through synthesis and problem-driven approaches. He has successfully transferred technologies from one area of knowledge to another. And, his work has been seminal to researchers and applicable to practitioners.
Fred’s accomplishments were the inspiration for the newly created INFORMS Impact Prize. The INFORMS Professional Recognition committee and the Denver Meeting Organizing Committee proudly present this special recognition prize to Fred Glover.
The 1998 John von Neumann Theory Prize was awarded to Fred W. Glover, for his fundamental contributions to integer programming, networks, and combinatorial optimization.
His contributions to integer programming began with his dissertation at Carnegie-Mellon University in 1965, where he introduced surrogate constraints, and an improved data structure for implicit enumeration. In 1970, the surrogate constraint ideas led him to a family of facet generation algorithms for Gomory's group problem, now known as lifting procedures. His research in the early to mid 1970's led to the polyhedral annexation framework, fundamental in disjunctive programming. As with surrogates, lifting procedures, and convexity cuts, this framework became an important part of integer programming, withstanding the test of time for more than two decades in its impact on our ability to solve hard problems.
Starting in the 1970's, Fred and Darwin Klingman revolutionized the field of network optimization. They developed new data structures, algorithms, and computer implementations which vastly improved the speed and size capabilities of network codes. They specialized their primal, dual, and primal-dual procedures to important categories of network problems like transportation and assignment. In the best traditions of OR/MS, they pioneered many important applications, and played the major role in disseminating this technology to practitioners. In the 1980's they introduced the family of modeling concepts known as Netforms, and later published a seminal book on that topic. This approach includes elements of what we now call reformulation in optimization modeling. Fred has also provided results regarding reformulation of LP's as networks, and binary IP's as LP's.
Starting in the late 1970s, Fred developed the framework of the metaheuristic called Tabu Search, which has had an enormous impact on our abilities to solve hard combinatorial problems. Fred coined both "Metaheuristic" and "Tabu Search" in the same 1986 article that has spawned hundreds of Tabu-search-related applications throughout the world. In many areas, ranging from scheduling to financial planning to training neural networks, Tabu Search has solved or quickly obtained a high-quality solution for problems that were too difficult to tackle by other methods.
The success of Tabu search relative to competing techniques like genetic algorithms and simulated annealing continues to grow.
Few researchers have provided theoretical frameworks which have had so great an impact, both on the development of further theory, and on the practice of OR/MS.
For the remarkable variety, high caliber, and enormous impact of his lifetime's work, we award the John von Neumann Theory Prize to Fred W. Glover.