Has Optimization Hit a Tipping Point?

Ehsan Khodabandeh, who co-teaches Optimization with me, told me (in a nice way) that I might be wrong and my information outdated. I think he's right.

Ehsan and I co-teach an optimization class for Northwestern’s MSiA program.

I was refreshing the slides for our introduction to Integer Programming class. It had the standard advice I thought was always true: avoid using integer variables for things like production quantities. Instead, save them for the binary variables that are part of every model.

In his friendly way, Ehsan told me this was wrong. He said, “I think this is outdated, and I honestly wouldn’t give that as blanket advice now.”

I replied, “Really? No way! Why not just let the quantity be 158.6? Run time will be too long if you make that integer? What are you suggesting?”

He replied, “From the models I’ve built, what I’ve read on OR Stack Exchange, and what I’ve learned from Gurobi’s technical team, this isn’t good blanket advice anymore. I trust Gurobi more than myself.”

He said, “What I do now is set the variables to integer if I’d rather they be integers. I test that model against the relaxed model. If it runs fast enough, I’m done. This has worked for me quite a few times. I let Gurobi handle the hard stuff.”

"I’d go further. In the past, I was cautious not to ever have any quadratic terms in my models. And if I had to multiply two binary variables or a binary and continuous variable, I linearized them without hesitation. But now, even for that, I first check if Gurobi can handle the quadratic terms and how the performance is compared against the linearized version of the model. So far, I've been pleasantly surprised. The quadratic ran faster than the linearized model. The team at Gurobi wasn’t surprised because they use different algorithms."

He continued, “Don't get me wrong. If I don't have access to a powerful commercial solver (like Gurobi, CPLEX, XPRESS) and I need to use an open-source solver, the old blanket advice still applies.”

Ehsan’s comments made me think about something Filippo Focacci from DecisionBrain said about CPLEX. He said that he no longer worries about solver speed for many problems.

Ehsan’s advice is not standard. What is happening?

The answer might come from the two things I learned from Azeem Azhar and his book Exponential Age.

One, our intuition fails us when we try to figure out how fast exponential growth is. That is, it sneaks up on you.

And two, if a technology grows exponentially, it quickly opens up many new opportunities.

Solver speed has increased exponentially for a few decades, with steady, yearly speed-ups ranging from 20% to 100%.

Did growth catch me off guard? Did it make Ehsan realize he couldn’t trust his instincts about run time?

If we’ve hit a tipping point, this may be a new golden age for optimization. Of course, there are still (and always will be) problems that take a long time to run. And some combinatorial problems require custom solutions because even medium-sized problems cannot be efficiently solved.

But has the exponential growth snuck up on us and opened up many new possibilities?

We’d love to hear from the optimization community. Is this what you are seeing? Do you see new possibilities for using optimization more broadly and for different things? Or are we still a few years out?