Does gurobi use Genetic algorithm or ant colony algorithm?

Answered

Parijat Mitra

• May 21, 2021 16:07

Hi, 

As I know gourbi use branch and bound algorithm to solve problems. I was wondering does gourbi use genetic algorithm or ant colony algorithm to find solution to the problems?

 

0

• 

  Alison Cozad

  Gurobi Staff

  • June 03, 2021 14:42
  • Edited

  One of the key ways to differentiate optimization solvers is whether they are derivative-free (DFO) or derivative-based solvers.

  Derivative-free solvers (also known as black-box solvers) are used when derivative information is unavailable, unreliable, or prohibitively expensive.  This is often the case with numerical simulators, CFD models, real-world experiments, etc.  Derivative-free methods include genetic algorithms, Nelder-Mead, simulated annealing, particle swarm, ant colony, etc.

  Gurobi, on the other hand, is a derivate-based solver.  As such, Gurobi is able to exploit the underlying mathematical model to identify and prove optimality using the branch and bound algorithm you noted.

   

  If you are trying to decide between a derivative-free and a derivative-based solver, it is good to ask yourself

  a) Can you write out the objectives and constraints algebraically? Note: Most IF-THEN conditionals can be converted to an algebraic model using binary variables. 

  • If so, a derivative-based optimization framework is likely your best bet.  These offer provable, repeatable, and scalable solutions that are typically much faster than DFO alternatives.
  • If not, then check out b) and c).

  b) Are the black-box functions (objectives and/or constraints) smooth (i.e. not noisy)? In other words, will the function evaluations lead to noisy derivatives? This may be the case if you need actual physical experiments, noisy simulators, etc. 
  

  • If yes, then using a derivative-based optimization framework is a good option.
  • If not, then estimated derivatives will be too poor. Then options include repeated sampling, surrogate-based models, and DFO/BBO.

  c) Are the function evaluations costly? Are they very time-consuming (minutes to hours to days)? Or do they involve physical experiments?
  

  • If yes, then BBO/DFO may be the way to go because estimated derivatives would be WAY too costly.
  • If not, then you could use derivative-based methods that include estimated gradients or create surrogate models of your functions.

    

  0

Please sign in to leave a comment.