Mathematical Optimization: Past, Present, and Future (Part 2)

Author: Robert Bixby, PhD

Date: 3/9/2020

Mathematical optimization technologies such as linear programming (LP) and mixed-integer programming (MIP) are utilized today by thousands of major global corporations across numerous industries to solve their complex, real-world problems and make optimal, data-driven business decisions.

But the transformation of LP and MIP from theorical to practical (and very powerful) problem-solving tools did not happen overnight. Indeed, these mathematical optimization technologies have undergone a slow, steady, and significant evolution since they were first introduced around 70 years ago.

In the first blog in this series, I chronicled the early years in the history of mathematical optimization – from the initial introduction of LP and MIP in the 1940s and 1950s respectively, to their emergence (propelled by advancements in computing capabilities) as commercially viable technologies in a handful of industries in the 1970s. And that’s where we will continue the story of the development of these mathematical optimization technologies in this blog.

Hitting a Roadblock

Although the 1970s were a time of great promise and potential (as interest in mathematical optimization, particularly in the academic world, blossomed during this period), actual adoption and application of mathematical optimization technologies in the business world was quite limited.

During that period, LP applications were used by a select group of companies in certain industries (most notably oil companies, who were the chief funders of research into computational linear programming at that time) to solve relatively small, mostly planning-oriented problems.

Widespread adoption of LP and MIP in the business world, however, was simply not possible in the 1970s and 1980s due to the complexity of building a mathematical optimization application (which, back then, more often than not literally took years!), the difficulty in maintaining such an application, and – most importantly – the very limited capability to solve the resulting models.

Indeed, at that time, building and maintaining mathematical optimization applications was a time-consuming and labor-intensive endeavor – requiring expertise across an array of areas including data collection, operations research, computer programming, and business analysis.

As a result of these issues, a sense of disillusionment (particularly about using MIP as a practical, problem-solving tool) set in and persisted for many years – and the development of mathematical optimization technologies hit a significant roadblock. Change, however, was on the horizon.

A Time of Transformation

The early 1990s marked a period of phenomenal growth and profound transformation for mathematical optimization technologies.

Fueled by the groundbreaking research of computer scientist Narendra Karmarkar and others (who developed special purpose algorithms to solve several categories of large-scale, real-world problems), LP applications underwent a metamorphosis and became increasingly powerful, practical, and popular – particularly in the airlines industry.

The commercial codes for solving MIP applications – which up until then had been widely viewed as a fascinating modeling “toy” with little applicability in addressing real-world problems – saw dramatic improvements in the 1990s.

During that time, MIP capabilities steadily improved, experiencing two major bumps in performance: 1) In 1994, because of the maturity of simplex algorithms as they are used in MIP and 2) In 1998, through a mining of the theoretical backlog that had been built up over 30 years – which I will discuss in greater detail in the next section of this article.

The tides were turning: LP – the foundation of mathematical optimization as we know it today – was being overtaken by MIP as the predominant problem-solving approach.

Over the course of the 1990s, MIP would come to revolutionize the applicability of mathematical optimization technologies, enhancing their impact and expanding their reach into a broad range of industries.

Big Breakthroughs

It was around this time that I entered the mathematical optimization software field (and, thus, this story).

Actually, I began working on mathematical optimization in the early 1980s – first on theoretical, academic-oriented research and then on designing a general-purpose LP code. This code was tested on real-world models by Tom Baker, the founder of Chesapeake Decision Sciences – and it was this connection to real-world models drove the early development and improvement of the code and led to the establishment of CPLEX Optimization.

In 1987, I co-founded CPLEX Optimization, and we released our first product, an LP code, in 1988.

Looking back, I can honestly say that this period – when I got into the mathematical optimization software business – was truly one of the most exciting periods of my professional life.

And it was truly a watershed moment for mathematical optimization technologies: Karmarkar had just published his groundbreaking paper on interior-point algorithms and there was a growing conviction that mathematical optimization algorithms could be used to solve complex, real-world business problems. This conviction – accompanied by the significant improvements in the classical simplex algorithm (which until today remains the primary computational tool in MIP) – injected a huge amount of enthusiasm into the field.

The improvements were absolutely jaw-dropping. Between 1988 and 2004, LP algorithms – which many had previously thought had progressed as far as they could go – got faster by a factor of five million times!

In the mid-1990s, as I continued with my work designing code at CPLEX Optimization, I had a significant revelation. I realized that what academics conducting ongoing research into integer programming needed was an LP code that could be embedded as a “black-box” solver – which would enable programmers to define and change the parameters of their problems and solve those problems in an efficient manner. This realization led to the creation of the callable library design of CPLEX – an object-oriented structure that enabled users to build applications easily around it. This design turned out to be exactly what business applications needed.

The introduction of this callable library approach was a major development, and ultimately became the model for essentially all future codes in this domain.

Another major development occurred in 1998, when Ed Rothberg and Zonghao Gu (who had recently joined the team at CPLEX Optimization) spurred the most significant performance improvement ever in the development of MIP technologies – which came with the release of CPLEX Version 6.5 that year. In that release, Ed and Gu mined the theoretical backlog and implemented a huge number of ideas – which were inspired by the seminal computational and theoretical research that had been done over the preceding 30 years (but wasn’t being used in commercial codes).

CPLEX Version 6.5 – which cleverly combined a wide spectrum of theoretical ideas developed over the past 30 years, numerous new ideas introduced by Ed and Gu,  and combined these ideas with a genius for software engineering – led to a speedup exceeding a factor of 10.0 and the emergence of a new generation of general-purpose MIP codes that could be used out-of-the-box to solve a whole host of real-world problems (simply not possible prior to that time).

In one fell swoop, our team at CPLEX had changed the game. We revolutionized the mathematical optimization software industry by introducing an out-of-the-box solver that – without any customization of code – can be used in an essentially unlimited breadth of applications to solve a whole host of real-life business problems.

In 2008, Ed, Gu, and I co-founded Gurobi Optimization with the aim of building the world’s most powerful mathematical optimization solver – and that is exactly what we did.

Since its first release in 2009, the Gurobi Optimizer has been constantly setting new standards in terms of solver performance (by achieving an average 60% yearly improvement in speed) and applicability (by expanding its use to over 2,400 companies in more than 40 different industries). Indeed, the performance of our solver just keeps getting better and its presence in various business areas just keeps getting bigger.

Generally speaking, mathematical optimization has firmly established itself as a powerful problem-solving approach in today’s business world. It is used by an ever-increasing number of companies to tackle their complex, real-world problems and make better decisions.

But this is not the end of the story of mathematical optimization technologies – in fact, it is only the beginning of a new chapter. Indeed, with the recent improvements in data availability and quality and the advent of cutting-edge IoT and AI technologies, the use of mathematical optimization is being expanded to new applications. I will explore this topic in the next blog in this series.