Local Search

Local search algorithms iteratively improve a solution by making small changes called “moves.” This is where the solver spends most of its time finding better solutions.

How It Works

Start with initial solution
Repeat until termination:
    1. Generate possible moves
    2. Evaluate each move's score impact
    3. Select a move based on acceptance criteria
    4. Apply the move
    5. Update best solution if improved

Local Search Algorithms

Late Acceptance

Default algorithm. Accepts moves that improve on the solution from N steps ago.

• Balances exploration and exploitation
• Escapes local optima by accepting slightly worse moves
• Simple and effective for most problems

Hill Climbing

Only accepts moves that improve the score:

• Fast convergence
• Gets stuck in local optima
• Best for easy problems or quick iterations

Tabu Search

Maintains a list of recently made moves and forbids reversing them:

• Avoids cycles and revisiting solutions
• Explores more of the search space
• Memory overhead for tabu list

Simulated Annealing

Accepts worse moves with probability that decreases over time:

• “Temperature” controls acceptance probability
• High temperature = more exploration
• Low temperature = more exploitation
• Inspired by metallurgy annealing process

Great Deluge

Accepts moves above a rising “water level” threshold:

• Threshold increases over time
• Forces gradual improvement
• Similar to simulated annealing

Move Selection

Local search evaluates moves generated by move selectors:

Move Examples:
├── Change Move: lesson.room = Room B → Room C
├── Swap Move: lesson1.room ↔ lesson2.room
├── 2-Opt Move: Reverse segment in route
└── Custom Move: Domain-specific change

See Move Selectors for details.

Understanding the Search

Score Improvement Curve

Score
  ^
  |     ****
  |    *    **
  |   *       ***
  |  *           ****
  | *                ********
  |*                         ***************
  +---------------------------------> Time
     Construction   Local Search

Rapid improvement early, then diminishing returns.

Local Optima

A local optimum is a solution where no single move improves the score, but better solutions exist:

Score
  ^
  |        *
  |       * *        Global optimum
  |      *   *      ↓
  |     *     *    *
  |    *       *  * *
  |   *    ↑    **   *
  |  *     Local      *
  |        optimum
  +------------------------→ Solution Space

Algorithms like Late Acceptance and Tabu Search help escape local optima.

Termination

Local search runs until termination:

TerminationConfig(
    spent_limit=Duration(minutes=5),      # Time limit
    best_score_limit="0hard/0soft",       # Score target
    unimproved_spent_limit=Duration(seconds=60),  # Plateau detection
)

Choosing Termination Time

More time generally means better scores, with diminishing returns.

Monitoring Progress

def on_progress(event: BestSolutionChangedEvent):
    print(f"Time: {event.time_spent}")
    print(f"Score: {event.new_best_score}")
    print(f"Initialized: {event.is_new_best_solution_initialized}")

solver.add_event_listener(on_progress)

Score Plateaus

When the score stops improving:

1. Stuck in local optimum: Algorithm can’t find better moves
2. Near optimal: Little room for improvement
3. Constraint conflict: Hard constraints blocking progress

Detecting Plateaus

TerminationConfig(
    unimproved_spent_limit=Duration(seconds=60)  # Stop if no improvement
)

Algorithm Selection

Start with the default (Late Acceptance) and only change if benchmarking shows improvement.

Performance Tips

1. Let It Run Longer

More time usually means better scores.

2. Optimize Constraints

Slow constraints = fewer moves evaluated per second.

3. Use Appropriate Moves

Some moves work better for certain problems (see Move Selectors).

4. Benchmark

Test different algorithms and parameters on your specific problem.

Next Steps

• Move Selectors - Customize move generation
• Benchmarking - Compare configurations