In this section, we present the implementation of Local Search in **or-tools**. First, we sketch the main basic idea
and then we list the main actors (aka classes) that participate in the Local Search. It’s good to keep them in memory
for the rest of this section. We then overview the implementation
and describe some of its main components. Finally, we detail the inner workings of the Local Search algorithm and
indicate where the callbacks of the `SearchMonitor`s are called.

We present a simplified version of the Local Search algorithm. Yes, this is well worth a warning box!

Warning

We describe a simplified version of the Local Search algorithm.

The Local Search algorithm is implemented with the `LocalSearch` `DecisionBuilder` which
returns `NestedSolveDecision`s (through its `Next()` method). These `NestedSolveDecision`s in turn
collect the solutions returned by the `FindOneNeighbor`
`DecisionBuilder` in their left branches (and don’t do anything in their right branches). As its name implies, the
`FindOneNeighbor` `DecisionBuilder` tries to find one solution. The `LocalSearch` `DecisionBuilder`
stops the search when stopping criteria are met or when it can not improve the last solution found. This
solution is thus a local optimum w.r.t. the chosen neighborhood.

If needed, the search
can be restarted again around a new initial solution. The `LocalSearch`
`DecisionBuilder` then acts like a multi-restart `DecisionBuilder`. We exploit this property in the
chapter *Meta-heuristics: several previous problems* when we implement (meta-)heuristics based on local searches that restart
from a given solution.

Wow, this went fast! Let’s summarize all this in the next picture:

`ls` is the `LocalSearchOperator` that constructs the candidate solutions. The search
tree very quickly becomes completely unbalanced if we only keep finding solutions in the left branches. We’ll see a balancing
mechanism that involves one `BalancingDecision` at the end of this section.

Speaking about *candidate* solutions, let’s agree on some wordings. The next figure presents the beginning of a Local Search.
is the initial solution. In **or-tools**, this solution is given by an `Assignment` or a `DecisionBuilder` that
the `LocalSearch` class uses to construct this initial solution. are *solutions*. As we have seen,
the Local Search algorithm moves from one solution to another. It takes a starting solution and visit the
neighborhood defined around to find the next solution . By *visiting* the neighborhood, we mean
constructing and testing feasible solutions of this neighborhood. We call these solutions
*candidate* solutions. In the code, they are called *neighbors*. The `LocalSearchOperator` produces these candidates and
the `FindOneNeighbor` `DecisionBuilder` filter these out to keep the interesting candidate solutions only. When a
stopping criteria is met or the neighborhood has been exhausted, the current solution of the CP solver is the next starting
solution.

Let’s illustrate this:

The code consistently use the term *neighbor* to denote what we call a *candidate solution* in this manual.
We prefer to emphasize the fact
that this *neighbor* solution is in fact a feasible solution that the CP solver tests and accepts or rejects.

Warning

In this manual, we use the term *candidate solution* for what is consistently called a *neighbor* in the code.

The main classes involved in the Local Search algorithm are:

`LocalSearch`: This`DecisionBuilder`controls the Local Search algorithm.`LocalSearchPhaseParameters`: This class gathers the components to define the current Local Search.`LocalSearchOperator`s: This class is responsible of constructing the candidate solutions.`FindOneNeighbor`: This`DecisionBuilder`filters the candidate solutions given by the`LocalSearchOperator`and only constructs*filtered*and*accepted*(solutions accepted by the CP solver as feasible solutions) solutions.`NestedSolveDecision`: This`Decision`invokes a nested search with another`DecisionBuilder`(`FindOneNeighbor`in this case) in its left branch (`Apply()`method) and does nothing in its right branch (`Refute()`method).`LocalSearchFilter`: This filter allows to immediately skip (discard) a candidate solution. It is used by`FindOneNeighbor`to filter the candidate solutions.

We will not discuss the filtering mechanism here (see the dedicated section *Filtering*).

The next figure illustrates the basic mechanism of Local Search in **or-tools**:

We start with an initial feasible solution. The `MakeOneNeighbor()` callback method
from the Local Search operator(s)[1]
constructs candidate solutions one by one[2]. These solutions are checked by the CP solver and completed if needed.
The “best” solution
is chosen and the process is repeated starting with this new improved
solution[3].

The whole search process stops whenever a stopping criterion is reached or the CP solver cannot improve anymore the current best solution.

Let’s describe some pieces of the **or-tools** mechanism for Local Search:

initial solution: we need afeasiblesolution to start with. You can either pass anAssignmentor aDecisionBuilderto theLocalSearch‘s constructor.LocalSearchPhaseParameters: theLocalSearchPhaseParametersparameter holds the actual definition of the Local Search phase:

- a
SolutionPoolthat keep solution(s);- a
LocalSearchOperatorused to explore the neighborhood of the current solution. You can combine severalLocalSearchOperators into oneLocalSearchOperator;- a
complementaryDecisionBuilderto instantiate unbound variables once an (incomplete) candidate solution has been defined by theLocalSearchOperator. It will also complete the initialAssignmentor the solution provided by the initialDecisionBuilder.;- a
Searchlimitspecifying the stopping criteria each time we start searching a new neighborhood;- an
std::vectorofLocalSearchFilters used to speed up the search by pruning unfeasible (or undesirable) candidate solutions: instead of letting the solver find out if a candidate solution is feasible or not, you can help it by bypassing its checking mechanism and telling it right away if a candidate solution is not feasible (or not desirable).

`LocalSearchOperator`s are detailed in the next section and `LocalSearchFilter`s in
the section *Filtering*.

We now detail these two basics ingredients that are the initial solution and the `LocalSearchPhaseParameters` parameter.

To start the Local Search, we need an initial *feasible* solution. We can either give a starting
solution or we can ask the CP solver to find one for us. To let the solver find a solution for us,
we pass to it a `DecisionBuilder`. The **first** solution discovered by this `DecisionBuilder` will be taken
as the initial solution.

There is a factory method for each one of the two options:

```
DecisionBuilder* Solver::MakeLocalSearchPhase(Assignment* assignment,
LocalSearchPhaseParameters* parameters)
DecisionBuilder* Solver::MakeLocalSearchPhase(
const std::vector<IntVar*>& vars,
DecisionBuilder* first_solution,
LocalSearchPhaseParameters* parameters)
```

In the file `dummy_ls.cc`, we use a **gflags** flag `FLAG_initial_phase`
to switch between these two possibilities.

What are the variables involved in the Local Search procedure?

The Local Search **only** applies to the variables contained either in the `Assignment`
or the `std::vector<IntVar*>` of variables given to `MakeLocalSearchPhase()`.

The `LocalSearchPhaseParameters` parameter holds the actual definition
of the Local Search phase.

It basically consists in:

a

`SolutionPool`: as its name implies, this class is a pool of solutions. As usual,`SolutionPool`is a pure virtual class that must be implemented. One such implementation is the`DefaultSolutionPool`that only keeps the current solution. You don’t have to provide one as it is constructed by default if you use the appropriate factory method. If you want to keep intermediate solutions or want to modify these solutions during the search, you might have to implement your own version. Four methods have to be implemented:`void Initialize(Assignment* const assignment)`: This method is called to initialize the`SolutionPool`with the initial`Assignment`.`void RegisterNewSolution(Assignment* const assignment)`: This method is called when a new solution has been accepted by the Local Search algorithm.`void GetNextSolution(Assignment* const assignment)`: This method is called when the Local Search algorithm starts a new neighborhood.`assigment`is the solution to start the new neighborhood search.`bool SyncNeeded(Assignment* const local_assignment)`: This method checks if the current solution needs to be updated, i.e. the pool can oblige the solver to start a new neighborhood search with the next solution given by the pool (given by its`GetNextSolution()`method, see the`Next()`method of the`FindOneNeighbor``DecisionBuilder`class below).

A

`SolutionPool`gives you complete control on the starting solution(s). Note that the`SolutionPool`**must**take ownership of the`Assignment`s it keeps[4].a

`LocalSearchOperator`: a`LocalSearchOperator`or a combination of`LocalSearchOperator`s explore the neighborhood of the current solution. We detail them in the next section.a

`DecisionBuilder`: this*complementary*`DecisionBuilder`helps creating feasible solutions if your`LocalSearchOperator`s only return partial solutions, i.e. solutions with unbounded variables. It also completes the initial solution if needed. If you know that your candidate and the initial solutions are already feasible, you don’t have to provide this`DecisionBuilder`(set the corresponding pointer to`NULL`).

a

`SearchLimit`: This`SearchLimit`limits the search of**one**neighborhood. The most interesting statistic to limit is probably the number of found solutions:SearchLimit * const limit = s.MakeSolutionsLimit(2);

This would limit the search to maximum two candidate solutions in the same neighborhood. By default, the CP solver stops the neighborhood search as soon as it finds a filtered and feasible candidate solution. If you add an

`OptimizeVar`to your model, once the solver finds this good candidate solution, it changes the model to exclude solutions with the same objective value. The second solution found can only be better than the first one. See the section*How does the solver optimize?*to refresh your memory if needed. In our example, when the solver finds 2 solutions (or when the whole neighborhood is explored), it stops and starts over again with the best solution.`LocalSearchFilter`s: these filters speed up the search by bypassing the solver checking mechanism if you know that the solution must be rejected (because it is not feasible, because it is not good enough, ...). If the filters accept a solution, the solver still tests the feasibility of this solution.`LocalSearchFilter`s are discussed in the section*Filtering*.

Several factory methods are available to create a `LocalSearchPhaseParameters` parameter.
At least you need to declare a `LocalSearchOperator` and a complementary `DecisionBuilder`:

```
LocalSearchPhaseParameters * Solver::MakeLocalSearchPhaseParameters(
LocalSearchOperator *const ls_operator,
DecisionBuilder *const
complementary_decision_builder);
```

You can also pass all the above enumerated parameters :

```
LocalSearchPhaseParameters* Solver::MakeLocalSearchPhaseParameters(
SolutionPool* const pool,
LocalSearchOperator* const ls_operator,
DecisionBuilder* const
complementary_decision_builder,
SearchLimit* const limit,
const std::vector<LocalSearchFilter*>& filters);
```

The `LocalSearchOperator` will find candidate solutions while the `complementary_decision_builder`
`DecisionBuilder` will complete
the candidate solutions if some of the variables are not assigned.

A handy way to create a `DecisionBuilder` to assist the Local Search operator(s) is to limit one
with `MakeSolveOnce()`. `MakeSolveOnce` returns a `DecisionBuilder` that takes another `DecisionBuilder` `db`
and `SearchMonitor`s:

```
DecisionBuilder * const db = ...
SearchLimit* const limit = solver.MakeLimit(...);
DecisionBuilder * const complementary_decision_builder =
solver.MakeSolveOnce(db, limit);
```

The `SolveOnce` `DecisionBuilder` created by `MakeSolveOnce()` will collapse the search tree described by the
`DecisionBuilder` `db` and a set of `SearchMonitor`s and wrap it into a single point. The nested search stops after
the first solution is found.
If there are no solutions in this nested tree, then (the `Next()` method of) `SolveOnce` will
fail.

We feel compelled to use our warning box again:

Warning

We describe a simplified version of the Local Search algorithm.

If you want to know more, have a look at the section
*Local Search (LS)* in the chapter *Under the hood*.

In this subsection, we present the following callbacks of the `SearchMonitor` class and show you
exactly when they are called in the Local Search algorithm:

Methods | Descriptions |
---|---|

LocalOptimum() |
When a local optimum is reached. If true is returned, the last solution is discarded and the search proceeds to find the next local optimum. Handy when you implement a meta-heuristic with a SearchMonitor. |

AcceptDelta(Assignment *delta, Assignment *deltadelta) |
When the LocalSearchOperator has produced the next candidate solution given in the form of delta and deltadelta. You can accept or reject this new candidate solution. |

AcceptNeighbor() |
After accepting a candidate solution during Local Search. |

PeriodicCheck() |
Periodic call to check limits in long running procedures, like Local Search. |

To ensure the communication between the Local Search and the Global Search, three utility functions are defined.
These functions simply call their `SearchMonitor`‘s counterparts, i.e. they call the corresponding methods of the
involved `SearchMonitor`s:

`bool LocalOptimumReached()`:`FalseExceptIfOneTrue`.`bool AcceptDelta()`:`TrueExceptIfOneFalse`.`void AcceptNeighbor()`: Notification.

Before we delve into the core of the Local Search algorithm and the implementation of the `LocalSearch` `DecisionBuilder`‘s
`Next()` method, we first discuss the inner workings of the `FindOneNeighbor` `DecisionBuilder` whose job is to find
the next filtered and accepted candidate solution. This `DecisionBuilder` is used inside a `NestedSolveDecision` that we study next.
This `Decision` is returned by the `Next()` method of
the `LocalSearch` `DecisionBuilder` in the main loop of the Local Search algorithm. Finally, we address the
`LocalSearch` `DecisionBuilder` class. In particular, we study its initializing phase and its `Next()` method.
We consider the case where an initial `DecisionBuilder` constructs the initial solution.

SearchMonitorâ€˜s callbacks are indicated in the code by the comment:

```
// SEARCHMONITOR CALLBACK
```

This `DecisionBuilder` tries to find the next filtered and accepted candidate solution.
It tests (and sometimes completes) the candidate solutions given by the `LocalSearchOperator`.

We present its `Next()` method and discuss it after:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | ```
Decision* FindOneNeighbor::Next(Solver* const solver) {
// No neighbor (candidate solution) found
// only on the first call to Next().
if (!neighbor_found_) {
// SYNCHRONIZE ALL
...
}
// Another assignment is needed to apply the delta
Assignment* assignment_copy =
solver->MakeAssignment(reference_assignment_.get());
int counter = 0;
DecisionBuilder* restore =
solver->MakeRestoreAssignment(assignment_copy);
if (sub_decision_builder_) {
restore = solver->Compose(restore, sub_decision_builder_);
}
Assignment* delta = solver->MakeAssignment();
Assignment* deltadelta = solver->MakeAssignment();
// MAIN LOOP
while (true) {
delta->Clear();
deltadelta->Clear();
// SEARCHMONITOR CALLBACK
solver->TopPeriodicCheck();
if (++counter >= FLAGS_cp_local_search_sync_frequency &&
pool_->SyncNeeded(reference_assignment_.get())) {
// SYNCHRONIZE ALL
...
counter = 0;
}
if (!limit_->Check()
&& ls_operator_->MakeNextNeighbor(delta, deltadelta)) {
solver->neighbors_ += 1;
// SEARCHMONITOR CALLBACK
const bool meta_heuristics_filter =
AcceptDelta(solver->ParentSearch(), delta, deltadelta);
const bool move_filter = FilterAccept(delta, deltadelta);
if (meta_heuristics_filter && move_filter) {
solver->filtered_neighbors_ += 1;
assignment_copy->Copy(reference_assignment_.get());
assignment_copy->Copy(delta);
if (solver->SolveAndCommit(restore)) {
solver->accepted_neighbors_ += 1;
assignment_->Store();
neighbor_found_ = true;
return NULL;
}
}
} else {
if (neighbor_found_) {
// SEARCHMONITOR CALLBACK
AcceptNeighbor(solver->ParentSearch());
pool_->RegisterNewSolution(assignment_);
// SYNCHRONIZE ALL
...
} else {
break;
}
}
}
solver->Fail();
return NULL;
}
``` |

You might wonder why there are so many lines of code but there are a some subtleties to consider.

The code of lines 5 to 8 is only called the first time the `Next()` method is invoked
and allow to synchronize the Local Search machinery with the initial solution. In general,
the words `SYNCHRONIZE ALL` in the comments mean that we synchronize the *Local Search Operators* **and** the
*Local Search Filters* with
a solution.

`reference_assignment_` is an `Assignment` with the initial solution while `assignment_` is an
`Assignment` with the current solution.
On line 10, we copy `reference_assignment_` to the local `assignment_copy` `Assignment`
to be able to define the `delta`s. `counter` counts the number candidate solutions.
This counter is used on line 29 to test if we shouldn’t start again the Local Search with another solution.

On lines 15-19, we define the `restore` `DecisionBuilder` that will allow us to
keep the newly found candidate solution.

We construct the `delta` and `deltadelta` on lines 20 and 21 and are
now ready to enter the main loop to find the
next solution.

On lines 25 and 26 we clear our `delta`s and on line 28 we allow for a periodic check: for searches that last long,
we allow the `SearchMonitor`s to interfere and test if the search needs to continue or not and/or must be adapted.

Lines 29-34 allow to change the starting solution and ask the solution pool `pool_` for a new solution via its
`GetNextSolution()`. The `FLAGS_cp_local_search_sync_frequency` value corresponds to the number of attempts
before the CP solver tries to synchronize the Local Search with a new solution.

On line 36 and 37, the `SearchLimit`s applied to the search of one neighborhood are tested.
If the limits are not reached and if the
`LocalSearchOperator` succeeds to find a new candidate solution, we enter the `if` statement
on line 38. The `LocalSearchOperator`‘s `MakeNextNeighbor()` method is
called to create the next candidate solution in `delta`s format.

If you overwrite the `MakeNextNeighbor()` method, you need to manage the `delta`s:
you must take care of *applying* and *reverting* the `delta`s yourself if needed. You can use the
`ApplyChanges()` and `RevertChanges()` helper functions to do so. For instance, here is the implementation of the
`MakeNextNeighbor()` method of the `IntVarLocalSearchOperator`:

```
bool IntVarLocalSearchOperator::MakeNextNeighbor(Assignment* delta,
Assignment* deltadelta) {
CHECK_NOTNULL(delta);
while (true) {
RevertChanges(true);
if (!MakeOneNeighbor()) {
return false;
}
if (ApplyChanges(delta, deltadelta)) {
return true;
}
}
return false;
}
```

`ApplyChanges()` actually fills the `delta`s after you use the helper methods
`SetValue()`, `Activate()` and the like to change the current candidate solution.

Once we enter the `if` statement on line 38, we have a new candidate solution and we update the candidate
solution counter accordingly.
It is now time to test this new candidate solution. The **first test** comes from the `SearchMonitor`s in their
`AcceptDelta()` methods. If only one `SearchMonitor` rejects this solution, it is rejected. In **or-tools**, we
implement (meta-)heuristics with `SearchMonitor`s. See the chapter *Meta-heuristics: several previous problems* for more.

The `AcceptDelta()` function is the global utility function we mentioned above.
We’ll meet `LocalOptimumReached()` and `AcceptNeighbor()` a few lines below.

The **second test** is the *filtering* test on line 42. `FilterAccept()` returns a `TrueExceptIfOneFalse`.
If both tests are successful, we enter the `if` statement on line 44. If not, we simply generate another
candidate solution. On lines 44 and 46, we update the
counter of `filtered_neighbors_` and store the candidate solution in the `assignment_copy` `Assignment`.

On line 47, we try (and if needed complete) the candidate. If we succeed, the current solution
and the counter `accepted_neighbors_` are updated.
The `Next()` method returns `NULL` because the `FindOneNeighbor`
`DecisionBuilder` has finished its job at this node of the search tree. If we don’t succeed, the solver fails on
line 66.

The `SolveAndCommit()` method is similar to the `Solve()` method **except** that
`SolveAndCommit` will not backtrack all modifications at the end of the search and this is why you should:

Warning

Use the `SolveAndCommit()` method **only** in the `Next()` method of a `DecisionBuilder`!

If the `if` test on line 36 and 37 fails, we enter the `else` part of the statement on line 55. This means that
either one `SearchLimit` was reached or that the neighborhood is exhausted. If a solution (stored in `assignment_`)
was found during the Local Search, we register it and synchronize the `LocalSearchOperator`s and `LocalSearchFilter`s
with a new solution provided by the solution pool `pool_` on lines 58-60. We also notify the `SearchMonitor`s
on line 57. If no solution was found, we simply `break` out of the
`while()` loop on line 62 and make the CP solver fail on line 66.

The `NestedSolveDecision` is the `Decision` that the `LocalSearch`‘s `Next()` method returns
to find the next solution.
This `Decision` is basically a `Decision` wrapper around a nested solve with a given `DecisionBuilder`
and `SearchMonitor`s. It doesn’t do anything in its right
branch (in its `Refute()` method) and calls `Solve()` or `SolveAndCommit()` depending on a `restore` `bool`
in its left branch (in its `Apply()` method).

The `NestedSolveDecision` `Decision` can be in three states that are also the three states of the Local Search:

Value | Meaning |
---|---|

DECISION_FAILED |
The nested search phase failed, i.e. Solve() or SolveAndCommit()
failed. |

DECISION_PENDING |
The nested search hasn’t been called yet. The Local Search is in this state when it balances the search tree. |

DECISION_FOUND |
The nested search phase succeeded and found a solution, i.e. Solve()
or SolveAndCommit() succeeded and returned true. |

The three states are defined in the `NestedSolveDecision` `StateType` `enum`.

We are now ready to assemble all the pieces of the puzzle together to understand the (simplified)
Local Search algorithm in **or-tools**.

We first consider the initialization phase and then we discuss in details its `Next()` method.

Initialization

Consider the situation where we already have a `LocalSearchPhaseParameters` parameter set up and we let the CP solver
construct the initial solution:

```
Solver s("Dummy LS");
...
std::vector<IntVar*> vars = ...
...
LocalSearchOperator * const ls_operator = ...
DecisionBuilder * const complementary_decision_builder = ...
...
LocalSearchPhaseParameters params =
s.MakeLocalSearchPhaseParameters(ls_operator,
complementary_decision_builder);
```

The `complementary_decision_builder` `DecisionBuilder` will help us complete
the candidate solutions found by the `LocalSearchOperator` `ls_operator`. Our initial solution will be constructed
by the `initial_solution` `DecisionBuilder` (and completed by the `complementary_decision_builder` `DecisionBuilder`
if needed). Remember, that the solution chosen by the CP solver is the **first**
solution found by this `DecisionBuilder`. We are now ready to create the `DecisionBuilder` for the Local Search:

```
DecisionBuilder * const initial_solution = ...
...
DecisionBuilder * const ls = s.MakeLocalSearchPhase(vars,
initial_solution,
params);
```

We can now add as many monitors as we want and launch the solving process:

```
std::vector<SearchMonitor *> monitors;
...
s.Solve(ls, monitors);
```

It’s interesting to see how this initial solution is constructed in the `LocalSearch` class.
First, we create an `Assignment` to store this
initial solution:

```
Assignment * const initial_sol = s.MakeAssignment();
```

To store an `Assignment` found by the CP solver, we use the `StoreAssignment` `DecisionBuilder`:

```
DecisionBuilder * store = solver->MakeStoreAssignment(initial_sol);
```

This `DecisionBuilder` simply stores the current solution in the `initial_sol` `Assignment`:

```
DecisionBuilder * initial_solution_and_store = solver->Compose(
initial_solution,
complementary_decision_builder,
store);
```

`initial_solution_and_store` constructs this initial solution. This `DecisionBuilder`
is used in a nested search:

```
std::vector<SearchMonitor *> monitors;
monitors.push_back(limit);
NestedSolveDecision * initial_solution_decision =
new NestedSolveDecision(initial_solution_and_store,
false,
monitors);
```

where:

limitis theSearchLimitgiven to the Local Search algorithm;- the
NestedSolveDecisionconstructor’s arguments are respectively:

- a
DecisionBuilderto construct the next solution;- a
boolto indicate if we restore the last solution in case we cannot find a solution;- an
std::vector<SearchMonitor *>.

The `Apply()` method of a `NestedSolveDecision` calls `SolveAndCommit()`:

```
solver->SolveAndCommit(initial_solution_and_store, monitors);
```

where the arguments respectively are:

- a
DecisionBuilder;- an
std::vector<SearchMonitor *>.

The `DecisionBuilder` companion to `StoreAssignment` is `RestoreAssignment` that
*installs* an `Assignment` as the current solution:

```
Assignment * solution = ...
...
DecisionBuilder * current_sol = s.MakeRestoreAssignment(solution);
...
// do something fancy starting with current_sol
DecisionBuilder * fancy_db = s.Compose(current_sol, ...);
...
s.Solve(fancy_db,...);
```

This is exactly the `DecisionBuilder` used when you give an initial solution to the CP solver.
The `initial_solution` `DecisionBuilder` is simply replaced with a `RestoreAssignment` `DecisionBuilder`
taking your initial `Assignment`.

Now that we have developed the machinery to find and test the initial solution, we are ready to wrap the nested solve process
into a `NestedSolveDecision`:

```
// Main DecisionBuilder to find candidate solutions one by one
DecisionBuilder* find_neighbors =
solver->RevAlloc(new FindOneNeighbor(assignment_,
pool_,
ls_operator_,
sub_decision_builder_,
limit_,
filters_));
NestedSolveDecision* decision = solver->RevAlloc(
new NestedSolveDecision(find_neighbors,
false)));
```

The `boolean` argument in the `NestedSolveDecision`‘s constructor indicates that we don’t want to backtrack.
The `decision` `Decision` will thus call `SolveAndCommit()` in its left branch.

The `Next()` method

The `Next()` method of the `LocalSearch` `DecisionBuilder` is in charge of controling the Local Search. We present it
first and discuss it next:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | ```
Decision * Next(Solver * solver) {
...
const int state = decision->state();
switch (state) {
case NestedSolveDecision::DECISION_FAILED: {
// SEARCHMONITOR CALLBACK: LocalOptimum()
if (!LocalOptimumReached(solver->ActiveSearch())) {
// Stop the current search
...
}
solver->Fail();
return NULL;
}
case NestedSolveDecision::DECISION_PENDING: {
// Stabilize search tree by balancing the current search tree.
// Statistics are updated even if this is not relevant to the
// global search
...
const int depth = solver->SearchDepth();
if (depth < kLocalSearchBalancedTreeDepth) {
return solver->balancing_decision();
} else if (depth > kLocalSearchBalancedTreeDepth) {
solver->Fail();
}
...
return decision;
}
case NestedSolveDecision::DECISION_FOUND: {
// Nothing important for us in this simplified version
...
return NULL;
}
default: {
LOG(ERROR) << "Unknown local search state";
return NULL;
}
}
return NULL;
}
``` |

The `decision` variable on line 3 is the `NestedSolveDecision` created with
the `FindOneNeighbor` `DecisionBuilder`.
We `switch` between three cases depending on the state of the nested search initiated by this `Decision`.

- Line 5: case
**DECISION_FAILED**: The nested solving process failed, meaning that there are no solution left. We let the`SearchMonitor`s decide if a local optimum has been reached and cannot be improved.`LocalOptimum()`returns a`FalseExceptIfOneTrue`. - Line 14: case
**DECISION_PENDING**: This is the most interesting case: we try to keep the search tree balanced and force its height to be bounded.`kLocalSearchBalancedTreeDepth`is set to 32. So as long as the tree height is smaller than 32, the`LocalSearch``DecisionBuilder`returns the**same**`BalancingDecision`on line 21.`BalancingDecision`s don’t do anything by default. Once the search tree height is over 32, the`NestedSolveDecision``Decision`enters in action and when the height of the three gets higher than 32, we make the CP solver`Fail()`to backtrack on line 23 thus keeping the height of the tree bounded. - Line 28: case
**DECISION_FOUND**: The nested search found a solution that is the current solution. The`LocalSearch`‘s`Next()`method has done its job at the current node and nothing needs to be done.

`Solve()`, `SolveAndCommit()`, `SolveOnce()`, etc...: what are the differences?

This topic is so important that the whole section *What are my solving options?* is devoted to it.
You already can jump and read this section if you’re curious.

[1] | In the code, you are only allowed to use one LocalSearchOperator but
you can combine several LocalSearchOperators in one LocalSearchOperator. This is a common pattern in the code. |

[2] | MakeOneNeighbor() is a convenient method. The real method to create a new
candidate is MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) but you have to deal with the low
level delta and deltadelta. We discuss these details in the
section LocalSearchOperators: the real thing!. |

[3] | By default, the solver accepts the
first feasible solution and repeats the search starting with
this new solution. The idea is that if you combine the Local Search with an ObjectiveVar,
the next feasible solution will be a solution that beats the current best solution.
You can change this behaviour with a SearchLimit. Read on. The LocalSearch class is also deeply coupled to the Metaheuristic class or more generally to a SearchMonitor. This is the subject
of next chapter. |

[4] | Well, you could devise another way to keep track of the solutions and take care of their existence but anyhow, you are responsible for these solutions. |