# Large Neighborhood Search

Local search techniques are very effective to solve hard optimization problems. Most of them are, by nature, incomplete. In the context of constraint programming (CP) for optimization problems, one of the most well-known and widely used local search techniques is the Large Neighborhood Search (LNS) algorithm . The basic idea is to iteratively relax a part of the problem, then to use constraint programming to evaluate and bound the new solution.

## Principle

LNS is a two-phase algorithm which partially relaxes a given solution and repairs it. Given a solution as input, the relaxation phase builds a partial solution (or neighborhood) by choosing a set of variables to reset to their initial domain; The remaining ones are assigned to their value in the solution. This phase is directly inspired from the classical Local Search techniques. Even though there are various ways to repair the partial solution, we focus on the technique in which Constraint Programming is used to bound the objective variable and to assign a value to variables not yet instantiated. These two phases are repeated until the search stops (optimality proven or limit reached).

The `INeighborFactory`

provides pre-defined configurations.
Here is the way to declare LNS to solve a problem:

```
solver.setLNS(INeighborFactory.random(ivars, new FailCounter(solver, 100));
solver.findOptimalSolution(Model.MINIMIZE, objective);
```

It declares a *random* LNS which, on a solution, computes a partial solution based on `ivars`

.
If no solution are found within 100 fails (`FailCounter(solver, 100)`

), a restart is forced.

The factory provides other built-in neighbors.

## Neighbors

While the implementation of LNS is straightforward, the main difficulty lies in the design of neighborhoods able to move the search further. Indeed, the balance between diversification (i.e., evaluating unexplored sub-tree) and intensification (i.e., exploring them exhaustively) should be well-distributed.

### Generic neighbors

One drawback of LNS is that the relaxation process is quite often problem dependent. Some works have been dedicated to the selection of variables to relax through general concept not related to the class of the problem treated [5,24]. However, in conjunction with CP, only one generic approach, namely Propagation-Guided LNS [24], has been shown to be very competitive with dedicated ones on a variation of the Car Sequencing Problem. Nevertheless, such generic approaches have been evaluated on a single class of problem and need to be thoroughly parametrized at the instance level, which may be a tedious task to do. It must, in a way, automatically detect the problem structure in order to be efficient.

### Combining neighborhoods

There are two ways to combine neighbors.

#### Sequential

Declare an instance of `SequenceNeighborhood(n1, n2, ..., nm)`

.
Each neighbor `ni`

is applied in a sequence until one of them leads to a solution.
At step `k`

, the $(k \mod m)^{th}$ neighbor is selected.
The sequence stops if at least one of the neighbor is complete.

#### Adaptive

Declare an instance of `AdaptiveNeighborhood(1L, n1, n2, ..., nm)`

.
At the beginning a weight $w_i = 1$ is assigned to each neighbor `ni`

.

If a neighbor leads to solution, its weight $w_i$ is increased by 1.
Any time a partial solution has to be computed, a value `W`

between 1 and $w_1+w_2+…+w_n$ is randomly picked (`1L`

is the seed).

Then the weight of each neighbor is subtracted from `W`

, as soon as `W`

$\leq 0$, the corresponding neighbor is selected.

For instance, let’s consider three neighbors `n1`

, `n2`

and `n3`

, their respective weights $w1=2, w2=4, w3=1$. 3 is randomly assigned to `W`

.
Then, the weight of `n1`

is subtracted, `W`

$- 2 = 1$ ; the weight of `n2`

is subtracted, `W`

$- 3 = -3$, `W`

is less than 0 and n2 is selected.

## Restarts

A generic and common way to reinforce diversification of LNS is to introduce restarts during the search process. This technique has proven to be very flexible and to be easily integrated within standard backtracking procedures .

## Walking

A complementary technique that appear to be efficient in practice is named `Walking`

and consists in accepting equivalent intermediate solutions in a search iteration instead of requiring a strictly better one.

This can be achieved by defining an `ObjectiveManager`

like this:

```
solver.setObjectiveManager(new ObjectiveManager(objective, ResolutionPolicy.MAXIMIZE, false));
```

Where the last parameter, named `strict`

must be set to false to accept equivalent intermediate solutions.

Other optimization policies may be encoded by using either search monitors or a custom `ObjectiveManager`

.

## Feedback

Was this page helpful?

Glad to hear it! Please tell us how we can improve.

Sorry to hear that. Please tell us how we can improve.