Building a chemical plant. Developing an airline route. Modeling the shapes of proteins.

Each of these actions requires optimization algorithms – the combination of math and theory translated into code that ultimately finds the best way to perform an action. And while engineers often develop algorithms for specific uses, professors in Northwestern Engineering’s Department of Industrial Engineering and Management Sciences (IEMS) have the distinct accomplishment of having developed three optimization algorithms that are widely used across industries and scientific disciplines.

L-BFGS and KNITRO, developed by Professor Jorge Nocedal, and Ipopt, developed by Professor Andreas Wächter, have been used in everything from designing computer chips to modeling pandemics to understanding the effects of climate change on arctic ice.

“With great effort and skill, they have created and implemented these algorithms in unrivaled software, which has both stood the test of time and continues to improve,” said David Morton, David A. and Karen Richards Sachs Professor of Industrial Engineering and Management Sciences professor and chair of IEMS. “The impact of their software is hard to overstate, as it facilitates advances by practitioners and researchers in a breathtaking array of fields.”

Optimizing with L-BFGS and KNITRO

Optimization algorithms work by taking a problem – the best airline route from Chicago to Atlanta, for example – and considering variables, like air traffic and wind, before presenting the optimal solution.

Nocedal developed the algorithm L-BFGS after realizing that an existing optimization algorithm, called BFGS, could not be applied to problems with a large number of variables. He tried to solve this throughout graduate school and only succeeded after becoming a faculty member and realizing that the algorithm could not retain everything it learned, since that would exceed the capacity of every computer. Instead, it needed to retain only a limited amount of relevant information using a term called limited memory, the “L” in L-BFGS.

“My modification of the algorithm allowed it to solve problems with millions of variables,” said Nocedal, Walter P. Murphy Professor of Industrial Engineering and Management Sciences and (by courtesy) professor of engineering sciences and applied mathematics. The algorithm was simple and became open source. But this was pre-big data, and its usefulness wasn’t readily apparent. “I published it and nobody paid any attention,” he said. But he kept refining it based on his increasingly deeper understanding of the problem.

Fast forward to the 1990s, and the algorithm became popular with weather forecasters. When machine learning research took off twenty years later, the use of the algorithm accelerated.

Now, most everyone in the field knows the term L-BFGS. Recently, the algorithm was used as part of the Google DeepMind project to help determine the 3D shapes of proteins – a breakthrough in the field that could lead to major advances in biology and drug discovery. It was also recently used by the White House to model COVID-19 early in the pandemic. Because the algorithm is open source, Nocedal does not know everywhere it has been used.

“As an engineer, you just explore,” he said. “You don’t know when something is going to end up being successful or not. I knew when I developed it that there must be some use for it, and sometimes you create an algorithm that is ahead of its time.”

In the 1990s, Nocedal also began developing another nonlinear optimization algorithm called KNITRO. Unlike L-BFGS, this algorithm took years to develop and could solve more complicated problems with more restrictions. (Nocedal explains the difference in complexity between the two algorithms this way: If L-BFGS is a bicycle, then KNITRO is a modern car.) He and his graduate students ultimately commercialized the algorithm to develop it into software. Now, KNITRO is widely used in the energy, finance, economics, and robotics sectors.

“It has found its way into all these different areas of applications,” he said.

Enabling new technologies with Ipopt

KNITRO has a companion in Ipopt, the nonlinear optimization algorithm developed by Wächter using a different algorithm than KNITRO. Wächter, professor of industrial engineering and management sciences, began developing the algorithm in the late 1990s as a chemical engineering graduate student. He and his adviser were looking for a way to optimize reactors so they “don’t blow up the chemical plant.”

He continued working on Ipopt at IBM, where it became an open-source project. For years, he used math, theory, and computer programming to test and refine Ipopt. When it was translated into the C++ programming language, it became known as the go-to open-source optimization algorithm.

Wächter regularly hears about instances where it has been used – running trains, optimizing power grids, building chemical plants, developing airline routes, enhancing medical imaging, and even creating models of black holes.

“I have a friend who told me even a Formula 1 team is using my code,” he said. “I just feel extremely lucky that I had the opportunity to spend the time to make Ipopt as robust as it is and that it had such an impact. We’re developing enabling technologies. Not only are our algorithms used in all these different industries, they also make it possible for scientists and engineers to do new research.”

Both Nocedal and Wächter continue to develop new algorithms – the future, Nocedal said, lies in algorithms that can deal with uncertainty. One rich source of new problems is in machine learning, where the optimization must be performed in the presence of uncertainty in the data. Given the explosive growth of artificial intelligence, the demand for more capable optimization algorithms will only increase with time.