certainly those that cannot be formulated mathematically

With respecting with the first question, metaheuristics can be applied to solve any optimization problem if we define correctly the equivalence between the parameters involved in the optimization problem, i.e., decision variables, with the parameters modified by the metaheuristics, by example, the chromosomes in evolutionary algorithms, or the particles or agents in swarm intelligence algorithms. If the problem involves a set of constraints, diverse approaches exist to include them in any metaheuristic—the same with a multi-objective or combinatorial optimization problem.

On the other hand, using metaheuristics to solve any decision problem does not imply to modify the decision problem since only we define the mapping scheme between decision variables and metaheuristic variables. In some cases, the disturb operators used in any metaheuristics should be modified to guarantee to generate feasible solutions, or some repair method inside the metaheuristic internal process should be defined.

Best regards

I think we need to distinguish the two. A heuristic, I think, refers to a very simple methodology whose purpose is to quickly find a feasible solution for a particular problem setting; it is typically devised for one particular model set-up. Typically it is of the greedy sort, which means that if a variable has been assigned a value, it will not be adjusted.

A metaheuristic is more general; it allows a procedure to change the value of a variable that has been assigned earlier, but it is not as general as a mathematical optimisation methodology: it is still not based on the goal to fulfill all optimality conditions for the problem. For example, there is no method for producing an optimal solution to the TSP (travelling salesperson problem) other than branch-and-bound-type and cutting-plane schemes.

Heuristics are intuitive ways to solve an optimization problem. They are not guaranteed to produce the optimal result. If the problem is to find out if a melon is ripe without cutting it open, there is a heuristic solution for the problem, namely, to smell the melon. This may not always work, but will work most of the times. It should be possible to come up with some heuristic for any optimization problem.

But you will then never know how good or bad the output was, and I for one despise non-optimal solutions. I will therefore tend not to use heuristics, if I can avoid them.

What I instead would do is to try to find a structure in the problem that I can take advantage from, in order to produce at least a good feasible solution, in tandem with a lower bound that is as high as I can; the best lower bound will tell me how bad my feasible solution is, and hopefully it is good enough. If not, maybe I might enrich the formulation by adding cutting planes, or something else in my toolbox.

Using mathematical optimisation is typically vastly better than a metaheuristic, as in the world of mathematical optimisation we have access to convergent methods, based on criteria on optimality, while metaheuristics can not exploit structure in the problem.

The general answer to the question "What are the types of optimization problems that can't be solved with meta-heuristic and heuristic algorithms?" is - in fact - ALL problems, except perhaps those that are equivalent to the greedy method, and I'm not sure about those, either!

There are a few theorems that tell us how close to the optimum a finite procedure can reach, but only for special problems; we call them approximation schemes.

A potential add-on to be discussed is - of course - some local search technique started from the place where the meta-heuristic stopped; if it is not too costly to calculate objective values and make sure that the result from it is feasible, you may gain even more. Although you have no guarantees, you may be lucky!

Thanks Prof. Michael Patriksson for your insightful answers.

So assuming that we were lucky and the meta-heuristic/heuristic method yielded a feasible point, this feasible point could be close or far away from the global optimum (assuming the function in question has only one global solution) but it is still a feasible point so we can use mathematical optimization methods from there and we are sure that it will eventually converge to the optimum.

But if I may ask, I have two questions:

1- In your comment, you are saying "some local search techniques" so, why not all the local search techniques?

As I understand by a local optimization method, we must choose the initial point that is close to the optimum and the method then collects local information at that initial point and then by applying some deterministic rules, it outputs a new iterate. If we let the process continue indefinitely the sequence of iterates will converge eventually to the optimum.

2- What are other methods people generally use to generate an initial guess in order to use local methods? I think one answer would be global methods? like the line-search methods? like using the bisection method for few iterations to generate an initial point and then use other local faster method assuming we are dealing with unconstrained optimization problem f:R \to R but even if we do, how can we know if we are sufficiently close to the optimum and then decide to use a local method?

Thank you :)

First, you will need to utilise a methodology based on global optimisation, in order to be certain that you can find it, and furthermore you need to get hold of a measure of the Lipschitz constant of the problem - that is the only way to be able to use subproblems based on mathematical optimisation - as you need to discover a variety of bounds on the problem. There are ways to derive estimates of the Lipschitz constant, and from that utilise a type of tree search (i.e., branch-and-bound-like stuff). That has been pretty successful, as not all global optimisation problems are very hard.

what is your problem?

The change propagation models may give a great idea

certainly those that cannot be formulated mathematically

Sometimes optimization isn't no vital, please remember Karp's 21 NP-complete problems due to S. Johnson.

In this type of problem, it's quite enough to measure the worst case complexity and propose optimal way of solution accordingly.