Exact Algorithm or Heuristic?
Are you struggling to find the best method for solving your optimization problem? When it comes to solving optimization problems, there are two main approaches: (meta-)heuristics and exact algorithms. Each approach has its own strengths and weaknesses, and the choice of method will depend on the specific characteristics of the problem. In this post, we will explore the differences between heuristics and exact algorithms, and help you decide which method is best suited for your problem.
Often used exact algorithms are linear programming, mixed integer programming and constraint programming. Famous heuristics are local search, genetic algorithms and particle swarm optimization. To improve an heuristic like local search it's interesting to combine it with meta-heuristics like simulated annealing or tabu search.
In this post, we'll start with an example to compare and explain different characteristics of exact algorithms and heuristics. The parts that follow will explain some considerations when choosing for an exact algorithm or heuristic, starting with a flowchart to make it even easier for you to make the right choice!
Besides the considerations of this post, other factors can play a part in your choice, like experience with different methods or maybe even gut feeling. This is a heads up that this post tries to generalize, but that every problem can have its own characteristics and circumstances that make you choose a certain approach, or let you deviate from the flowchart.
Comparison by Example
Let's start with an example to explain the main differences between exact algorithms and heuristics: say you have a delivery company with a fleet of trucks that need to deliver packages to different locations. The goal of the problem is to determine the best routes for each truck to deliver the packages in the most efficient way, while taking into account factors such as distance, delivery time windows, and truck capacity. This problem is a variation of the capacitated vehicle routing problem.
An exact algorithm for this problem might be a MIP model that formulates the problem as a mathematical optimization problem. The MIP model would consider all the constraints and objective(s) of the problem, and find the optimal solution that minimizes the total delivery time and cost, while ensuring that all the packages are delivered on time and within the capacity of each truck.
However, solving the MIP model for large problems can be computationally expensive and time-consuming, even with powerful computers. This is where heuristics come into play. A heuristic for this problem might be a simple nearest neighbor algorithm that assigns each package to the closest truck, and then optimizes the route for each truck using local search. While this approach may not guarantee an optimal solution, it can quickly generate good-quality solutions that are close to the optimal solution, and may be sufficient for practical applications.
In summary, the main difference between an exact algorithm and a heuristic is the level of accuracy and efficiency. Exact algorithms aim to find the optimal solution, but may be computationally expensive and impractical for large-scale problems. Heuristics, on the other hand, aim to find a good solution quickly and efficiently, but may not guarantee an optimal solution. The choice between these approaches depends on the specific characteristics of the problem and the trade-off between accuracy and efficiency.
Exact or Heuristic?
A couple of things are important to keep in mind when choosing between an exact algorithm and heuristic. I have divided them into four main topics: solution quality, performance, flexibility and costs. If you are looking for a quick answer (heuristic or exact algorithm), this flowchart might help:
Let's take a look at each of them in more depth.
Solution Quality
If your most important goal is to get solutions with the highest possible quality, because a slightly better solution brings a lot of value, you can stop here. In that case you should go for an exact algorithm. By using an exact algorithm, you know the gap between the optimal and current solution and you can continue the search until you have found the optimum.
But, an important note, if the problem is really large, an exact algorithm can take a lot of time to come to that optimal. Hours, days, or weeks are possible. Especially if you use an open source solver like CBC or glpk, you can't expect an optimal solution fast. You'd rather use a commercial one like Gurobi or CPLEX. And even with state of the art solvers, finding the optimal solution can take a lot of time.
The difficulty with heuristics is that it's hard to know the quality of the solution. You can compare it with a baseline, but you don't know the gap between the optimal and the current solution.
Performance
Heuristics are generally faster than exact algorithms because they sacrifice accuracy for speed. Exact algorithms aim to find the optimal solution to a problem, but this can be computationally expensive and time-consuming, especially for large-scale problems. Exact algorithms typically explore the entire solution space, which can be very large for some problems, and require the use of complex mathematical techniques to find the optimal solution.
Heuristics use simple rules of thumb to guide the search for a solution. Often they focus on a subset of the most promising solutions. This reduces the computational effort required to find a solution and allows heuristics to generate good-quality solutions in a shorter amount of time.
It's easier to implement problem-specific knowledge in a heuristic to guide the search for a solution, which can help to avoid exploring parts of the solution space that are unlikely to contain good solutions. This can further reduce the computational effort required to find a solution.
Flexibility
Heuristics are often more flexible than exact algorithms because they are not bound by the same restrictions as exact algorithms and can be adapted to address specific problem characteristics or constraints. Heuristics can often be implemented using simple algorithms and data structures, making them easier to develop and modify than exact algorithms. This allows heuristics to quickly adapt to new or changing problem instances, making them a good choice for problems where the solution needs to be found quickly or where the problem is likely to change over time.
Exact algorithms are based on mathematical models that provide a formal, rigorous framework for solving problems. These models are based on a set of constraints and objective functions that define the problem to be solved. However, this rigidity can make it difficult to address specific problem characteristics or constraints that are not easily captured by the mathematical model.
Overall, the flexibility of heuristics is one of their key strengths, allowing them to be applied to a wide range of problems and to quickly adapt to changing problem characteristics.
Costs
When it comes to solving large problems, obtaining a high-quality solver can cost a lot of money. However, the investment is often worth it for those who require the highest level of accuracy and speed in their solutions. And a great addition: you usually get good support when getting a commercial solver license, people with a lot of experience can help you with the model formulation and improve performance.
In terms of time, hiring consultants to implement solutions for you can be an efficient way to get things done quickly. However, this approach can also be costly, and may not always yield the most optimal results. For those who don't have the budget for consultants or want to maintain greater control over the problem-solving process, learning and implementing different heuristics can be a viable option. While it may take more time upfront, investing in the development of heuristics can pay off in the long run by providing a more customized and efficient solution process.
Conclusion
This post compares exact algorithms and heuristics for solving optimization problems. Exact algorithms aim for optimal solutions, but can be slow and computationally expensive. Heuristics sacrifice accuracy for speed, but can generate good solutions quickly. The choice depends on the specific problem and the trade-off between accuracy and efficiency. The flowchart provided aims to help choosing between the two methods. Considerations include solution quality, performance, flexibility, and costs.
And one final note: every problem is different and sometimes small nuances can make you choose another approach, which is perfectly fine. You can always reconsider your choice in a later stage, or try both approaches for Comparison purposes.
Related
Why Every Data Scientist Should Learn Mathematical Optimization
How to Handle Optimization Problems?
Mathematical Optimization Heuristics Every Data Scientist Should Know
