Five Ideas I'll use in my optimization class after listening to Gurobi's Tobias Achterberg

I enjoy the ‘Subject to’ (s.t.) podcast. I like learning about the professors and experts in OR. It helps that I know a few and am just one degree of separation from most others.

This week, I listened to the interview with Tobias Achterberg. I should know him since we were at ILOG and IBM together. But we didn’t work together.

He was part of the CPLEX solver team at ILOG and IBM. He is the creator of SCIP, a great open-source solver. And he’s now VP of R&D for Gurobi. So, he has a front-row seat on making mixed integer programming (MIPs) solvers faster.

The podcast came at the right time. I’m just starting to teach optimization to another great class of data scientists in Northwestern’s Masters in Machine Learning and Data Science program.

I’m always looking for new stories, ideas, and lessons to share. Here are the five I took from this interview.

One (the obvious): MIPs are such a great general-purpose tool.

I love to stress this to people new to optimization. I highlight two points. First, if you can formulate a real-world problem as a MIP, you have a way to solve it. Second, there are probably more problems you can model as a MIP than you’d think. This is an underutilized technology.

Two (ChatGPT): Will ChatGPT (and other LLMs) help make optimization models more accessible?

The big barrier to widespread use is the difficulty in building MIP models of business problems. The tools are getting better, but it is still complex. An open question is if we can use ChatGPT to make modeling and optimization easier. I would love to explore this more.

Three (why commercial): Open source solvers can’t compete with commercial solvers.

People who know machine learning expect optimization to have great open-source solvers. However, commercial solvers are much better than open-source.

Tobias gave some reasons: Gurobi has many more resources— they have many more people, 192 machines running 24x7 performing tests, and 6,00 benchmark models (I would have thought more). Many of the improvements come from detailed software engineering and doing tests to see what works best. Since academics can’t write papers on these improvements, they are less inclined to do this for open-source solvers.

Four (tuning?): Don’t try to speed up your models by tuning the solver.

My friend Pete Cacioppi has been telling me this forever.

MIPs are always slower than you want. You can change the default parameters to see if you can get a speed-up. I always wanted to try this, but Pete refused.

Tobias gave some reasons why Pete was right and I was wrong. Gurobi uses those 192 machines to test the best default settings— they’ve tried millions (more?) combinations of settings. Is my random choice going to be better? Tobias said sometimes the opposite of what they thought works better in practice. If their intuition fails, how can mine be better? Finally, they are constantly testing new ways to create defaults. For example, they’ve built machine learning models to predict the best settings for different model types.

Five (be grateful): These solvers are engineering wonders. Don’t teach the algorithm.

I was once told that the speed of solvers depends on 100s of small improvements. It is impressive that these solver teams increase the speed by 15% to 40% every year for decades.

When listening to Tobias, they seem to leave no leaf unturned. They look for improvements in default parameters, pre-solve, the core engine, and parallel cores, to name a few. I would guess that they also keep a close eye on disruptive ideas or technologies— academic research, quantum computing, and deep learning.

Because the algorithms are so well-engineered, it seems pointless for most people to know much about them. I think most optimization courses should focus on modeling problems. In our optimization course, we spend about four minutes explaining the concept of Simplex, about nine minutes talking about primal and dual, and about thirty minutes on branch and bound. We cover Simplex because other professors will talk about it. We also cover the primal and dual because others talk about it, and it occasionally comes up in log files. Branch and Bound gets thirty minutes because I think it provides some intuition on why MIPs are so slow (you are solving lots of LPs!).

---