7
$\begingroup$

I have been trying to find examples of major research studies examining the properties and performance of the "Branch and Bound" Algorithm compared to "Evolutionary Algorithms".

For instance, in terms of popular types of mixed integer programming and combinatorics optimization problems (e.g. scheduling, knapsack problem, traveling salesman problem, etc.), have we developed any common consensus on "Branch and Bound" vs "Evolutionary Algorithms"?

It would be very interesting to learn more about which of these two types of algorithms (Branch and Bound vs Evolutionary Algorithms) are preferred in the Operations Research Industry for solving different types of mixed integer programming and combinatorics optimization problems. Perhaps there might be some tradeoffs, for example:

  • Branch and Bound works better when the search space is bigger
  • Evolutionary Algorithms take less time to run
Improve this question
$\endgroup$
3
  • $\begingroup$ Actually, I do not know what you mean by the properties and performance of the "Branch and Bound" Algorithm compared to "Evolutionary Algorithms"?. But almost in all the papers related to OR/MS that used from an evolutionary, (meta) heuristics algorithm, the performance of those have been compared with an exact solution like B&B to understand how those results treat in the large scale model. $\endgroup$
    – A.Omidi
    Feb 2, 2022 at 10:09
  • 1
    $\begingroup$ Related question: or.stackexchange.com/questions/7588/… $\endgroup$
    – fontanf
    Feb 2, 2022 at 10:27
  • $\begingroup$ Related reading: yetanothermathprogrammingconsultant.blogspot.com/2022/01/… $\endgroup$
    – Shibaprasadb
    Feb 7, 2022 at 9:46

1 Answer 1

Reset to default
10
$\begingroup$

First of all, evolutionary algorithms do not solve optimisation problems. They provide feasible solutions (if you are lucky) often with no measure of the quality of the solution returned - hence they are heuristics.

Branch and bound algorithms on the other hand solves your optimisation problem (given enough time to massage the problem). If you terminate the branch and bound code early you will usually have a measure of the quality of the best known solution as branch and bound algorithms maintain information on global upper and lower bounds.

Hence, I would argue, that evolutionary algorithms can be a "go to" if

  1. You are in a hurry and you cannot wait for a branch and bound algorithm to terminate.
  2. You are more interested in a solution than an optimal solution.
  3. You cannot afford a good branch and bound based solver or you do not want to code one for your particular problem.

That said, there may be many other (meta-) heuristics that would work just as well as an evolutionary algorithm on your problem. Even some that might be significantly easier to code.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you! This is a very interesting point! Branch and Bound provides exact solutions, but takes much longer! $\endgroup$
    – stats_noob
    Feb 2, 2022 at 16:10
  • $\begingroup$ Sometimes branch and bound takes longer. Sometimes it will be faster. I might be biased, but I always try a MIP model + a good solver, before I go into the world of heuristics. If you can obtain an optimal solution fast enough, why bother with coding a heuristic? $\endgroup$
    – Sune
    Feb 2, 2022 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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