If we could find a mathematical model for each optimization problem, could mathematical programming replace meta-heuristic algorithms?
Most probably "Yes." In fact we already now know how to beat meta-heuristics: most problems that arise in industry can be formulated as a mathematical program, and provide better solutions than any meta-heuristic - first of all because meta-heuristics cannot find an optimum. In rather many applications mathematical optimisation tools are also very efficient.
I am not sure I understand the premise of the question.
(1) If one does not have a mathematical model of an optimization problem, can we actually call it that? and
(2) How would meta-heuristics help in this case?
I imagine that to use a meta-heuristic for optimization, one would need at the very least a black-box, which takes values from some set and produces elements in a totally ordered set. In mathematical language, such black box is a function, and I would call this a mathematical model of one's problem. There are optimization algorithms that rely only on function values; see for example the relevant chapter in Nocedal&Wright's textbook (Chapter Derivative-Free Optimization
).
Dear Prof. Dr. Michael Patriksson
I agree with you for several reasons from my point of view:
1- Mathematical programming gets the exact solution, but metaheuristic algorithms get an approximate solution.
2- The running time of solution obtained by mathematical programming is often less than the running time of solution obtained by heuristic algorithms (from my experience to solve some optimization problems)
On the other hand, there are two challenges, the first how to formulate real-life problems as a mathematical model and the other is how to solve such mathematical models, for example, simple mathematical programming models can be used software package (Matlab, Python, Lingo, Ceplex,...) to solve them if they do not contain the absolute value while you need special treatment before using such software.
Generally, we need many comparisons between them to show which one is better.
Prof. Dr. Michael Patriksson Thank you very much because you gave me confidence to do a lot of practical experiments between them.
When you build your model as a mathematical model, you should first try mathematical programming methods to optimize it. If it is not a mathematical model, then it has to be at least a collection of mathematical sub-models, otherwise how can you think of optimization? If it is a mathematical model, but it is not a mathematical programming model, you can still use mathematical optimization methods. Only if the problem is intractable or very hard to solve using optimization algorithms, then you should consider metaheuristics. If you need reasonable solutions quickly, that is where the need for heuristics arises.
Just to avoid any confusion, both, mathematical programming and metaheuristics can, of course, find the optimal solution for a problem.
With metaheuristics, however, you might also obtain clearly suboptimal solutions, without always having the means to gauge the distance to the optimum. On the other hand, having a mathematical formulation, doesn't grant that you can solve the underlying problem within practically motivated time limits.
So you might be left walking in the dark but sometimes you may still have to and be able to reach your goal that way.
It's highly unlikely that a (meta)-heuristic can even get close to the optimum - and that has been seen hundreds of times over the years. Can't you just face it - metaheuristics are not worthy of trying if we have a crisp math model to solve.
Dear Michael Patriksson
I agree with you, but in the attached paper, I proposed a mathematical model for the radio k-coloring problem of graphs, but when solving it, it cannot reach the exact solution, but by setting an upper bound for it, what can you explain to this problem? (Figure 7 at the enclosed paper)
I am not sure now with the different data and uncertainties that we have, it is easy to have a mathematical problem for each problem that take into consideration the different factors. Metaheuristics could be then a practical approach to get good results quickly. Also, the hybridization of both is much useful, but the replacement I am not sure it is practical. This is just a question and I am not qualify to affirm this.
Meta-heuristic are applicable for non-deterministic problems. Here you don't know the global best solution but have a fitness criteria. Heuristics are also applied instead of meta-heuristics but huge search space cannot be explored by a greedy deterministic approach.
Most definitely. But there's always this beauty in having an all-encompassing global optimization methodology that is able to tackle any problem, regardless of size or complexity. I know some may attack meta-heuristics on the premise of its simplicity and occasional subpar performance, but I think there will always be a need for computational speed over solution quality, as in the case of autonomous robotics. Sometimes exact solutions to all problems in real-time is just not possible.
- Badges
- Science topic
- Similar topics
- Filing