9
$\begingroup$

Are there any rules of thumb for when to use classical methods like branch and bound, branch and cut, etc...for non-convex problems, vs using meta-heuristic methods like genetic algorithms, evolutionary algorithms, simulated annealing, etc....?

When both classes of algorithms are applicable, what are the main trade-offs between the two?

$\endgroup$
3
$\begingroup$

Glover and Sörensen (2015)

Metaheuristics have been demonstrated by the scientific community to be a viable, and often superior, alternative to more traditional (exact) methods of mixed-integer optimization such as branch and bound and dynamic programming. Especially for complicated problems or large problem instances, metaheuristics are often able to offer a better trade-off between solution quality and computing time.

Moreover, metaheuristics are more flexible than exact methods in two important ways. First, because metaheuristic frameworks are defined in general terms, metaheuristic algorithms can be adapted to fit the needs of most real-life optimization problems in terms of expected solution quality and allowed computing time, which can vary greatly across different problems and different situations.

Secondly, metaheuristics do not put any demands on the formulation of the optimization problem (like requiring constraints or objective functions to be expressed as linear functions of the decision variables). However, this flexibility comes at the cost of requiring considerable problem-specific adaptation to achieve good performance.


Reference

[1] Glover, F., Sörensen, K. (2015). Metaheuristics. Scholarpedia. 10(4):6532.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.