To help you (and us) in the building of meta-heuristics, the **or-tools** library offers an abstract `Metaheuristic`
which your specialized class can inherit from. We deal with
optimization problems: we either *minimize* or *maximize* an objective function. The way meta-heuristics are implemented in **or-tools** is to
let the meta-heuristic itself decide what to do when the objective value changes: it can add a new constraint on the objective value and/or the next solution to be found. This means that you **don’t** use
the `OptimizeVar` class to encapsulate your objective function[1] but instead use the `Metaheuristic` class to add complementary constraints
on your objective.

Warning

**Don’t** use the `OptimizeVar` class to encapsulate your objective function when using a `Metaheuristic` class.

The `Metaheuristic` class inherits from the `SearchMonitor` class.
`SearchMonitor`s allow you to monitor/control the search. If you don’t remember anything about the basic search
algorithm and the `SearchMonitor` class, we invite you to quickly (re)read the section *Basic working of the solver: the search algorithm* and especially the section *Basic working of the solver: Local Search*.
We do sketch what the methods of the `SearchMonitor` class do in this chapter thought.

We reiterate our warning concerning the start of our meta-heuristics:

Warning

Our meta-heuristics only kick in when we have already reached a **local optimum** with the Local Search.

This is a choice in our implementations of the meta-heuristics. See the box *Why wait for a local optimum to start a meta-heuristic?* below for more.

One last thing before digging further into this fascinating subject. Because details matter very much in the case of meta-heuristic implementations, we present the full code of all the classes discussed in this and the next three sections.

The basic idea behind meta-heuristics is to enhance the Local Search. In particular, most meta-heuristics share (at least) the three following main features:

- avoid being trapped in local optimums;
- intensify the search in a promising neighborhood (intensification) and
- keep better solutions met during the search (aspiration criterion).

We discuss these three features more in details next.

Let’s reexamine the figure used in the previous chapter to illustrate Local Search:

With a given `LocalSearchOperator` and starting at , we might find solutions , , and even probably the local minimum depicted above.
In practice, no matter what starting point you take close to the local optimum, your Local Search will probably guide you towards this local optimum.
This is because at each of these points, locally and with the limited information your Local Search has, it will move towards this local optimum. This is called **being trapped in a local optimum**.
Meta-heuristics devise clever ways to get out of this local optimum trap but to do so, meta-heuristics **must** accept worse solutions.

Avoiding being trapped in a local optimum can be seen as a special case of **diversification** of the search: the algorithm explores different parts of the search space in the hope of finding
promising neighborhoods that a basic Local Search algorithm would not explore on its own.
The opposite is also desirable. Once a promising neighborhood has been found, it is probably worth exploring it in more details. This is called **intensification**.

Often the intensification and diversification mechanisms are conflicting and the meta-heuristic oscillates between these two phases in the search.

In practice, we often see the following scenario. A `LocalSearchOperator` could have found a better candidate solution in a neighborhood if
it were operating without restrictions by the meta-heuristics
That’s a really annoying situation: you want to help your `LocalSearchOperator`
by restricting it a little bit and then it turns out that without your guidelines, it would have been able to find a better solution
This situation is so common that most meta-heuristics use an **aspiration criterion**: a criterion to accept a solution **even** if it doesn’t follow the meta-heuristic guidelines. Most of the time this criterion is based on the quality of the found solution: a solution is accepted no matter what if it is better than any other solution encountered so far.

The base `Metaheuristic` class is quite simple.
It only implements three basic virtual methods:

`virtual void EnterSearch()`;`virtual bool AtSolution()`and`virtual void RefuteDecision(Decision* const d)`.

It also defines five basic variables:

```
protected:
IntVar* const objective_;
int64 step_;
int64 current_;
int64 best_;
bool maximize_;
```

The names of the variables are self-explanatory. `maximize_` is set to `true` when maximizing and `false` when minimizing.

We reproduce the implementation of the three virtual methods integrally. Not only are they pedagogically interesting, it is also good to know them to avoid reinventing the wheel.

`EnterSearch` is called at the beginning of the search and is the perfect place to initialize our variables:

```
virtual void Metaheuristic::EnterSearch() {
if (maximize_) {
best_ = objective_->Min();
current_ = kint64min;
} else {
best_ = objective_->Max();
current_ = kint64max;
}
}
```

The other variables are set in the constructor. The `current_` variable holds the value of the current solution and is used to bound the objective value. We start with a very high value to allow the meta-heuristic to find solutions that have worst objective values than the best solution encountered so far.

The `AtSolution()` method is called whenever a valid solution is found. If the return value is `true`, then the search will resume, otherwise the search will stop there. This is the perfect place to
update the current and best solution:

```
virtual bool Metaheuristic::AtSolution() {
current_ = objective_->Value();
if (maximize_) {
best_ = std::max(current_, best_);
} else {
best_ = std::min(current_, best_);
}
return true;
}
```

By default, we don’t want the `Metaheuristic` class to halt the search so we return `true`.

`RefuteDecision(Decision* const d)` is called just before refuting the corresponding `Decision`. Remember how, at each node of the search tree, the search algorithm visits two search sub-trees:
the first one when *applying* the `Decision` and the second one when *refuting* this `Decision`.
This second visit happens (essentially) when the search algorithm backtracks and
on its way back we test if our meta-heuristic can still beat the best solution or not:

```
virtual void Metaheuristic::RefuteDecision(Decision* d) {
if (maximize_) {
if (objective_->Max() < best_ + step_) {
solver()->Fail();
}
} else if (objective_->Min() > best_ - step_) {
solver()->Fail();
}
}
```

If our meta-heuristic is not able to beat the best solution, we make the search fail at this node and let the solver continue the search at another node. We don’t take any action before a `Decision` is
applied by default because each meta-heuristic has its own way of dealing with an applied `Decision`. You’ll probably need to overwrite the `ApplyDecision()` method for each meta-heuristic.

Do I really need to inherit from `Metaheurstic` to create my specialized meta-heuristic?

Using a `SearchMonitor` is probably the way to go if you want to implement a meta-heuristic. And if you decide to inherit from a `SearchMonitor`, why not benefit from the added value of the
`Metaheuristic` class? More generally, isn’t there another way to construct a (meta-)heuristic? Large Neighborhood Search[2] is implemented by a `BaseLNS` class that is a `IntVarLocalSearchOperator` class for instance. It is all a question of choice and... trade-offs.

We briefly review some of the callbacks of the `SearchMonitor` class that we might want to implement when designing a new meta-heuristic. We have already seen a basic use for `EnterSearch()`,
`AtSolution()` and `RefuteDecision()` above. We probably need to extend/specialize these basic implementations but for now, we discuss *other* callbacks of the `SearchMonitor` class that can or must
be used to implement a meta-heuristic. Don’t forget that we use Local Search.

This is the counter-part of `RefuteDecision()` and **must** be implemented. This callback is called just before applying the `Decision` and you use it to control the direction of the Local Search, i.e. to control where to go in the neighborhood to find the next solution. Every meta-heuristic has its own search mechanism and this is the main method to implement.

To search for better solutions, you might want to implement something along these lines:

```
// Go downhill to the next local optimum
if (maximize_) {
const int64 bound = (current_ > kint64min) ?
current_ + step_ : current_;
s->AddConstraint(s->MakeGreaterOrEqual(objective_, bound));
} else {
const int64 bound = (current_ < kint64max) ?
current_ - step_ : current_;
s->AddConstraint(s->MakeLessOrEqual(objective_, bound));
}
```

`LocalOptimum()` is called whenever a “local optimum is reached”: but it is up to you to decide in your `SearchMonitor`/`Metaheuristic` class if this is the case or not. Most probably you would
want to agree if a solution has been found.
You know that a nested Local Search has been exhausted and that probably a local best solution has been found. If your meta-heuristic continues the search as ours do, this is the place to launch
your meta-heuristic and restart another Local Search.

Why wait for a local optimum to start a meta-heuristic?

Let’s try to explain our practical approach in a few lines. First of all, we do accept any improving solution found by a `LocalSearchOperator` even if the move leading to that solution isn’t
permitted by the meta-heuristic. For instance, in our implementation of the Tabu Search, we allow the `LocalSearchOperator` to transgress any tabu moves[3]. To allow this,
we implemented the tabu moves as constraints that can be violated in case a better solution is found. Thus as long as a `LocalSearchOperator` finds improving solutions, the use of a meta-heuristic
will **not** make any difference in **our** implementations. Our point of view is to let a `LocalSearchOperator` do its job as long as it can improve the solutions it finds. Once it cannot improve a solution, i.e. once it scours the neighborhood without any success, we have... a local optimum. And that’s precisely when our meta-heuristics kick in: we would like to get out of this local minimum trap and visit other neighborhoods. This also means that you should use our meta-heuristics with `LocalSearchOperator`s that are not too clever and don’t visit a huge number of neighbors (candidate solutions). For instance, `LocalSearchOperator`s that include lots of randomness should probably best be avoided.

This method is called whenever a *neighbor* (what we called a *candidate solution* in the previous chapter) has been selected (accepted and filtered) in one neighborhood. This is probably one
iteration of your algorithm and the perfect time to update your search strategy depending on the new candidate solution.

The following figure illustrates the hierarchy situation between the different implemented `Metaheuristic` classes:

Tabu Search, Simulated Annealing and Guided Local Search are three well-known meta-heuristics.

In the following sections, we’ll have a detailed look at each of these classes and apply them to solve one or several problems we have already encountered[4]. Meta-heuristic are more a general canvas within which much liberty is offered for a concrete and specialized implementation. Our implementation is only one among many.

These three meta-heuristics can be used within the Routing Library (RL) by switching a command line flag:

```
- routing_guided_local_search
- routing_simulated_annealing
- routing_tabu_search
```

All three flags are set to `false` by default. You can only use **one** meta-heuristic at a time.

[1] | Well, if you do, nothing bad will happen. It’s just unnecessary work for the CP Solver. Both OptimizeVar and Metaheuristic classes
are SearchMonitors. The Metaheuristic class
was implemented to be used without the OptimizeVar class. This is the case for the three implemented Metaheuristics: TabuSearch, SimulatedAnnealing and GuidedLocalSearch. |

[2] | You can read more about LNS in the section |

[3] | See next section about the Tabu Search if you are not acquainted with this meta-heuristic. |

[4] | We will not see an example for the GLS meta-heuristic because our implementation is tailored to solve Routing Problems. |