Are you sure that optimization problems can be solved by heuristic techniques? Try to solve only an instance of the knapsack problem using heuristic methods. You will see a wrong answer almost always. My point is that heuristic is not a solution, but an easy way to produce fast answers with no guarantee. Mathematical Programming is, actually, a problem like SAT, Knapsack, Bin Packing, ... When you know how to convert your original problem into a mathematical programming problem, you will have many exact methods to solve it.

It depends upon the problem. Nowadays meta-heuristic techniques like PSO, ANT COLONY, GSA, etc. are widely applied.

Alexandre Frias Faria, thank you very much, sometimes we get the exact solution using heuristic methods or metaheuristic algorithms but do we always get the exact solution using mathematical programming? And if this is true, why do we use metaheuristic techniques?

S. B. Singh, Thank you, What are the factors that determine whether to use mathematical programming meta-heuristic techniques?

There is no thumb rule as such. However complex problems are more often solved with Meta-heuristic. However for Meta-heuristic, you programming needs to be good.

i'm using Wolfram Alpha, sometimes, write in Google : solve ....... online to see some algorithms or apps

El-Sayed Badr,

When you find an exact solution using heuristic or metaheuristic algorithms, how do you verify or prove the optimality? I think it is possible only in some cases. About mathematical programming, if the original problem was converted correctly to a mathematical programming problem, it is possible to use the whole tools from the theory to solve it. For example, mixed-integer linear programming is a well-solved problem and it is easy for modern solvers. Despite that, general continuous programming can be hard. The majority of the books cover the theory over integer, linear or quadratic, programming problems.

"why do we use metaheuristic techniques?"

It is a good question. I do not know. We need the help of a more experienced researcher here.

This question about when to use meta/heuristics or mathematical programming is totally related to the complexity of the problem that you are solving. If it is a NP-Hard problem, then you can probably find good solutions in a reasonable time by using an efficient metaheuristic (but with no optimality guarantee). At the same time, mathematical programming models can take days to solve the same problem and give the optimal solution. That's why meta/heuristics are applied and very useful. On the other side, when the problem you are dealing with is not 'hard', then you can use mathematical programming tools to solve it optimally without spending much time on the resolution. And in this case meta/heuristics are not so useful.

I think that there are three ways to measure how "good" an optimisation algorithm is: (i) the quality of the solutions it finds, (ii) the amount of computing time and memory it needs, and (iii) the ease of implementation. Exact methods will obviously beat heuristics according to the first measure. But heuristics can sometimes beat exact methods according to the other measures.

By the way, it does not have to be "either-or". For a minimisation problem, it is sometimes useful to use a heuristic to get an upper bound, and solve some kind of relaxation to get a lower bound. It is also possible to combine exact and heuristic methods (see the books on "matheuristics"). Finally, check out "approximation algorithms", which are heuristics that give a guarantee on the quality of the solutions.

El-Sayed Badr your doubt is only natural. Having too many heuristics and exact methods for optimization problems also helps in that.

The most widely accepted answer to that is "it depends". It depends on the problem at hand, the knowledge you have on the problem, the computational means you have, the time you want to spend developing and waiting for an answer, instance size, and so on.

Adam N. Letchford brilliantly told you the 101 on that debate. And, in fact, for most problems, it is common to use both approaches, as one can certainly benefit from the other, being it directly (as in matheuristics) or indirectly (simply by generating a duality bound to compare your heuristic primal bound).

Also, heuristics come with an inner problem called parametrization, as it is itself an optimization problem. As more complex is the heuristic, more parameters you have to tune in so it can be a better approximation to your optimum (with no guarantee whatsoever).

Thanks to everyone ( Adam N. Letchford, Sávio Dias, Diego Martino, Alexandre Frias Faria, Sofyane Bouameur, and S. B. Singh)

I understand that, from a computational comparison between the approach of mathematical programming and the heuristic approach, we will find that the metaheuristic approach is superior to the approach of mathematical programming in terms of running time, On the other hand, the approach of mathematical programming is superior to the metaheuristic approach in terms of accuracy.

Both, depending on the problem that you want to solve.

Generally you might use:

1. exact method - this should guarantee an optimal solution. Unfortunately for many hard optimization problems, e.g. NP-hard or NPO, efficient exact methods are unknown or impossible. For NP-hard problems (that are not very small in size) exact method could give you optimal solution but you might have to wait e.g. 1000000 years for a supercomputer to give you that solution. Is there any possibility that efficient exact method for solving any NP-hard problem could exist is a very important unanswered theoretical question.

2. Metaheuristics or heuristics - they might give you a very good solution, near-optimal or optimal, in some reasonable time e.g. seconds, minutes, hours or days. Metaheuristics are often nature-inspired, usually have some learning mechanism - they learn about the problem instance they are solving. When you provide more time (more computational resources) you might get a better solution.

3. Approximation methods are approximate methods that have error bounds - in a reasonable time you get some solution within known error bounds. (Although error could be very large.)

For hard problems that exact methods cannot solve at all in a reasonable time, we usually use metaheuristics. Although approximation methods have error bounds and metaheuristics don't, metaheuristics often give better solutions.

In minimization problems, mathematical techniques may yield to local minimum solutions, meta-heuristics methods find the global minimum solution in optimization problems better than other techniques.

The fact is that most (and probably all!) metaheuristics do not have sufficient focus on minimising the objective function, and staying feasible, and that is due to the rigid form that these methods need to follow. There are global solvers that work, as long as the functions involved are Lipschitz continuous. If you need to solve a non-convex problem, you will be happier with them, than with any meta thing you throw in.

Meta-heuristics can solve any problem, but not every problem can be solved by mathematical programming.

It is not rue that metaheuristics are always faster than mathematical programming techniques. Evolutionary algorithms, simulated annealing, neural networks, etc. require a huge number of computations and comparisons to arrive at a good solution. For easy problems such as network flows, it would be crazy to use any metaheuristic algorithm because you can find a guaranteed optimal solution faster than any of them, whereas metaheuristics cannot even guarantee optimality. I have seen papers demonstrating metaheuristic algorithms on very easy problems like the shortest path, maximum flow, etc., which is ridiculous. Metaheuristics should only be used for solving very hard problems. Even then, a mathematical programming approach may still be competitive in terms of solution quality (when terminated early). Also, you often get some sort of an optimality gap with a mathematical programming approach, which is not available with most metaheuristics.

Joao Luiz Junho Pereira I think you will have a very, very hard time convincing any mathematical programming expert that you are right ... and for a very simple reason: that you are wrong. :-)

Mathematical programming is a robust machine - if I may say so - and it is robust because the theory behind it is robust. Your metaheuristic surely are very quick to converge, but it doesn't have a focus like mathematical programming has - metaheuristics are bound by their too simple rules.

You see - mathematical programming algorithms are built from the theory of optimality in mathematical optimisation - and therefore our methods are made such that, step by step, we get closer to an optimum in some measure. The basics of metaheuristics are not sufficiently tied to the theory of optimality - in fact there is very little theory built around them at all, except fireflies and worms.

The wiki page on these methods says this on the subject of metaheuristics: "While the field also features high-quality research, many of the publications have been of poor quality; flaws include vagueness, lack of conceptual elaboration, poor experiments, and ignorance of previous literature.

So there you go. Lots of screaming - little success.

Michael Patriksson , in times of so much denial of science that we see in relation to a pandemic, it is sad to see the same happening within a group of researchers. Classic optimization methods had their importance in the past, but have been replaced by powerful meta-heuristics. Which will become even more so with the computational advance we are having. It's very rude to say that an algorithm doesn't guarantee optimality just because it doesn't calculate that the gradient at that point is null. Engineering has developed a lot using finite element analysis software from any area linked to meta-heuristics. In this way it is possible to make optimizations without even having equations. How would a classic method do it? Furthermore, it has many problems that are only possible to find solutions with a tremendous and intelligent combinations, that only metaheuristics can find. For example, Feature Selection.

It's not the first time I've seen you belittling meta-heuristics to generate controversial posts. I believe that as researcher, you should respect all areas, including those you don't doctor.

Big hug and focus on what's important! Don't deny the future!

Kindly refer to this:

S. Sharma, R. Kapoor and S. Dhiman, "A Novel Hybrid Metaheuristic Based on Augmented Grey Wolf Optimizer and Cuckoo Search for Global Optimization,"2021 2nd International Conference on Secure Cyber Computing and Communications (ICSCCC), 2021, pp. 376-381, doi: 10.1109/ICSCCC51823.2021.9478142.

Or refer to the same paper at the following address:

https://www.researchgate.net/publication/353403100_A_Novel_Hybrid_Metaheuristic_Based_on_Augmented_Grey_Wolf_Optimizer_and_Cuckoo_Search_for_Global_Optimization

The only advantage of using metaheuristics is that they can find some solutions (of varying quality, with no guarantees of how good they might be) to difficult problems that are normally intractable using mathematical programming techniques. If a problem is solvable by mathematical programming techniques, there is no need for metaheuristics. Unfortunately, in the literature, there are numerous papers that demonstrate the effectiveness of various metaheuristics on extremely simple problems such as the shortest path or maximum flow. You can even solve these problems by hand, on a piece of paper with a pencil. It is ridiculous to use them to show the effectiveness of metaheuristics. To be of any use, metaheuristics need to be applied to very difficult problems for which even finding a feasible solution is a challenge. That's where the value of metaheuristics lies.

Joao Luiz Junho Pereira "It's very rude to say that an algorithm doesn't guarantee optimality just because it doesn't calculate that the gradient at that point is null."

Well... it's precisely the definition of a guarantee of local optimality, isn't it?

I'm familiar with both mathematical programming techniques and metaheuristics (I combined both in my PhD work and now do research on both local and global optimization methods), so I have enough perspective to state that:

- mathematical methods provide *strong* guarantees:

1) local methods come with a *proof* of local optimality (we reach a stationary point) and usually a *proof* of global convergence (it doesn't matter where we start). Besides, they can often detect local or global infeasibility, and converge with a point that minimizes the constraint violation ;

2) global methods perform an exhaustive exploration of the search space and iteratively improve lower and upper bounds on the optimum, until the gap is smaller than the tolerance. They find the global optimum and *prove* its global optimality ;

- metaheuristics work well in practice on numerous (small-scale) examples, especially when the problem is nonconvex (we often say that they're equipped with mechanisms that help escape local optima). However, they give zero guarantee. No guarantee of local optimality (let alone of global optimality) and no guarantee of convergence towards an optimum. So it's basically down to luck. It works well on your example? Good for you!

At *no* point have metaheuristics replaced mathematical programming techniques for efficiently solving large-scale problems. Metaheuristics should be the last resort when you can't use any other technique. Doesn't mean they're bad, it just means that you can often use much better techniques for a given problem.

I recently started a cooperation with optical designers who actually use metaheuristics to design optical systems. But that's because:

- they use optical simulation as a black box, although the analytical equations are perfectly well known ;

- they don't know how to use methods for constrained optimization (maybe they don't know that such methods exist altogether) and they end up relaxing the constraints in the objective function.

Charlie Vanaret

(point where gradient is null) "....it's precisely the definition of a guarantee of local optimally..."

- Well, not really. If I am not mistaken, this is only true in the special case when gradient exist and it is not the point of inflection.

There is a really large class of practically important problems, NP-hard, for which there is no mathematical programming method that can be used for getting optimal solutions.

Nikola Ivkovic true, you need also second-order characterizations (the problem should be locally convex).

A class of really hard problems are discrete problems. In this case, you can't solve directly using derivatives (and the first- and second-order optimality conditions do not hold). Exhaustive methods often relax the integrity constraints to get a lower bound, so you actually end up invoking continuous optimization methods.

@Nikola wrote: "There is a really large class of practically important problems, NP-hard, for which there is no mathematical programming method that can be used for getting optimal solutions."

This is completely untrue. People have been solving NP-hard problems since the 1950s! Just look at the work of Egon Balas, Manfred Padberg or Laurence Wolsey.

If a problem is NP-hard, it means (assuming that P != NP) that exact algorithms will take exponential time in the *worst case*. There is no reason to expect that instances arising in practice will be worst-case instances.

@Adam N. Letchford

If what I said is untrue, why don't you tell us at least one NP-hard problem for which there is a mathematical programming technique that can guarantee to find optimal solution in reasonable time.

Oh well, if you do know the technique, I think you would be able to collect $1000000 prize from Clay Mathematics Institute for proving that P=NP.

Of course, some instances of NP-hard problems can be easy to solve, but we are talking about problems in general.

For some NP problems, most of the instances are hard to solve. Asymmetric cryptography works this way, the simplest example would be RSA.

Yes, people are "solving" NP-hard problems for decades by using metaheuristics and specially tailored heuristics, but usually we cannot prove that those solutions are optimal. Sometimes those solutions are optimal, sometimes very good but suboptimal, and sometimes not so good.

@Adam N. Letchford

(part 2)

Of course, mathematical programming has its value.

As I wrote in an earlier post, exact, heuristic and approximation methods each have their practical value and which is better depends on use case/situation.

I just think it is not fair and not true to say that mathematical programming is superior and guarantee optimal solutions and that metaheuristics are inferior, like some people in this forum are saying.

I would also like to add that people sometimes get confused about scientific research vs. practical application. Sometimes we might investigate the behavior of metaheuristics based algorithm on problems for which there are excellent exact methods. -There are good scientific reasons to do that kind of research.

Nikola Ivkovic : Our views may be closer than you think. I believe that both exact and heuristic approaches are valuable. Here is my own version of your paragraph:

Many optimisation problems arising in practical applications are "NP-hard". According to a widely-held conjecture, there is no algorithm that can solve all instances of an NP-hard problem exactly in reasonable computing times. Fortunately, instances arising in practice can often be solved to proven optimality using mathematical programming techniques (such as branch-and-cut and branch-and-price). For instances that are too difficult for exact methods, one can use heuristic methods (such as simulated annealing and tabu search).

I see many words and most represent convictions and not facts. The best guarantee of optimum is an f(a)

Joao Luiz Junho Pereira I understand your point.

In this case, what you mention is not a *guarantee*. You can coin a new word, but this particular word means something else ;)

See Chapter 7 (and also part of Chapter 1) in this book for a discussion on this:

https://www.researchgate.net/publication/352413464_Engineering_Design_Optimization

All of exact, approximate, parameterized, randomized, and heuristic algorithms all have their places, for different reasons. For example, heuristics are valuable in settings where we just want stuff that works "well enough", and sometimes can yield surprisingly effective approaches that later on are confirmed by theory to actually be approximation algorithms. However, I must stress, like some others have here, there is a pretty vast subset of research that isn't anything resembling this (and if anything, it makes good heuristics research look bad), and at best provides hammer and nail approaches to problem solving, as opposed to actually studying a problem. These I don't believe, in many circumstances, provide insight from a Computer Science perspective for fundamental aspects of a problem; this is largely because they remain heavily disconnected from the problems themselves.

For me, if it doesn't tell me anything about how close answers are to the optimum in some way, shape, or form, it's mostly inapplicable to the kinds of things I'm interested in, proving claims about algorithms. If it can't guarantee anything, it's not good enough for me. I need to be able to assure people something in my research performs as well as I actually claim it does, in very exact terms. But I understand some people aren't like this. I want to know fundamental things about the problems and their relationships with algorithms, for instance, about limitations of solving certain optimization problems based on complexity-theoretic assumptions.

What's better for me? Well if you told me I can only pick one or the other, I'll go with the ones that guarantee results for me, the mathematical programming approaches. Many approximation algorithms (a lot in my circles) employ mathematical programming to some degree, to yield nice bounds often (but not always) on optimal answers (including in classic circumstances, such as for LP-relaxations). Metaheuristics lack all of these features, and typically are inapplicable to the kind of research I do, unless I step away from my fundamental goals (as described above) and just want to see what happens (which is fine to do, but it's hardly the same degree of rigour I'd expect in my Algorithms research). Different researchers can work at different rungs of standards, some are more restrictive than others; however, by getting less restrictive, you will have harder times demonstrating results that are more fundamental to areas relating to optimization and algorithms.

El-Sayed Badr I hope multicriteria optimization and variational mechanics problems are included in the discussion.

The problem is by what criteria to evaluate the heuristics proposed for publication. In my opinion, heuristic authors should be asked (or required) to provide examples on which their algorithm fails.

A reader like me wants to know that "worst case.")) It's not always obvious.

One way to answer the question would be to pick a mathematical programming technique and a metaheuristic technique and comprae the two. Then continue with another mathematical programming technique and a metaheursitic technique and compare again. And so on.

Let me start the comparison with the following proposal and questions:

Proposal

The Two-Phase Method, a Mathematical Programming Technique, can be used to find a feasible solution to the linear constraint system of a Linear Programming problem (4.2 The Two-Phase Method, pp. 154 - 165, Bazaraa, 2010). I propose this as the initial technique for comparison with a metaheuristic technique.

In the worst case the Simplex Method can take an exponential number of steps to find an optimal solution (8.2 Complexity of the Simplex Algorithm, pp. 397-401, Bazaraa, 2010). Thus in theory it can also take an exponential number steps in the Two-Phase Method in finding a solution to the linear constraint system of the Linear Programming problem.

However "the linear program to minimize cx subject to Ax < b with integer data can be solved in a number of elementary arithmetic operations bounded by a polynomial in the size of A alone. Hence, network structured problems, for example, admit genuinely or strongly polynomial algorithms" (as cited on p. 449 of Notes and References 6, Bazaraa, 2010).

Furthermore "researchers were pleasantly surprised when, in practice, this method performed exceedingly well. For most practical problems, this method has been empirically observed to take roughly 3m/2 iterations, and seldom more than 3m iterations, where the coefficient matrix A is m x n" (p. 397, Bazaraa, 2010).

Questions

Can someone propose a metaheuristic technique for finding a solution to the linear constraint system of a Linear Programming problem? In theory or in the worst case how many steps does the selected metaheuristic method take to find a solution to the linear constraint system of the linear programming problem? How about in practice?

References

Bazaraa, M. S.; Jarvis, J. J; and Sherali, H. D. (2010). Linear Programming and Network Flows [electronic edition]. Hoboken, NJ: John Wiley & Sons.

Mathematical Optimization. (2021). . (Sep. 10, 2021).

Metaheuristic. (2021). . (Sep. 10, 20201).

In my opinion, they are complementary methods. For two main reasons: (i) most real (large-scale) problems are intractable using exact algorithms and; (ii) on the other hand, even for small instances, heuristics (meta, hyper, math - heuristics ) can not provide an optimality guarantee (or optimality gap). So that, firstly, you should provide algorithmic performance metrics comparing both approaches, and for real cases (large instances), you probably have to apply validated heuristics. Obviously, there are models that can be solved by exact approaches (e.g., decompositions or B&B family) easily, in these scenarios you can avoid heuristics.

Francisco Pérez-Galarce : good point.

An option is also to combine them to accelerate convergence and find satisfactory solutions faster. See my thesis for example: Thesis Hybridization of interval methods and evolutionary algorithm...

If an exact method doesn't solve the problem in reasonable time, you have to use heuristics. The question is not that which one is better, the answer is obvious: an exact method is superior to any heuristic in terms of solution quality. The question is which heuristic is better than others, for those problems that are not solvable by exact methods. This of course, depends on the problem type and problem size. What works on one problem may perform terribly on another completely different problem.

@Cenk Çalışkan "If an exact method doesn't solve the problem in reasonable time, you have to use [fast] heuristics" and [an iterative procedure to improve the heuristic solution]. The heuristic gives the first approximation of the solution, no more.

The problem clustering you proposed is an independent task, usually with varying success, and difficult to evaluate.

Why meta heuristic is important? Please explain

DEAR El-Sayed Badr

The main advantage of adopting a heuristic approach is that it offers a quick solution, which is easy to understand and implement. Heuristic algorithms are practical, serving as fast and feasible short-term solutions to planning and scheduling problems.

They often provide quick solutions. Disadvantage - This May sometimes lead to errors.

Chapter Metaheuristic Techniques for Test Case Generation: A Review

GOOD LUCK

It's difficult to say. Although mathematical programming techniques offer exact solutions to problems, they are often problem dependent, i.e., a method that works for one optimization task (traveling salesperson problem, for example) might not work for another. Also, the computational effort involved in the exact-solution methodologies are often very expensive.

Meta-heuristics, however, have the advantage of not being problem specific and are therefore global optimization algorithms. My advice is to use mathematical techniques whenever an exact solution is possible, no matter how cumbersome the computations turn out, and use meta-heuristics for the rest of the problems that don't have solutions

Good Luck.

https://www.sciencedirect.com/science/article/abs/pii/S0378779621002534

https://www.sciencedirect.com/science/article/abs/pii/S0378779621002534

This is like asking what is better, hammer or screwdriver.

If you want to solve some particular problem, then it depends on what kind of problem you have.

Generally we use metaheuristics when there is no exact method that can be used to solve the problem in reasonable time. ("there is no exact method" = it is not known or it cannot exist.)

The other thing is if you want to do scientific research . In that case, e.g. you might want to find a good method for some hard problem or you want to investigate behaviour of metaheuristics based algorithm. Whan you investigate the behaviour of the algorithm you might use very simple problems that would be possible to solve exactly in short time.

Dear Sirs. The so-called metaheuristics has to do with psychology, not mathematics. It is an example of the "law of small numbers"/"strong law of small numbers" or "gambler's fallacy". https://en.wikipedia.org/wiki/Strong_law_of_small_numbers

In other words, comparing two metaheuristics, or saying "my metaheuristic is better" is not verifiable and cannot be verified, regardless of the tests done.

https://www.sciencedirect.com/science/article/abs/pii/S0378779621002534