What's a heuristic and when you should use it

In Computer Science and Mathematical Optimization, we usually look for a procedure that yields an exact solution for a problem. In the general context, that means always returning the right answer, and, in the optimization case, the right answer is the best one! But as we saw in P vs. NP: a million-dollar problem, not every problem can be optimally solved in a feasible amount of time. That's exactly what motivates a growing research field that studies methods of finding the best solution you can in the time you have. These methods are known as Heuristics.

To illustrate how useful heuristic methods can be, let’s borrow the example from The Queen's Gambit and complexity and imagine a game of chess. More precisely, let's consider a practical chess game in which the players have a time limit. We can build an algorithm to play chess that considers all possible moves and chooses the best one. But despite having proven to be optimal, this algorithm would always lose in a real-life game. Even with our modern supercomputers, it would take an absurd amount of time to decide its opening move. So how could a computer beat the world champion, Garry Kasparov, in 1997? With Heuristics, of course!

The main difference between exact methods and heuristics is in the approach. Exact methods focus on finding the optimal solution in the least amount of time, which, in many cases, means balancing between trying to find a better solution and trying to prove that your current best solution is optimal. On the other hand, heuristic methods focus on understanding what constitutes a "good" solution and developing a search method that takes advantage of that knowledge. A usual starting point for developing heuristics is to replicate the logic of a professional. In the chess example, a commonly used heuristic is to create, with the help of expert chess players, a function that can score a board configuration based on piece positions. This function avoids having to simulate every possible game to the end.

But should I always choose heuristics? Of course not! Many practical problems can be solved optimally, and if this is the case, you should go for the optimal answer! But in cases when the optimal solution is not possible, you should be aware of the downsides of heuristics and how to overcome then:

When is it "good enough"?

When you have an optimal solution, you know that you could have not done better. But if you are using a heuristic, you never know if you could have a 50% improvement if you just tried a little more. Luckily, in the majority of the cases, a study based on generated instances of your problem can indicate when a given search method starts to plateau. With this, a skilled optimization professional can define good stopping criteria that, based on your needs, will provide you the best tradeoff between time and solution quality.

Humans are not always good in solving problems

As we discussed, a common strategy for heuristics is to use human intuition as a starting point. That's great in many situations, but sometimes human limitations and biases can result in bad decision-making. Designing a good heuristic is not simply coding the professional intuition into a solution. An efficient search method that takes advantage of the computer speed is also very important to explore different and unusual solutions.

They are hard to compare

Comparing two heuristics is not a trivial task. You almost always have a mixed result where method A yields better results in some cases and, in others, method B is superior. Carefully built statistical analysis and a good computational model of the problem are very important to identify a robust method that yields good solutions in a large variety of contexts. Another good practice is to use methods with free parameters that can be fine-tuned to different scenarios.  

Author: Vinícius Mello - Consultant at Cassotis Consulting

                                      Co-author: Fabio Silva - Senior Manager at Cassotis Consulting