You may argue that because of the No Free Lunch Theorem, you are doomed from Day 1. And indeed, in order to attack a new problem you may need several trials in several "departments":

* You may need to write down your optimization problem not only once, but in several attempts, so that you can decide how variables as well as constraints shall be defined. (Many students I meet think that there is only one way to "write down" the model, but decision variables can, for many actual problems, be defined in different ways, and some are profitable for some problems, for some others not. Expertize through lots of variations of model definitions will provide you with a better understanding what works the best for your type of problems. Perhaps you can run a software for smaller problem instances, and draw some conclusions, but if you need to solve a problem with very many variables and/or constraints, then you need to investigate - in more detail - possible representations of the problem, such that natural algorithms from the world of mathematical optimization can be applied.

* Nothing should stop you from combining methods, of course. Branch & Bound, Branch & Cut, Lagrangian relaxation, Benders decomposition - and heuristic versions thereof - may work for you in some cases, in some cases not.

* Remember that the "NP=P?" question is not yet resolved.

I think they see that these algorithms are very simple compared to their methodologies.

Because they are stochastic and not exact, and in most of the time is faced with unrealizable solutions. but it does not prevent their effectiveness provided you make a good setting.

You may argue that because of the No Free Lunch Theorem, you are doomed from Day 1. And indeed, in order to attack a new problem you may need several trials in several "departments":

* You may need to write down your optimization problem not only once, but in several attempts, so that you can decide how variables as well as constraints shall be defined. (Many students I meet think that there is only one way to "write down" the model, but decision variables can, for many actual problems, be defined in different ways, and some are profitable for some problems, for some others not. Expertize through lots of variations of model definitions will provide you with a better understanding what works the best for your type of problems. Perhaps you can run a software for smaller problem instances, and draw some conclusions, but if you need to solve a problem with very many variables and/or constraints, then you need to investigate - in more detail - possible representations of the problem, such that natural algorithms from the world of mathematical optimization can be applied.

* Nothing should stop you from combining methods, of course. Branch & Bound, Branch & Cut, Lagrangian relaxation, Benders decomposition - and heuristic versions thereof - may work for you in some cases, in some cases not.

* Remember that the "NP=P?" question is not yet resolved.

Thank you for your lucid answer Professor Michael Patriksson

Mohammed Qais Well, they are indeed simple in the sense that they lack the rigor but, this is not the reason I think some mathematicians argue against this class of algorithms. These algorithms are sometimes useful and even practically can do better if compared to the traditional algorithms but there is always a trade-off involved. Like anything in life!

So, the final judgement is rather 'subjective'. Some for instance would argue against them because they are not deterministic in nature and I actually agree with these mathematicians. These mathematicians are more concerned with "perfection" rather than practicality which is not so strange, true mathematicians are artists in nature.

well, mathematicians tend to be theoretical and as an applied mathematician and an optimizations expert, we just want solutions, very good ones at that. we dont care how they are found. I have realized that in CPLEX for example, solution polishing which uses evolutionary algorithms to obtain new solutions from incumbent solutions can be sometimes better at finding optimal or near optimal solutions where branch and bound is still struggling.

With all due respect, being a mathematician, theory, is what we do. We make abstraction of situations that occur in life. Engineers use theoretical results develop by mathematicians, and they don't question the validity of them. But mathematicians we always question facts, and even theories.

Well, to question facts sounds bad in my ears. :-)

Following):

May be intervention of non-mathematicians into the field of optimization who always develop black box type of solution methods. Mathematicians love anything which can be proved

Vijaya: we certainly do not always develop black-box methods. Have you been sleeping in the lecture room again? :-)

Dear Sir, I do not mean all non-mathematicians give always black box methods. This is just communication gap.

We do not love just anything - we always try to derive something worth-while - sometimes even approximate stuff - if the problem is stiff. We are not only theorists - also we do lots of work in industry collaborations, which means that we need to derive practical solutions. And we do, and we do it well. And we both publish and implement in the work-place.

To my opinion, nowadays, metaheuristics are just an easy way of publication. To publish one, select any nature's phenomenon, relate it somehow with few simple existing equations, get the results and prove anyhow this works better than the existing one. Definitely not a fan of those! However, in last decade some researchers have proposed some powerful ones. Some of them does not require any tuning parameters and can provide a good quality solution for the complex engineering problems for which estimating accurate derivates is almost impossible.

NOW I think I see what you mean! :-) Yes, I interpreted you wrong - sorry! Communication gap, indeed.

Mathematicians are more concerned about the completeness of theory, but solving practical problems is secondary.

Jia Yao: Wrong. As we work on very complex combinatorial optimization problems together with industrial partners, we work on very practical things, too. Wherever you got the notion that a mathematician only worries about proofs, they were terribly wrong. I guess you are not a mathematician. Don't spread a false rumour, then.

We combine, with big success, practical models that are dedicated to the exact problem at hand, theory that enables us to create combinatorial models with nice properties regarding their practical complexity, we create smart implementations that run very fast, and that provide near-optimal solutions. That's what the industry needs - together with a valid estimate on near-optimality. And it's fun!

We also receive awards - if that can be seen as a positive thing: one in industrial maintenance, regarding aircraft engine components; and one on our work in transportation research.

And we run such projects to this day - since 20 years back.

Ergo: don't tell me that we do not care about practice. End of.

And I should add - based on the headline of this thread, "Why some mathematicians are against meta-heuristic and heuristic algorithms?":

I do not dislike metaheuristics per se; they have their pros and cons just like every other methodology have. What I do find troubling is that too many get stuck in the bubble. It would be beneficial for all if the two "communities" - if we can call them that - could work together. Perhaps that's what is called matheuristics?

We could definitely gain by talking more, providing valid estimates from the math side, and practical "short-cuts" and other tools from the other.

.

..

In my opinion, mathematicians are not opposed to such algorithms because they are able to solve very interesting problems accurately. They are opposed to people who, when faced with any problem, quickly turn to meta-heuristic algorithms without realizing the problem.

For example, I know a professor who asked his student to implement a meta-heuristic algorithm to solve a particular problem. That student found the optimum point for his teacher with a pencil because the total search space for that problem was only 7 cases. It ended with the rejecting of the poor student, and it became an experience for others to solve any problem with the meta-heuristic algorithms, regardless of its structure. In my opinion, such behaviors could be the source of opposition to these valuable algorithms.

In the time, where an exact or analytic solutions of a given problem take (hours, days or even months), heuristic and meta-heuristic solutions are efficient in both time and accuracy, without a doubt they are the best alternative when the problem is NP-hard. I think that, there is no mathematician who can oppose the use of heuristic and meta-heuristic algorithms.

It's a delicate matter, this one. I do not think that you are quite correct. If you were to look up

https://en.wikipedia.org/wiki/Knapsack_problem#Computational_complexity

you would find a rather nice description of ways in which to approximately solve the knapsack problem, for example. These methods both are fast and provide solutions that are proven to be near-optimal. I have not seen any metaheuristic that has a worst-case guarantee. Have you?

This question is similar to another one that I have seen. My response to that one was basically this:

1. I don't know any mathematicians who are prejudiced against heuristics per se. Many of them (myself included) use them regularly.

2. I do know a lot of mathematicians who are fed up with people claiming to invent dozens of "new" meta-heuristics every year (like harmony search or the bat algorithm), when really they are just old ideas expressed in fancy new words. Actually, many people in the heuristics community are unhappy with it as well.

3. I also know people working in combinatorial and/or global optimisation who are fed up with people saying "problem X is NP-hard, and therefore one must use a heuristic". This shows a breathtaking ignorance of the (vast) literature on exact methods (and approximation algorithms) for NP-hard problems.

(By the way, I agree with Michael's comment about "matheuristics" being a very interesting research direction.)

Not only mathematicians, but also some engineers will not recommend to use evolutionary algorithms and meta-heuristics in most cases. Specially, for large scale problems such as topology optimization of continuum structures. For example, in the paper: “Sigmund, O. (2011). On the usefulness of non-gradient approaches in topology optimization. Structural and Multidisciplinary Optimization, 43(5), 589-596.”, the use of evolutionary algorithms in topology optimization is discussed. In this paper, it is demonstrated that most of evolutionary approaches and meta-heuristic are hopelessly inefficient in solving the problems with many variables such as topology optimization and the final designs are not satisfactory (in familiar objectives such as compliance minimization).

In other words, non-gradient methods should be used in special and costly objective functions such as crashworthiness design in which there is computational noise in gradient information and analytical derivatives are unavailable (Bujny, M., Aulig, N., Olhofer, M., & Duddeck, F. (2018). Identification of optimal topologies for crashworthiness with the evolutionary level set method. International Journal of Crashworthiness, 23(4), 395-416.).

Metaheuristics are one tool among many others in the box of optimization professionals and researchers. Like any other method, they are useful in specific application contexts, typically in conditions where other methods (e.g., mathematical-programming based methods, dynamic programming, approximation algorithms, randomized algorithms...) fail due to excessive computational time. This situation, unfortunately, occurs often when facing practical large-scale problems combining multiple decision sets. Learning when to use metaheuristics is an important prerequisite before even applying any metaheuristic. You could check the following introductory slides (slides 29-35) for example:

http://www-di.inf.puc-rio.br/~vidalt/courses/Slides/1-Introduction.pdf

Regarding convergence properties, there are some for specific types of genetic algorithms and simulated annealing approaches, but these results are mainly theoretical and suppose an arbitrarily high number of iterations.

Regarding the "no free lunch" argument, keep in mind that the same argument applies to all search methods (not only metaheuristics). It says that for any arbitrary function (which arbitrarily associates INPUTS with OUTPUTS), no search method is better, on average, than any other. However, when you do practical optimization for useful problems, there is always some structure that can be exploited, i.e., you are not picking an arbitrary objective function in the space of all possible objectives. Otherwise, research on this problem would be pointless.