Is there a theory for heuristics in the field of optimization?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
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?
optimization algorithms problem-solving
asked Aug 31 at 1:47
Stoner
5482923
add a comment |Â
up vote
2
down vote
favorite
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?
optimization algorithms problem-solving
asked Aug 31 at 1:47
Stoner
5482923
3
I don't know if there can be a mathematical theory for heuristics, but you could find some heuristics for heuristics.
– Jair Taylor
Aug 31 at 1:54
1
@JairTaylor Ah yes do you mean somewhere along the lines of sciencedirect.com/science/article/pii/S0003687015301162?
– Stoner
Aug 31 at 2:20
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.
– Stoner
Aug 31 at 6:39
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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?
optimization algorithms problem-solving
asked Aug 31 at 1:47
Stoner
5482923
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?
optimization algorithms problem-solving
optimization algorithms problem-solving
asked Aug 31 at 1:47
Stoner
5482923
asked Aug 31 at 1:47
Stoner
5482923
asked Aug 31 at 1:47
Stoner
5482923
asked Aug 31 at 1:47
Stoner
5482923
asked Aug 31 at 1:47
Stoner
5482923
5482923
3
I don't know if there can be a mathematical theory for heuristics, but you could find some heuristics for heuristics.
– Jair Taylor
Aug 31 at 1:54
1
@JairTaylor Ah yes do you mean somewhere along the lines of sciencedirect.com/science/article/pii/S0003687015301162?
– Stoner
Aug 31 at 2:20
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.
– Stoner
Aug 31 at 6:39
add a comment |Â
3
I don't know if there can be a mathematical theory for heuristics, but you could find some heuristics for heuristics.
– Jair Taylor
Aug 31 at 1:54
1
@JairTaylor Ah yes do you mean somewhere along the lines of sciencedirect.com/science/article/pii/S0003687015301162?
– Stoner
Aug 31 at 2:20
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.
– Stoner
Aug 31 at 6:39
3
3
I don't know if there can be a mathematical theory for heuristics, but you could find some heuristics for heuristics.
– Jair Taylor
Aug 31 at 1:54
I don't know if there can be a mathematical theory for heuristics, but you could find some heuristics for heuristics.
– Jair Taylor
Aug 31 at 1:54
1
1
@JairTaylor Ah yes do you mean somewhere along the lines of sciencedirect.com/science/article/pii/S0003687015301162?
– Stoner
Aug 31 at 2:20
@JairTaylor Ah yes do you mean somewhere along the lines of sciencedirect.com/science/article/pii/S0003687015301162?
– Stoner
Aug 31 at 2:20
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.
– Stoner
Aug 31 at 6:39
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.
– Stoner
Aug 31 at 6:39
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
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.
answered Aug 31 at 5:49
aslv95
918
1
Thank you for the valuable insights! I will take a look at them in the meantime :)
– Stoner
Aug 31 at 6:36
add a comment |Â
up vote
1
down vote
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.
answered Aug 31 at 2:57
anon
111
Thanks for the clarifications and insights. I'll take note of that :)
– Stoner
Aug 31 at 6:38
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
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.
answered Aug 31 at 5:49
aslv95
918
1
Thank you for the valuable insights! I will take a look at them in the meantime :)
– Stoner
Aug 31 at 6:36
add a comment |Â
up vote
2
down vote
accepted
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.
answered Aug 31 at 5:49
aslv95
918
1
Thank you for the valuable insights! I will take a look at them in the meantime :)
– Stoner
Aug 31 at 6:36
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
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.
answered Aug 31 at 5:49
aslv95
918
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.
answered Aug 31 at 5:49
aslv95
918
answered Aug 31 at 5:49
aslv95
918
answered Aug 31 at 5:49
aslv95
918
answered Aug 31 at 5:49
aslv95
918
918
1
Thank you for the valuable insights! I will take a look at them in the meantime :)
– Stoner
Aug 31 at 6:36
add a comment |Â
1
Thank you for the valuable insights! I will take a look at them in the meantime :)
– Stoner
Aug 31 at 6:36
1
1
Thank you for the valuable insights! I will take a look at them in the meantime :)
– Stoner
Aug 31 at 6:36
Thank you for the valuable insights! I will take a look at them in the meantime :)
– Stoner
Aug 31 at 6:36
add a comment |Â
up vote
1
down vote
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.
answered Aug 31 at 2:57
anon
111
Thanks for the clarifications and insights. I'll take note of that :)
– Stoner
Aug 31 at 6:38
add a comment |Â
up vote
1
down vote
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.
answered Aug 31 at 2:57
anon
111
Thanks for the clarifications and insights. I'll take note of that :)
– Stoner
Aug 31 at 6:38
add a comment |Â
up vote
1
down vote
up vote
1
down vote
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.
answered Aug 31 at 2:57
anon
111
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.
answered Aug 31 at 2:57
anon
111
answered Aug 31 at 2:57
anon
111
answered Aug 31 at 2:57
anon
111
answered Aug 31 at 2:57
anon
111
111
Thanks for the clarifications and insights. I'll take note of that :)
– Stoner
Aug 31 at 6:38
add a comment |Â
Thanks for the clarifications and insights. I'll take note of that :)
– Stoner
Aug 31 at 6:38
Thanks for the clarifications and insights. I'll take note of that :)
– Stoner
Aug 31 at 6:38
Thanks for the clarifications and insights. I'll take note of that :)
– Stoner
Aug 31 at 6:38
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2900224%2fis-there-a-theory-for-heuristics-in-the-field-of-optimization%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
3
I don't know if there can be a mathematical theory for heuristics, but you could find some heuristics for heuristics.
– Jair Taylor
Aug 31 at 1:54
1
@JairTaylor Ah yes do you mean somewhere along the lines of sciencedirect.com/science/article/pii/S0003687015301162?
– Stoner
Aug 31 at 2:20
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.
– Stoner
Aug 31 at 6:39