Local Search¶

Local search is the main family of improvement procedures in Mork. It starts from a feasible solution, explores a Neighborhood<M, S, I>, executes an improving move, and repeats until no improving move remains or time runs out.

In the current API, the concrete strategies are:

LocalSearchBestImprovement<M, S, I>
LocalSearchCachedBestImprovement<M, S, I>
LocalSearchFirstImprovement<M, S, I>

Overview¶

LocalSearch<M, S, I> is the shared base class for local-search improvers. It combines:

an Objective<M, S, I> used to evaluate moves;
a Neighborhood<M, S, I> that generates candidate moves;
a strategy-specific getMove(solution) implementation that decides which improving move to execute next.

graph TD
    A[Current Solution] --> B[Explore Neighborhood]
    B --> C[Pick Improving Move]
    C --> D{Move found?}
    D -->|Yes| E[Execute Move]
    E --> A
    D -->|No| F[Local Optimum]

How it works in Mork¶

The shared loop in LocalSearch is:

improve(solution):
    while time remains:
        move = getMove(solution)
        if move == null:
            stop
        move.execute(solution)

The important design point is that LocalSearch does not generate moves itself. Move generation lives in the Neighborhood, while the concrete subclass decides how to select the next move from the explored neighborhood.

Using a neighborhood¶

Neighborhood<M, S, I> is the extension point used by local search.

public class MyNeighborhood
        extends Neighborhood<MyMove, MySolution, MyInstance> {

    @Override
    public ExploreResult<MyMove, MySolution, MyInstance> explore(MySolution solution) {
        return ExploreResult.fromList(
            solution.getCandidates().stream()
                .map(candidate -> new MyMove(solution, candidate))
                .toList()
        );
    }
}

The neighborhood can return:

a list-backed result, which is convenient when all moves are already materialized;
or a streamed result, which is useful when moves should be generated lazily.

That distinction matters because the concrete local-search strategies exploit both forms differently.

Creating a local search improver¶

The simplest way is to instantiate one of the three concrete classes with a neighborhood. Cached best improvement also requires a positive cache size and moves that implement RefreshableMove.

var bestImprovement = new LocalSearchBestImprovement<MyMove, MySolution, MyInstance>(
    new MyNeighborhood()
);

var firstImprovement = new LocalSearchFirstImprovement<MyMove, MySolution, MyInstance>(
    new MyNeighborhood()
);

var cachedBestImprovement = new LocalSearchCachedBestImprovement<
    MyRefreshableMove, MySolution, MyInstance
>(new MyRefreshableNeighborhood(), 32);

If needed, you can also provide an explicit objective instead of relying on the main objective from the execution context.

var ls = new LocalSearchBestImprovement<MyMove, MySolution, MyInstance>(
    myObjective,
    new MyNeighborhood()
);

Strategy specifics¶

LocalSearchBestImprovement¶

LocalSearchBestImprovement<M, S, I> explores the neighborhood and executes the best improving move available in the current iteration.

BestImprovement(solution):
    moves = neighborhood.explore(solution)
    bestMove = best improving move in moves
    if bestMove exists:
        execute bestMove
    else:
        stop

Behavior in the current implementation:

if the explored neighborhood is list-backed, Mork uses objective.bestMove(...);
if it is stream-backed, Mork reduces the stream using the objective;
after selecting the best candidate, the move is executed only if it actually improves the solution.

Use LocalSearchBestImprovement when:

neighborhood exploration is reasonably small or moderate;
move quality matters more than per-iteration speed;
you want the steepest-descent style behavior.

var improver = new LocalSearchBestImprovement<MyMove, MySolution, MyInstance>(
    new MyNeighborhood()
);

LocalSearchCachedBestImprovement¶

LocalSearchCachedBestImprovement<M, S, I> reduces repeated full-neighborhood explorations by retaining several promising moves. Its move type must extend Move<S, I> and implement RefreshableMove<M, S, I>.

When the cache is empty, the strategy explores the full neighborhood, retains the best cacheSize improving moves, executes the best one, and caches the remainder. On later iterations, it refreshes cached moves in their original best-first order and executes the first refreshed move that still improves the current solution. If the cache has no usable move, it explores the full neighborhood again.

CachedBestImprovement(solution):
    while cached moves remain:
        candidate = remove next cached move
        refreshed = candidate.refresh(solution)
        if refreshed exists and improves:
            return refreshed

    moves = neighborhood.explore(solution)
    retained = best cacheSize improving moves
    if retained is empty:
        stop
    return best retained move and cache the rest

Note that cached candidates were ordered using their scores during the last full exploration. After the solution changes, that order may be stale. The returned move is always checked for improvement, but it is not necessarily the best move for the current solution. We recommend using CachedBestImprovement when neigborhoods are big, and applying a move does not produce massive changes to other move scores.

Refreshable moves¶

Note that because move are cached between iterations when using CachedBestImprovement, they will likely be stale and their score wrong after applying several moves. For this reason, cached moves must implement the refresh(solution) method, which returns a new move bound to the current solution state, or Optional.empty() when the old move is no longer valid. Returning the old move instance after the solution has changed is wrong because Move instances are associated to the old solution state when they were created.

public final class MyRefreshableMove
        extends Move<MySolution, MyInstance>
        implements RefreshableMove<MyRefreshableMove, MySolution, MyInstance> {

    private final int candidate;

    @Override
    public Optional<MyRefreshableMove> refresh(MySolution solution) {
        if (!isStillApplicable(solution)) {
            return Optional.empty();
        }
        return Optional.of(new MyRefreshableMove(solution, candidate));
    }

    // Constructor, _execute(...), isStillApplicable(...), equals(...),
    // hashCode(...), and toString() omitted
}

Both list-backed and stream-backed neighborhoods are supported. A cache refill consumes the complete exploration result because it must identify the top candidates. The cache is cleared at the beginning of every improve(...) call, so candidates are never reused across separate searches.

An example of how to initialize a LocalSearchCachedBestImprovement using a cache size of 32 and the main objective is:

var improver = new LocalSearchCachedBestImprovement<
    MyRefreshableMove, MySolution, MyInstance
>(new MyRefreshableNeighborhood(), 32);

An explicit objective can also be supplied:

var improver = new LocalSearchCachedBestImprovement<
    MyRefreshableMove, MySolution, MyInstance
>(myCustomObjective, new MyRefreshableNeighborhood(), 32);

cacheSize must be greater than zero; there is no default value. A size of 1 leaves no move candidates to reuse and therefore behaves like ordinary best improvement, performing a full exploration for each selected move. Larger values use O(cacheSize) memory and make each refill approximately O(neighborhoodSize × log(cacheSize)), but amortize that cost across several iterations.

Use LocalSearchCachedBestImprovement when:

repeated full-neighborhood explorations are too expensive;
top candidates often remain valid after another move executes, even if their score change;
refreshing a candidate is cheaper than exploring the full neighborhood again;
an improving move is sufficient and we do not need to find the best available move in each iteration.

Prefer ordinary best or first improvement local search when moves are broadly invalidated by solution changes, refreshing is expensive, or selecting the current best move on every iteration is important.

LocalSearchFirstImprovement¶

LocalSearchFirstImprovement<M, S, I> explores the neighborhood and executes the first move that improves the current solution.

FirstImprovement(solution):
    moves = neighborhood.explore(solution)
    for move in moves:
        if move improves:
            execute move
            stop iteration
    stop if no improving move exists