Member-only story
Exact Algorithm or Heuristic?
A step-by-step guide to make the right choice for your mathematical optimization problem
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…
