2
$\begingroup$

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?

$\endgroup$
3
  • 3
    $\begingroup$ I don't know if there can be a mathematical theory for heuristics, but you could find some heuristics for heuristics. $\endgroup$ Aug 31, 2018 at 1:54
  • 1
    $\begingroup$ @JairTaylor Ah yes do you mean somewhere along the lines of sciencedirect.com/science/article/pii/S0003687015301162? $\endgroup$
    – Stoner
    Aug 31, 2018 at 2:20
  • $\begingroup$ To all who follow this post, I will accept an answer not today, but will do so in a few days time, once I have collected my thoughts based on the feedback given in the answers. $\endgroup$
    – Stoner
    Aug 31, 2018 at 6:39

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you for the valuable insights! I will take a look at them in the meantime :) $\endgroup$
    – Stoner
    Aug 31, 2018 at 6:36
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for the clarifications and insights. I'll take note of that :) $\endgroup$
    – Stoner
    Aug 31, 2018 at 6:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .