How to choose the right approach for your problem
When someone claims to optimize a process or solution, we naturally wonder—is it genuinely the best, or just a step up from before, or perhaps "good enough"? What techniques were employed to achieve this optimization? These questions matter for understanding the quality of a solution and identifying areas for improvement.
So, let’s dive into different solution approaches for optimization problems and their implications for decision-making.
The Main Players: Mathematical Optimization (MO) and Heuristics
Dealing with optimization problems involves various approaches, including mathematical optimization—where Mixed Integer Programming (MIP) stands out—heuristics and metaheuristics, constraint programming, simulation-based optimization, and more.
Among the above techniques, mathematical optimization (MO) and heuristics are the more common ones. MO provides optimal solutions while, broadly speaking, heuristics are designed to provide solutions fast for a specific problem, with no guarantee on the quality or proof of optimality.
While both MO and heuristics provide solutions, they differ significantly, and each has its place in problem-solving. So, let's explore their key differences:
1. Solution Quality
MO aims for optimal solutions through systematic exploration of all potential solutions, ensuring the absolute best outcome. Heuristics, on the other hand, may take shortcuts, lacking the thoroughness of MO, and can’t guarantee optimality.
Note that, even if the optimal solution is not needed in a specific problem, one can still set the “optimality gap” or “MIP gap” which defines how close from the optimal objective function value a solution can be to stop the optimization process.
2. Speed
Heuristics tend to have faster execution and implementation times, but their ease of implementation comes with a caveat. Crafting custom heuristics for complex problems might take longer than developing an MO model.
3. Scalability and Maintenance
MO is generally easier to maintain and expand. Because the key problem features are captured in MO through decision variables, constraints, and objectives. So, if any of those change, it’s easier to modify the MO model with the necessary adjustments, making it a suitable technique in dynamic environments. Because the underlying mathematical programming engine and algorithms remain the same.
Now, let's delve into a checklist to help decide which approach suits your specific problem.
Photo by David Travis on Unsplash
MO vs Heuristics: A Checklist
1. How hard is your problem?
To answer this question, you need to have a good understanding of your problem. To help you find out your problem complexity, consider a few things:
Not all problems are created equal. Some optimization problems are usually more difficult to solve than others. The number of variables and constraints alone doesn't determine a problem's solvability or runtime. Nowadays, you may be able to solve models with a million variables or constraints in a matter of minutes. And at the same time, formulate a model with hundreds of variables and a handful of constraints and fail to solve it.
The choice and implementation of algorithms influence solution efficiency or even the ability to solve the problem. Even the same algorithm on different datasets may yield different execution times.
How you formulate a problem matters. The way you express a problem mathematically can impact runtime. For example, the famous cutting stock problem can be formulated using binary variables that track usage of raw rolls and whether a desired roll is cut from a specific raw roll. But it turns out that this is not a good formulation. A better way to formulate this problem is by tracking different configurations or patterns that can be cut into a raw roll to see how many of them are needed. Although both of these formulations result in the same solution, they have very different run times (if you’re curious, you can check both of these formulations with detailed explanations about them, here).
Remember that advancements in computational power and algorithms have made solving previously hard problems faster. So, if you had difficulty solving a problem several years ago, give it another try.
Some problems were hard to solve because they were running on-premise and could get into memory issues for larger datasets. But nowadays many models run on cloud and it’s a lot easier to spin up a larger machine if needed. With memory being cheaper and less of a constraint, you can give your memory-consumer MO models another try rather than compromising on solution quality.
2. How constrained is your problem?
This one is related to the first point, but it deserves its own discussion.
More business constraints doesn't necessarily make an optimization model harder to solve. Constraints narrow down solution spaces, making the problem more manageable. Of course, you may still need to write a model with many variables and constraints that can take some time, but as already discussed, the number of variables and constraints shouldn’t immediately deter you from giving MO a try. Think about house hunting. Without any restrictions, you have all the houses in the market to consider. But as you start adding some filters or constraints, like your budget, location, and so on, your options become fewer and the process more focused.
3. How quickly do you need the results?
We all tend to want the results faster. But consider how quickly they are really needed. Balance the need for speed with the value of an optimal solution. For strategic problems, a few days might be more valuable than a quick heuristic solution. Similarly, the solution a user gets through an app on their phone, may need to be achieved in a matter of milliseconds or seconds.
4. How precise does the final solution need to be?
Surely you want to get the best solution but how good is good enough? Is 1% worse than the optimal solution still acceptable? How about 5%? How about 10%? What’s the gap that you’re comfortable accepting? Of course, if you’re deciding on the optimal level of additives in a drug, there should probably be no room for error and the solution should be optimal, but if you’re making a multi-million-dollar investment decision, then a few thousand dollars may not seem that big of a deal. Remember, heuristics don’t have a proof of gap so you can’t just say stop at 5%. That’s doable with MO.
5. How are you currently solving the problem?
Evaluate whether the problem is new or has an existing solution. If existing solutions are not satisfactory or scalable, especially if heuristics are being used, it might be time to explore new approaches. However, you may be able to combine existing solutions with mathematical optimization.
For example, maybe you can use the current heuristics to quickly find a solution and then pass them to MO to generate an optimal solution from that, essentially telling MO not to start from scratch (this process is called “warm start” or “MIP start” and you can check a discussion on that here).
Or maybe you can use your existing heuristics to decompose the problem into smaller more manageable sub-problems and then use MO on each of those, getting your final answer by combining the solutions to each of the sub-problems.
After all, the choice between MO and heuristics doesn’t need to be binary. Mixing them together is a viable option too. For example, in transportation optimization, it’s common to have different heuristics, each aiming to generate initial routes for delivery trucks. Then these routes are passed to an MO model to select the best routes among the provided options.
6. How much time or resources can you invest in solution development?
On the one hand, if you have an experienced person, they can build an optimization model in a few hours or days, whereas the same person might require weeks to design and develop a custom heuristic.
But the other side of the coin is that there are off-the-shelf implementations of some heuristics that someone with coding skills and with limited or no mathematical optimization background might be able to manage easily. Although, these heuristics usually require some fine-tuning as well, which is still critical.
So far, we compared mathematical optimization and heuristics, and we talked about a checklist to consider when deciding which of these tools is more suitable for your problems.
We can now summarize all we learned into a couple of recommendations.
Recommendations
Answer the checklist questions: Use the checklist to gain a sense of where you need to direct your time and effort for better results. If achieving the right balance between time and solution quality is challenging with MO alone, consider using heuristic approaches. But don’t rule out hybrid approaches where MO and heuristics complement each other and can yield effective results.
Formulate even with heuristics: Even if opting for heuristics, try to mathematically formulate your problem. This exercise provides insights into a problem’s complexity and guides heuristic development since it can pinpoint the challenging constraints and perhaps spark some ideas on where to focus your effort.
In closing, a personal rule of thumb is to initially pursue mathematical optimization. The advancements in computational power and algorithmic capabilities, make this a worthwhile investment. If the solution through MO is not possible, the formulation exercise can pave the way for designing more efficient heuristics. Remember, in solving optimization problems, it's not a rigid choice between MO and heuristics—sometimes, the most effective solutions arise from a combination of both.