📈 #86 Where did the time go? Part VI: the mindset shift
Why the real bottleneck isn't your solver, it's your problem framing
You know that quote that says…
All models are wrong, but some are useful.
George E. P. Box
The usefulness of a model lies in that fine line that separates if the model can solve the problem in a reasonable amount of time or not, and it comes with -lots of- challenges.
After taking a different approach on a problem I tackled, I reduced the needed time by 50% and improving the number of best solutions found by 3x. Just by looking at it from a different perspective.
That was revealing.
So today we’ll see in Feasible:
🪨 Understanding is the hard part
⚙️ Tractability drives our careers
🛠️ …And the way we work
This is not only the last part of the 6-post series about tractability, but also the last deep dive until I come back from vacations until September. If we don’t have the chance to speak again, have some wonderful weeks!Are you ready? Let’s dive in… 🪂
🪨 Understanding is the hard part
Let’s go back to September 2015.
I almost didn’t arrive to my destination, but two people were waiting for me in Lorient. Sunny day, even better than in Madrid. And there I had my supervisor for the next three months and a PhD student I knew through one of my girlfriend’s friends.
I was there to solve the Minimum Sitting Arrangement Problem, and I must admit I did just read the paper of reference while on the train from Paris to Lorient. I didn’t even speak English properly, and French was a pending subject.
The thing is I wanted to use a similar approach with this problem as in the previous ones I tackled. In the end, it was a good one!
But this problem was different.
Instead of being just a pure combinatorial issue, you could spot patterns of what good solutions would look like. You could imagine nodes connected among them, and plot them with GraphViz or a similar tool. Why? Because here we needed to arrange a graph into a line to minimize the number of errors. These errors occur when elements with negative connections are closer together than elements with positive connections in the arrangement.
The problem was easier to think about, but still difficult to tackle: there were many solutions
After a couple of meetings with my supervisors, I took a different approach.
Instead of just relying on VNS entirely, I added a new first phase to analyze the problem and solve an easier one. I could split it into cliques with those negative connections, and then solve the problem of connecting those cliques in the best possible way.
This allowed me to reduce the computational time by half but also solve some instances to optimality, multiplying the number of best solutions found by 3x.
This experience was a big lesson: if you can reframe your problem and look at it from a different angle, you’ll take advantage of its structure and solve it easily.
⚙️ Tractability drives our careers
When we’re solving our optimization problems, we expect to have a solution in a specific period of time.
Well, even more than that. We expect to have a high-quality solution in a short period of time.
(that’s better)
But sometimes we don’t get that, and we may get frustrated.
Understanding tractability changes what we do first, what we ignore, and how we sell results.
Throughout the course of this series, we’ve learned several things:
📊 The importance of benchmarking
When you have a model or algorithm that usually solved in 10-15 minutes but suddenly broke when making the problem bigger, what do you do?
Is it a problem of scale? Structure? The algorithmic approach? Simply hardware?
You shouldn’t guess it, but profiling the execution of your model so that you understand where it comes from. We learned in the first part of this series we need to measure CPU time, solution quality, and memory footprints if possible.
Those metrics will give you enough information to start solving the tractability problem.
I also shared with you one prompt to let AI interpret the logs for you (very useful!), and a flowchart to simplify the way you address this and detect where the issue comes from.
Benchmarking is crucial to understand your next steps.
🚀 Scaling will change the way you solve your problems
Working at a startup forces you to think out of the box quite a lot of time.
When we were managing around 120 trucks, they asked me if we could use the very same approach as of today’s if we had 1,000 trucks instead. The answer: “of course not!”.
We wouldn’t have that scale of the business in a short period of time, that’s true, but it also sparked some ideas on how to handle the problem in the future. The complexity lying under a problem with 100 trucks is not the same if we multiply them by 10.
The problem of assigning drivers to routes grows almost quadratically with the number of routes. Add it relay points to split a route into different segments, and instead of having just one route you have 2, 3, or even 4 segments of routes in the worst-case scenario. This means that the problem is significantly harder to solve.
So in the second part of this series we saw four ways of tackling this large-scale optimization problems, being heuristics and metaheuristics my preferred way of working.
Anyway, I always try to reduce the granularity of the problem before diving into them.
🧱 Many similar solutions will reduce the performance of your solver
Symmetries make the search space artificially bigger, complicate the way we compare solutions, and thus make it harder to find the best possible solution.
But how? They multiply the number of equivalent solutions.
The good thing is that many others in the space have studied symmetries already, and we saw in the first part of symmetries sub-series the types of symmetries and classical algorithms to tackle them. In the second part though, we saw advanced techniques, some of them reserved to the most advanced solvers in the market. And in the third part we saw ML-guided techniques that seem to be promising.
But remember: symmetry breaking constraints add memory overhead, so sometimes it’s better to just accept longer solve times than exceed memory limits.
Or…
⚖️ Not all the typical algorithms are easily parallelizable
You and I know we’re not here to lower our arms and accept we cannot solve the problem.
That’s not in our DNA.
So another way of breaking the limits is by parallelizing our algorithms. That will give us the possibility of either explore a wider portion of the search space or reduce the computation time.
The main problem? We cannot -easily- parallelize all the algorithms.
Algorithms with minimal communication between threads, independent progress, and that aren't overly sequential tend to be the best candidates. Parallelizing these can lead to meaningful speedups or the ability to explore more of the search space.
In the fourth part of this series, we saw the worst and best algorithms to parallelize, and some techniques to do it.
💻 The typical ‘throw more hardware’ may not help you here
In 2019, I started working for Fujitsu to use their quantum-inspired hardware to solve optimization problems.
It was quite promising: a process that took more than 2 hours could be solved in 5 minutes. That’s not theory, it’s something I could develop for the very first proof of concept we ran.
But if we have that speedup with just quantum-inspired hardware, is there any hardware better than CPUs to solve optimization problems? Why we’ve been stuck with them all this time?
In the first part of this sub-series about hardware, we explored why CPUs are tailor-made for optimization work, that there are workloads that break the “CPU only” rule, and CPUs are hitting their own ceilings. Which leads us to exploring other hardware approaches to solve this difficult problems.
Which ones? Apart from Digital Annealer, the quantum-inspired hardware from Fujitsu, we can see others. The most promising ones: quantum (not inspired, the real one) and GPUs.
The right question here is when should you consider alternatives?, and that’s something we talked about in the second part.
🛠️ …And the way we work
The tractability mindset isn't about learning new skills, it's about fundamentally changing your approach to optimization problems.
To me, there are three major changes in the way I work after tackling so many difficult problems:
🔢 Selecting a solver
It’s easy to fall into the trap of “Gurobi is the best solver, let’s use that”.
But if you analyze your optimization problem, you’ll understand that some algorithms are better suited than others to solve it.
This is not a race of knowing more and more solvers, but about matching problem structure to algorithmic strengths.
🗣️ Communicating the issues
When you face tractability issues you easily see the main symptom: the problem is becoming more and more difficult to solve. A process that used to take 10-15 minutes become more than one hour.
How do you communicate that to stakeholders? The wrong choice is just “the optimization engine is slow, we need more time for running it”.
Better: “we’re hitting multiple equivalent solutions, so we can try to solve this issue or accept suboptimal solutions in that 10-15 minutes range”.
You’ll need to communicate root causes and strategic choices, not just symptoms.
✅ “Good enough” is good enough
The main metrics we’re taught at university is gap thresholds (for exact approaches) or deviations from the best possible solution (for heuristic approaches).
That only speaks about optimality.
And you know the number of stakeholders that cares about that in the industry? Exactly, close to zero, null, zéro, ninguno.
So if you see that your current approach saves a good amount of time or a good amount of money (extra points if it does both things at once), just ship it. You’ll have the chance to improve it later while saving time/money in the meantime.
🏁 Conclusions
Tractability thinking changes your problem-solving sequence:
Old sequence: Model → Solve → Scale → Debug performance New sequence: Understand → Simplify → Model → Solve → (Scale only if needed)
Most "hard" problems become "easy" problems when you find the right simplification. And most scaling challenges disappear when you're scaling something that's already efficient.
This is what changes with tractability mindset: not the individual skills, but the strategic approach to applying them.
Let’s keep optimizing,
Borja.
