Mathematical Optimization: Past, Present, and Future

Author: Robert Bixby, PhD

I have dedicated my career for nearly the past four decades to developing mathematical optimization software technologies. This has been tremendously rewarding professionally and personally, as I have had the opportunity to be on the frontlines and – along with other key individuals who made seminal contributions – help forge new frontiers and foster the growth, evolution, and improvement of mathematical optimization technologies.

Today, mathematical optimization technologies are used by leading global companies across industries – including aviation, automotive, energy, finance, supply chain, telecommunications, media, and many more – to solve a broad range of complex, real-world problems, make optimal, data-driven decisions, and achieve improved efficiency. But how did mathematical optimization technologies come to have such a profound impact on the world we live in?

In the first of a series of blog posts, I would like to look back at the over-70-year history of mathematical optimization technologies – as I believe that, in the words of Carl Sagan, “You have to know the past to understand the present.” Indeed, I hope that this overview of the history of mathematical optimization technologies will help you better grasp their importance in our present-day world and also envision the possibilities of these technologies in the future.

Mathematical Optimization: The Early Years

Linear Programming (LP) is arguably the key, base methodology in mathematical optimization as we know it today. LP was first introduced by Leonid Kantorovich in 1939 and then independently reintroduced by George Dantzig in 1947. An American mathematical scientist, Dantzig not only invented the simplex algorithm – which to this day remains a primary computational tool in LP and mixed-integer programming (MIP) – but also established LP as an important planning and decision-making tool that could be used for practical applications (rather than merely as a conceptual, qualitative tool used by economists).

Dantzig had the incredible foresight (as computers were not available at that time) of anticipating that LP models could be used to solve large-scale, real-world planning problems and provide answers – which could then be used to make decisions. 

Dantzig reported that the economist Jack Laderman was the first to use the simplex algorithm to solve a non-trivial LP problem. It was a 9-constraint, 77-variable instance of the classical “Stigler Diet” problem – and it reportedly took a whopping 120 man-days to solve! Although the same problem could be solved in a fraction of a second using today’s technologies, this initial success marked a major milestone in the development of mathematical optimization – proving that this approach could be used to compute actual answers to specific real-world problems.

Dantzig was working at the RAND Corporation when, in the late 1940s, the programmer Bill Orchard-Hays was assigned to collaborate with him on developing computer implementations of the simplex algorithm, laying the foundations for the next generation of mathematical optimization technologies.

Integer programming (IP) also had its genesis – at least in a theoretical sense – during this period, spurred by a seminal paper published in 1954 by Dantzig, D. Ray Fulkerson, and Selmer Johnson. At this time, though, MIP was essentially viewed as a fascinating toy, which was fun to play around with, but was not capable of solving real-world business problems. Needless to say, this perception would change dramatically in the years to come.  

Mathematical Optimization Becomes a Commercially Viable Technology

In the early 1960s, mathematical optimization in general, and LP in particular, were still widely seen as theoretical topics that had limited applicability in the real world. At that time, most companies still used manual tools and techniques to address their business problems.

This dynamic changed, however, over the decade due largely to one driving force: the oil industry. In the early 1960s, oil companies began using LP to solve various kinds of problems at their refineries (and, believe it or not, these same problems are still being solved today with many of the same fundamental techniques).

As LP was a critical part of their business, oil companies were the primary funders of research into computational linear programming during the 1960s and 1970s – spurring the development of these mathematical optimization technologies.

However, the scope and scale of the problems that could be addressed with LP and MIP remained limited until the 1970s, when the advent of IBM System/360 computers ushered in a new period of development for mathematical optimization technologies.

These new computers offered expanded capabilities – which meant that not only could robust problems be solved more rapidly and with greater regularity, but also that new ideas and approaches (which would have been unworkable on the previous generation of machines) could now be implemented.

The decade of the 1970s can be viewed as a sort of renaissance for mathematical optimization technologies, when both LP and MIP became seen as commercially viable problem-solving approaches. Interest in mathematical optimization boomed during this period, but significant challenges also emerged – as these technologies were simply not ready for widespread adoption and application in the business world.

In the next blog in this series, I will take you through the next phase in the evolution of mathematical optimization technologies. This was a period of great innovation during which many obstacles were overcome and – with the contributions of trailblazers such as Gurobi Co-Founders Ed Rothberg, Zonghao Gu, and myself – mathematical optimization technologies truly made a quantum leap.