Is there a theory for heuristics in the field of optimization?

Question

I have been studying and working on heuristics in the field of optimization, in particular that of integer programming. A thought that has always been on my mind is that whether there is some (mathematical) theory developed for heuristics. I did some research by asking a few professors and looking up online literature, but the closest answer I got was that there isn't, or at most some kind of classification for classes of problems where a certain kind of heuristic works best for that class of problems. I also did manage to find https://link.springer.com/chapter/10.1057/9781137442505_3, but the authors describe the possible theory in more of a cognitive approach than a mathematical one.

Thus, I will like to ask: Are there are any developments in developing a mathematical theory for heuristics?

Answer 1

There are great theories behind most of the metaheuristics. Otherwise, it is not reliable to use them.

One example is Simulated Annealing. It is approaching the true optimum if you increase the number of iterations. There is a theory of the convergence. It is proven by using a Markov Chain with transition matrix, etc.

Also, whether a local search algorithm is PLS-complete or not requires a proof. The Lin-Kernighan heuristic for the TSP is PLS-complete for example and it is challenging to prove it.

You can find other examples in almost any kind of heuristics.

Answer 2

The short answer is no.

Heuristic algorithms are used to find feasible, but not necessarily optimal, solutions to mathematical optimization problems, where an objective function is minimized or maximized, possibly subject to constraints. Although we might wish for the heuristic algorithm to produce a "good" solution, there is no accepted definition for what this means. Without specifying a particular problem class and what constitutes a "good" solution, we can only say that a heuristic algorithm is one that produces a feasible solution.

This is not sufficient for developing a mathematical analysis. Any mathematical optimization problem can be shown to be equivalent to a problem where we only need to find a feasible solution and vice versa. A mathematical theory of feasibility problems is simply a theory of optimization problems.