I am surprised that a known scholar with a long experience in the transportation domain maintains such a hard stance on heuristic search. Obviously, we live in a world where extreme opinions are those which are the most echoed. Truth is, assuming that all practical optimization problems can be solved to optimality (or with approximation guarantees) is essentially wishful thinking. Given this state of art, better integration of exact and heuristic algorithms can largely benefit the research community. At the risk of repeating myself, here are some important remarks to consider:

• CPLEX and Gurobi (the current state of the art solvers for mixed integer programming optimization) rely on an army of internal heuristics for cut selection, branching, diving, polishing, etc... Without these heuristic components, optimal solutions could not be found for many problems of interest. CPLEX has even recently made a new release permitting a stronger heuristic emphasis (https://community.ibm.com/community/user/datascience/blogs/xavier-nodet1/2020/11/23/better-solutions-earlier-with-cplex-201). MIP solvers also heavily depend on the availability of good (heuristic) initial solutions to perform well. For many problems, cut separation is also done with heuristics. In the vehicle routing domain, we have a saying: heuristics are the methods that find the solutions, exact methods are those that finally permit to confirm that the heuristics were right (sometimes many decades later, and only for relatively small problems with a few hundred nodes despite over 60 years of research on mathematical models)...

• The machine learning domain is quickly taking over many applications that were previously done with optimization. Among the most popular methods, deep learning relies extensively on stochastic gradient descent and does not guarantee convergence to optimal parameters. Neural networks share the same issues as heuristics, but they have still led to notable breakthroughs. Decision-tree construction and random forests are largely based on greedy algorithms. The same holds for K-means (local improvement method), expectation-maximization, and many other popular learning models/algorithms.

• Even parameter tuning by the way is heuristic. Most design choices, even in the scientific domain, are heuristic and only qualify as good options through experimentation. Even the design of "exact methods" is in majority based on experimentation, as it is hard to determine beforehand which component, decomposition, or cut is going to pay off for a given application.

It's already done https://en.wikipedia.org/wiki/Matheuristics Matheuristics .

Dear Gennady Fedulov

Thank you for the link. I need your personal opinion about it. Would you recommend and use such a method?

Dear Pooya Rostami,

I am not a big fan of metaheuristics in any way, but in this direction you can bother one of the developers of this approach (Matheuristics), Stefan Voss https://www.researchgate.net/profile/Stefan_Voss . If he is kind to you, he will acquaint you with the entirety of information on the issues you are interested in, since he has rich statistics in the application of this approach.

Thank you very much Dr. Fedulov. I have sent Prof. Voss a message. I hope to have his comments here.

During the last years, interest on hybrid metaheuristics has risen considerably in the field of optimization and machine learning. The best results found for many optimization problems in science and industry are obtained by hybrid optimization algorithms. Combinations of optimization tools such as metaheuristics, mathematical programming, constraint programming and machine learning, have provided very efficient optimization algorithms.

Dear Pooya Rostami,

I agree with you that "for large scale problems, with higher computational cost (real-world problems), it would be inefficient to use an evolutionary algorithm."

My experience of solving NP-hard large- scale combinatorial problems showed that it is necessary first of all to deeply study the peculiarity of a particular problem and not to use evolutionary algorithms formally at the first step. Each real problem has certain features, its own specifics. This is what you need to use at the first step - to use these features and to reduce the size of the problem. After that, to apply evolutionary methods for smaller tasks. This is exactly what I do for many real problems, in particular for very difficult NP-hard combinatorial problems of designing integrated circuits, and I have achieved very good results without even using evolutionary algorithms. This state of partitioning, packaging, placement, routing, and TSP.

The use of hierarchical clustering helps a lot here, which allows to reduce the size of the problem, reducing it to hierarchically organized problems of small sizes. For small problems, you can already use evolutionary algorithms - but this is not mandatory.

Please, check out my methods on my Researchgate. First of all the paper :

1. MACROMODELING FOR VLSI PHYSICAL DESIGN AUTOMATION PROBLEMS January 2011 In book: G.Setlak, K.Markov. Business and engineering applications of intelligent and information systems.Publisher: ITHEAEditors: G.Setlak, K.Markov/.

2. Partitioning Optimization by Recursive Moves of Hierarchically Built Clusters.

3. Hierarchical clusterization, decomposition, and multilevel macro modeling—the effective and efficient tools to solve the high and very high size combinatorial circuit type problems (abstract only.

4. Topologically-Geometric Routing (also is used macro-modeling - some kind of clustering).

5. Partitioning Optimization by Iterative Reassignment of the Hierarchically Built Clusters with Border Elements.

6. Circuit Partitioning for FPGAs by the Optimal Circuit Reduction Method.

7. Decomposition Algorithms for Large-scale Clustered TSP.

8. A Decomposition Algorithm for Uniform Traveling Salesman Problem.

9. Decomposition and Scanning Optimization Algorithms for TSP.

10. The optimal circuit reduction method is an effective tool to solve large and very large size intractable combinatorial VLSI physical design problems.

11. Partitioning Optimization by Iterative Reassignment of the Hierarchically Built Clusters with Border Elements.

12. Power System Islanding by the Hierarchical Clustering.

13. The methodology and algorithms for solving the very large-scale physical design automation problems: Partitioning, packaging, placement, and routing.

14. “Hierarchical clustering – efficient approach to solve nonpolynomial large-scale combinatorial problems of circuit types”.

15. VLSI and PCB elements placement optimization using hierarchical scanning area method.

Gennady Fedulov

Thank you for your attention, I will gladly hear your opinion.

Regards,

Roman Bazylevych, DSc, PhD,

Full professor,

Lviv Polytechnic National University.

Email: [email protected]

Dear professor Roman Petrovych Bazylevych :

Thank you very much for your effective comment and interesting references.

As a mathematical optimisation scholar I am not really satisfied with the output from a heuristic, and I have lots of fun trying several versions of equivalent models with modifications, considering variable definitions, and so on - that's a very fruitful exercise.

Regarding metaheuristics I'd like to throw them out the window. Why? There's very little theory behind them, and I was brought up with theory as the main focus. I'd rather play with several variants of models of the problem described, and have them compete.

Dear professor Michael Patriksson :

Since I am a big fan of you, I mostly try to remember and analyze your comments. In a reply to the question “What is the future of Meta-heuristics?” in RG, one of your replies was (your reply is available in the attachment):

“In the mean-time I would like to propose to meta-heuristics enthusiasts to try to better combine your approaches with some elements of mathematical optimization….”

I am so curious to know more about it. What did you mean by “combining”? Does it mean hybridization? I would be so thankful if you please describe it more for us. Besides, I respect your opinions against metaheuristics.

I had some experiences, combining gradient-based methods such as the method of moving asymptotes (MMA) with some heuristics in structural optimization problems. I have observed that the unreliability of the hybrid algorithm will be decreased in comparison with the basic heuristic. Also, the algorithm will have the ability to handle the possible noise in gradient calculations (which MMA doesn’t have). However, it is completely true that again, it would be impossible to present any mathematical proof for the optimality and it is still unreliable.

To conclude, I think that this kind of combination is much better than proposing “the novel tired panda optimization algorithm” which most of the researchers in heuristics are doing.

Another - and much better - heuristic is the grizzly bear amputee heuristic. It's even better than magic!! ;-)

"Hybridisation" is a vague term, of course. What I might be ready to see is a smarter way to run B&B - if we are talking about integer programs - and if you have a test bed that is realistic and rich. Playing with heuristics within the nodes of a B&B search tree might help, but it will be rather application-specific.

We must nevertheless be aware that we are talking about hard problems - which means that the chance of getting a well-functioning heuristic devise is miniscule.

Thank you very much professor Michael Patriksson for the interesting and helpful comments.

You are a very hardworking person against metaheuristics! It seems that soon, you will convince many students (even me!), never use a metaheuristic again!

I wanted to mention a (somewhat lengthy) remark here (it's sort of a point extending off Michael's). I feel some of these questions on RG almost seem to blissfully focus on things like metaheuristics, and straight up ignore the reality that there's a rich theoretical way to discussing "approximately good answers" (or when a problem is "easier to solve", given some kind of real-world structure), such as the theory of approximation algorithms and multivariate analysis (e.g. parameterized complexity). This is not meant to disrespect those that find that work interesting, I just always find it an interesting coincidence.

I personally, as a computer scientist, would like (and challenge) supposed algorithms researchers to provide better guarantees (in relation to the optimum), that their proposed methods actually do what they claim. I'd like to see more papers that provide a contribution to better understand a problem (not just crudely throw together something that supposedly "solves" a problem). For example, the methods Michael Patriksson is discussing come from the richest kinds of optimization tools (especially when we're talking about anything from integer programming to beyond) we usually have at our disposal; sometimes they are so unbelievably broad and can capture all sorts of interesting problems. Furthermore, they often times tell us something (which is a contribution in itself) about the actual problem.

We have ways of talking about "how well" heuristics can and do perform for optimization problems, I really wish more would just take the time and learn more about it instead of just throwing anything at the wall and expecting it to make some kind of valuable contribution to our understanding of computation. I do think there can be value in heuristics work, should it be done "to the tee" and very well and not overstate its contributions; however, I'd like to see if some could really roll up their sleeves and not just plead ignorance to what they propose and throw out into the literature (unless it's a genuinely interesting research question, which will depend on the problem, even within approximation algorithms this can and does happen, e.g. an algorithm is proposed that if ran in poly-time would be the best-known approximation algorithm, but we don't know if the algorithm actually terminates in poly-time). It's true, sometimes methods just happen to work well and we don't know yet why, I'd love to see more really try to see "why" that might be as it might invite more discourse on it as a research problem.

It doesn't need to be "optimality" or not, you can still prove claims like "the algorithm produces feasible solutions that are within ____ times the optimal (always, should it exist)". Or perhaps, one could find some interesting parameter about the problem and show the method solves it quickly if that parameter is fixed (or perhaps even to optimality). It might be completely untrue that a method provides optimality, it could be that it actually only works well up to some point; I'd love to see more do the work necessary to make contributions that are things that won't just be some paper, but a paper that actually contributes to our understanding of a problem.

Agreeing with you Daniel Page :

Recently, I have received some good comments from Michael Patriksson regarding the implementation of mathematical optimization in complex problems in other discussions. As a Ph.D. candidate, I will try to write my proposal using powerful mathematical tools instead of those unreliable solutions. I will gradually leave metaheuristics.

I am surprised that a known scholar with a long experience in the transportation domain maintains such a hard stance on heuristic search. Obviously, we live in a world where extreme opinions are those which are the most echoed. Truth is, assuming that all practical optimization problems can be solved to optimality (or with approximation guarantees) is essentially wishful thinking. Given this state of art, better integration of exact and heuristic algorithms can largely benefit the research community. At the risk of repeating myself, here are some important remarks to consider:

• CPLEX and Gurobi (the current state of the art solvers for mixed integer programming optimization) rely on an army of internal heuristics for cut selection, branching, diving, polishing, etc... Without these heuristic components, optimal solutions could not be found for many problems of interest. CPLEX has even recently made a new release permitting a stronger heuristic emphasis (https://community.ibm.com/community/user/datascience/blogs/xavier-nodet1/2020/11/23/better-solutions-earlier-with-cplex-201). MIP solvers also heavily depend on the availability of good (heuristic) initial solutions to perform well. For many problems, cut separation is also done with heuristics. In the vehicle routing domain, we have a saying: heuristics are the methods that find the solutions, exact methods are those that finally permit to confirm that the heuristics were right (sometimes many decades later, and only for relatively small problems with a few hundred nodes despite over 60 years of research on mathematical models)...

• The machine learning domain is quickly taking over many applications that were previously done with optimization. Among the most popular methods, deep learning relies extensively on stochastic gradient descent and does not guarantee convergence to optimal parameters. Neural networks share the same issues as heuristics, but they have still led to notable breakthroughs. Decision-tree construction and random forests are largely based on greedy algorithms. The same holds for K-means (local improvement method), expectation-maximization, and many other popular learning models/algorithms.

• Even parameter tuning by the way is heuristic. Most design choices, even in the scientific domain, are heuristic and only qualify as good options through experimentation. Even the design of "exact methods" is in majority based on experimentation, as it is hard to determine beforehand which component, decomposition, or cut is going to pay off for a given application.

I find exact methods, heuristics, approximation algorithms and matheuristics all interesting. What I don't like is people claiming that their "drunk bat" or "intelligent oil slick" metaheuristic is new and exciting.

Dear professor Adam N. Letchford and Thibaut Vidal :

I am agreeing with you that these methods are all interesting. I am working on continuous optimization (structural optimization). I think that by the development of model-based methods (same as radial basis functions approximation) which is recently recommended by Michael Patriksson , for the problems with lack of knowledge, there would be no need for a heuristic!

Mathematical programming is preferred in problems in which the sensitivity is available. It works well even on the scale of one million design variables! For problems in which the analytical sensitivity is unavailable, we can use a model-based method or surrogate modeling to approximate the function and use mathematical programming. Also, the sensitivity can be predicted by machine learning! This is why I am getting agreed with Michael Patriksson.

I have started this discussion in the following link and I hope to have your interesting comments:

https://www.researchgate.net/post/The_improvement_of_model-based_methods_and_surrogate_modeling_kills_metaheuristics_in_continuous_optimization_What_do_you_think

I want to use my argument like this old question

https://www.researchgate.net/post/Who-will-achieve-success-in-life-more-a-clever-which-does-not-know-that-he-is-clever-or-a-fool-which-knows-that-he-is-fool

Who will achieve success in life more: a clever which does not know that he is clever, or a fool which knows that he is fool?

Behind this provocative question is the essence of the mathematical problem that I'm trying to solve, namely:

1. An algorithm that produces often good solutions, but it knows nothing about their quality, or

2. An algorithm that produces often bad solutions, but it has a quantitative metric of closeness to the optimal solution?

Which of these two algorithms should we trust more?

We often hear sayings:

1. "He is certainly an intelligent person, however he does not know his own price, and therefore everyone uses it for personal gain"

2. "He is certainly a stupid person, however he knows his own price to apply his poor knowledge in practice"

There is also the saying "if a fool realizes that he is a fool, he is no longer a fool".

I want to remind you of one hypothetical game.

There are two algorithms: the approximate algorithm A1 based on the metaheuristic and the approximate algorithm A2, which is capable of constructing a lower bound. The game consists in the fact that the customer pays a large sum of money to the one who proves that his approximate solution is close to the optimal solution with the measure (A (D) - OPT(D) / OPT(D)

Bravo! Very nice answer Gennady Fedulov !!

I have some experience in metaheuristics. You can find them in my profile (even some of them are under review!). But I will no longer want to continue in a non-scientific way. Also, the hybridization would be non-scientific. I am not afraid of changing my way. However, I think that methaheuristic can not be a reliable craft!

Thank you very much!!!

Dear Pooya Rostami,

I want to offer one slide that shows the properties of the future approximate solution as a passage inside the so-called "Estimation Corridor". This corridor is being built for the 1DBPP (One-Dimrnsional Bin Packing Problem) problem. Here Initial Approximate Solution is FFD (D) = 1259, trivial Lower Bound L0 (D) = 1127, Best Approximate Solution A (D) = 1169, Best Lower Bound L1 (D) = 1168. An approximate solution for a given number of containers will pass between the Upper Green Polyline and the Lower Red Polyline.

A simple explanation of the popularity of metaheuristics over rigorous mathematical methods can be given.

1. Metaheuristic Algorithms are very simple and easy to understand, the text of these algorithms is sometimes placed on a smartphone screen and young people like it a lot. Why read thick books on optimization methods when today's youth do not read thick books at all and this is a fact.

2. A modern test system for assessing knowledge, when several possible answers are offered to a question and you only need to guess the correct answer. There was such a funny case when young people in Latvia were asked the question "Who won the Second World War?" Young people answered with a question to the question "You name the participants, and we will try to guess".

In this regard, I see a direct connection between metaheuristics and trying to guess the correct answer.

Dear Dr. Gennady Fedulov :

That’s completely true. However, I think that the supervisors around the world had a bigger contribution to attracting young researchers in metaheuristics. In almost all of the universities around the world, some people are teaching optimization. In many of them, supervisors teach metaheuristics instead of the theory of optimality! This is where the problem starts!

Me and other young students should acknowledge people like you and Michael Patriksson for the guidance!

Dear Pooya Rostami,

If ever prof. Stefan Voss will answer you to your request, be sure to let us know and if there is nothing personal in his response to you, be sure to post in this thread. However, I am afraid this answer will go on for a long time, if not forever!

I might again take part in ventures that harbour heuristics - I am not that negative every day, you know - but the project shall preferably not be based on too much hand-waving, which I find metaheuristics too often to be. I would like a project on metaheuristics, if so, to also include a "check" - which is to find the optimum as well - and then evaluate whether the heuristic is fairly accurate or not. Something good might come out from that exercise, especially when working with a plethora of data. I apologise to those who thinks I am too harsh against heuristics, and I do know that we do depend on heuristics quite often. I should know as I have worked a lot with industry people.

Nice recommendation!

But I am sure that a person working in metaheuristics will not do this!

Consider a topology optimization problem with one million design variables. In 99 percent of single runs, the design would be not optimal. If he adds a ‘check’ in the algorithm, he proves that the method is always non-optimal and cannot obtain global optima. In other words, the algorithm will be proven to be inferior. Therefore, the research paper will be rejected.

Dear Gennady Fedulov :

Yet, I have received no reply from his side. I requested him to add his reply here. But if he adds something in private, I will try to export it right here. However, I have received my answer from you and others.

Dear Michael Patriksson,

"I would like a project on metaheuristics, if so, to also include a "check" - which is to find the optimum as well - and then evaluate whether the heuristic is fairly accurate or not. Something good might come out from that exercise."

You are absolutely right, because the optimization process reminds me of a bird with a fat body called "finding an optimal solution" and two wings, of which the right wing is "finding an effective approximate solution to OPT(D)", and the left wing is "finding an effective Lower Bound LB(D)", where LB(D) = "b + 1". So far this method has fully justified itself. Although there are many other more specialized methods for finding effective Lower Bound LB(D). For example, if it is proved that OPT(D) >= OPT(D'), then the problem is to reduce to the search for OPT(D') and this will be just a good Lower Bound to OPT(D) >= OPT(D').

Incidentally, such an association arises in connection with the search for a vaccine against coronavirus. Imagine OPT is the perfect COVID-19 vaccine. However, now the whole world is trying to find vaccines as a sequence of metaheuristic algorithms A1, A2, ... An. There are many similarities between the Ai, 1

Thanks Gennady and Pooya for bringing me into the loop. As usual, I waited a bit before interfering as I believe that many of the arguments that we see in this thread have already been made elsewhere (and not only once). Ok, the reason for waiting was different. Just shortly before your question came, we had a paper accepted for the journal Natural Computing called "Similarity in metaheuristics: a gentle step towards a comparison methodology" (https://doi.org/10.1007/s11047-020-09837-9). However the paper became online available only about one month later. We show that some (if not many) of the so-called [I hate this phrase but here it is correctly used] new analogy-from-nature-or-something-else-seeking metaheuristics popping up are not new. That is, whenever we speak about metaheuristics, we should have the real contenders in mind, not their copies. This makes it difficult and easy to discuss the given question "What do you think about improving metaheuristics using mathematical programming?" In case of the real contenders I think that it can be very beneficial.

So, let me start a bit more to come inside the discussion. We invented matheuristics as an area long time ago using the idea of model-based heuristics. and the idea was and is to bring together the good things from different worlds; see, e.g., our matheuristics book under DOI 10.1007/978-1-4419-1306-7 and the start of a conference series with Vittorio Maniezzo under http://astarte.csr.unibo.it/Matheuristics2006/. So, in my view, and we already have quite some evidence on that, hybridization, once properly done, is using the benefits of both methods. I often quote "no systems, no impact" to indicate that we only have an impact, if we are able to put our ideas into running systems. Of course, that still needs theoretical foundation, but it goes a step further. Whatever is really helping in solving real problems should be welcome. As an academic you should have the freedom to choose whether and which type of impact you want to have. And if a proper way of utilizing the interoperability of metaheuristics and mathematical programming in one way or the other is successful, that should be beneficial for both sides, academics as well as those seeking to solve real problems (especially under the burden of scarce ressources).

But, believe it or not, I am stating this without having a paper in mind that should be accepted or rejected. That is a different issue. And there are enough respectible outlets that will like papers if they are properly written doing both.

"Ein hab' ich noch!";-) Let me rephrase the question to get a different insight. What do you think about improving mathematical programming with metaheuristics? I love it. And it should show that we should love to utilize interoperability in either way to advance science and solving competencies. With Marco Caserta we had been working on this. Most of you might know the overall concepts of Bendesr decomposition (and Lagrange and Dantzig-Wolfe). Can we do it better? Can we do it faster? May be yes, and may be by utilizing metaheuristics and/or matheuristics. We have a paper on this in the International Journal of Production Research (why there? because of several reasons including the example that we used to support our argument). Accelerating mathematical programming techniques with the corridor method (DOI 10.1080/00207543.2020.1740343). Just a different view but again showing that interoperability (or call it hybridization)  can benefit both sides. And one can use it to solve problems.

Dear Stefan Voss,

You used the famous way of expressing your thoughts in your three posts and this method is often used by diplomats, namely: "To say about everything and don't say not about anything". So I still want to get direct answers from you to direct questions:

1. Is metaheuristics a science?

2. Is metaheuristics a craft, although perhaps a good craft?

As Descartes said, "Enter the correct notions and you will solve half the problem".

Whenever we speak about metaheuristics, we should have the real contenders in mind (think about early examples like different versions of tabu search, simulated annealing etc.). Developing these real contenders can be an art and can utilize a lot of good craftsmanship. And, yes, this belongs to the realm of science. But, as stated earlier, it can go wrong and then we might loose our way. Let's try to avoid that.

Just re-proposing existing metaheuristics under new fancy names to solve all kinds of discrete and continuous optimization problems (or not) is not what we should want. But if we want to gain insights into specific components of metaheuristics and understanding why and where they work well and how they need to be put together. That is what we should need ...

Dear Stefan Voss,

With a certain periodicity, we can see the birth of new metaheuristic algorithms

https://www.researchgate.net/post/List-of-metaheuristics-algorithms

However, there is a good correlation between Metaheuristics and the Test, which is the foundation of modern education. The test is a list of answers to the question posed, and schoolchildren (students) do need to guess the correct answer. I remember a funny incident when young people in one country were asked: Who won WW2? The young people answered: You name the participants in this war, and we will try to guess the name of the winner. So, the metaheuristic algorithm (MA) produces some solution A(D), but MA does not know anything about the degree of closeness of this solution to the optimal solution OPT(D), where D is the initial data. The fact that MA guessed the optimal solution indicates that the student guessed the correct answer from the list of alternative answers given in the test. Yes, the solution is named correctly, but MA does not know that this solution is optimal or close to optimal. This is why metaheuristics is so popular with young people, because why read thick books on Combinatorial Optimization when a half-page MA text fits well on the screen of any Iphone. I am waiting for a moment when finally the main focus will be on finding effective Lower Bound (LB) within a given Time Limit, LB(D)