Local search

The methods of descent, or local searches, compose to « slide » along the objective function to find a local optimum, until the descent is no longer possible. There are several types of descent methods that we will describe here.

Simple descent

From an initial solution, the simple descent algorithm chooses a neighboring solution better than the current solution, until it can not make such a choice.
   S(i+1) = neighboor(Si)
   if f(S(i+1)) < f(Si)
      accept S(i+1)
while f(S(i+1)) < f(Si), any S(i+1) = neighboor(Si)
return Rn


Largest descent

The algorithm is mainly the same as for the simple descent, only a criterion of selection of a neighboring solution is modified:

choose s' from neighboor(s) / f(s') < f(s'') or f(s')=f(s'') for any s'' from neighboor(s)


Multi-start descent

The multi-start descent performs multiple instances of the single descent or greater descent problem.