Skip to main content

Local Search Solver

The Local Search solver uses iterative improvement to find good solutions quickly. It's the recommended solver for large problems (>10,000 objects).

How It Works​

Local Search starts with the current assignment and repeatedly makes "moves" that improve the objective:

  1. Start with initial assignment
  2. Generate candidate moves (e.g., move object X to container Y)
  3. Evaluate each move's impact on objective
  4. Apply the best improving move
  5. Repeat until no improving moves found (or hit limits)

This finds a local optimum - a solution where no single move improves things further.

Quick Example​

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            timeLimitMs=30000,  # Stop after 30 seconds
            movesLimit=100000,  # Or after 100K iterations
        )
    )
)

solution = solver.solve()

# Check termination reason
print(f"Stopped because: {solution.profile.terminationReason}")
print(f"Iterations: {solution.profile.iterations}")
print(f"Time: {solution.profile.solveTime}ms")

Configuration Parameters​

ParameterTypeDefaultDescription
solveTimeintNo limitMaximum solve time in milliseconds
stopAfterMovesintNo limitMaximum number of moves to apply
moveTypeListlist<MoveTypeSpec>AutoWhich move types to use (see below)
randomSeedintRandomRandom seed for reproducibility
enableObjectPotentialSortingboolfalseEnable potential-based object sorting
minHotObjectsint1Minimum hot objects to consider

Move Types​

Local Search explores different types of moves. Each move type searches a different "neighborhood" of solutions. See the Move Types Reference for complete documentation of all 27 move types.

Common Move Types​

Single: Move one object to a different container

  • When: Always useful - most fundamental move type
  • Cost: O(objects × containers) per iteration
  • Example: Move task5 from host1 to host3

Swap: Swap two objects between containers

  • When: Capacity constrained (can't just add objects)
  • Cost: O(objects²) per iteration
  • Example: Swap task5 on host1 with task8 on host3

TripleLoop: Try complex multi-object rearrangements

  • When: Need to escape local optima
  • Cost: Expensive, O(objects³)
  • Example: Move 3+ objects in a cycle

Specialized Move Types​

KLSearch: Kernighan-Lin style search with sequences of moves

  • When: Graph partitioning-style problems
  • Cost: Expensive but powerful

Chain Moves: Move sequences of objects in a chain

  • When: Moving objects creates opportunities for other moves
  • Cost: Medium
  • Best: SingleEndChain (recommended over SingleChain)

Group Moves: Move entire groups together

  • When: Using MoveGroupSpec or colocation goals
  • Cost: Depends on group sizes
  • Example: ColocateGroups

Fixed Source/Dest: Only consider moves from/to specific containers

  • When: Draining specific containers (ToFree) or filling specific containers
  • Cost: Reduced search space, faster
  • Example: FixedSource for draining

Configuring Move Types​

from rebalancer.specs import (
    LocalSearchSolverSpec,
    MoveTypeSpec,
    SingleMoveTypeSpec,
    SolverSpec,
    SwapMoveTypeSpec,
)

# Default: auto-selected move types
solver.add_solver(SolverSpec(localSearchSolverSpec=LocalSearchSolverSpec()))

# Custom: specify exact move types to use
solver.add_solver(
    SolverSpec(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                MoveTypeSpec(singleMoveTypeSpec=SingleMoveTypeSpec()),
                MoveTypeSpec(swapMoveTypeSpec=SwapMoveTypeSpec()),
            ]
        )
    )
)

Termination Conditions​

Local Search stops when:

  1. No improving move found - Reached local optimum (UNABLE_TO_FIND_MORE_MOVES)
  2. Move limit reached - Hit stopAfterMoves (HIT_MOVE_LIMIT)
  3. Time limit reached - Hit solveTime (HIT_TIME_LIMIT)
  4. Plateau timeout - Stuck in plateau too long (HIT_PLATEAU_TIME)

Check termination reason from the solver report:

# Access the solver report (first solver if multiple)
solver_report = solution["solverSummaries"][0]

end_reason = solver_report["endReason"]
if end_reason == "UNABLE_TO_FIND_MORE_MOVES":
    print("Found local optimum")
elif end_reason == "HIT_MOVE_LIMIT":
    print("Hit iteration limit - may improve with more moves")
elif end_reason == "HIT_TIME_LIMIT":
    print("Hit time limit - may improve with more time")

Performance Characteristics​

Scalability​

Problem SizeTypical TimeIterations
100 objects, 10 containers<1 second100-1,000
1,000 objects, 100 containers1-5 seconds1,000-10,000
10,000 objects, 1,000 containers10-60 seconds10,000-100,000
100,000 objects, 10,000 containers1-10 minutes100,000-1,000,000

Memory Usage​

  • Per object: ~100-200 bytes
  • Per container: ~50-100 bytes
  • Example: 100K objects + 10K containers ≈ 20MB

Parallelization​

Local Search uses multi-threading for move evaluation:

  • Move generation: Can be parallelized across move types
  • Move evaluation: Parallelized across candidate moves
  • Cores used: Effectively utilizes multiple cores (typically 2-8+)
  • Note: Some move types like SingleGreedy are single-threaded

Solution Quality​

Local Search provides no optimality guarantee, but empirically:

  • Typically 95-99% of optimal for well-structured problems
  • Quality improves with more time/iterations
  • Quality depends on initial assignment

Quality Factors​

Good quality when:

  • Good initial assignment
  • Well-balanced problem
  • Sufficient time/moves
  • Appropriate move types

Poor quality when:

  • Terrible initial assignment (many broken constraints)
  • Highly constrained problem (few feasible solutions)
  • Insufficient time/moves
  • Wrong move types for problem structure

Improving Solution Quality​

Increase Limits​

# Give more time
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            timeLimitMs=300000,  # 5 minutes instead of 30 seconds
            movesLimit=1000000,  # 1M moves instead of 100K
        )
    )
)

Better Initial Assignment​

# Start with a better assignment
# E.g., pre-balance object counts before running solver
initial_assignment = distribute_evenly(objects, containers)
solver.set_assignment(initial_assignment)

Enable More Move Types​

By default, Local Search auto-selects appropriate move types. To use all available move types or a custom set, specify them explicitly using moveTypeList:

from rebalancer.specs import (
    LocalSearchSolverSpec,
    MoveTypeSpec,
    SingleChainMoveTypeSpec,
    SingleMoveTypeSpec,
    SolverSpec,
    SwapMoveTypeSpec,
    TripleLoopMoveTypeSpec,
)

# Use a comprehensive set of move types
solver.add_solver(
    SolverSpec(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                MoveTypeSpec(singleMoveTypeSpec=SingleMoveTypeSpec()),
                MoveTypeSpec(swapMoveTypeSpec=SwapMoveTypeSpec()),
                MoveTypeSpec(tripleLoopMoveTypeSpec=TripleLoopMoveTypeSpec()),
                MoveTypeSpec(singleChainMoveTypeSpec=SingleChainMoveTypeSpec()),
            ]
        )
    )
)

Run Multiple Times​

from rebalancer import ProblemSolver
from rebalancer.specs import LocalSearchSolverSpec, SolverSpec

# Try multiple random seeds, pick best
best_solution = None
best_objective = float("inf")

for seed in range(10):
    solver = ProblemSolver(service_name="rebalancer", service_scope="seed-search")
    # ... set up problem ...
    solver.add_solver(
        SolverSpec(
            localSearchSolverSpec=LocalSearchSolverSpec(randomSeed=seed)
        )
    )
    solution = solver.solve()

    objective = solution["finalObjective"]["value"]
    if objective < best_objective:
        best_objective = objective
        best_solution = solution

# best_solution is the best of 10 runs

Common Patterns​

Fast Interactive Rebalancing​

Quick responses for interactive tools:

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            timeLimitMs=5000,  # 5 second limit
        )
    )
)

Production Rebalancing​

Balance speed and quality:

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            timeLimitMs=60000,  # 1 minute
            movesLimit=500000,  # 500K moves
        )
    )
)

Offline Optimization​

Take time to find best solution:

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            timeLimitMs=3600000,  # 1 hour
            # No move limit - run until no improvements
        )
    )
)

Draining Containers​

Use FixedSource move type for draining specific containers (e.g., with ToFreeSpec):

from rebalancer.specs import (
    LocalSearchSolverSpec,
    MoveTypeSpec,
    SingleFixedSourceMoveTypeSpec,
    SolverSpec,
)

# When draining containers, use FixedSource to only consider
# moves from the containers being drained.
solver.add_solver(
    SolverSpec(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                MoveTypeSpec(
                    singleFixedSourceMoveTypeSpec=SingleFixedSourceMoveTypeSpec()
                )
            ]
        )
    )
)

Debugging Poor Results​

Problem: Solution not improving​

Diagnosis:

print(f"Iterations: {solution["profile"].iterations}")
print(f"Time: {solution["profile"].solveTime}ms")
print(f"Reason: {solution["profile"].terminationReason}")

Solutions:

  • Increase time/move limits
  • Check if initial assignment is extremely poor
  • Verify goals/constraints are achievable

Problem: Slow convergence​

Diagnosis:

  • Many iterations but small improvements
  • Terminating due to limits, not local optimum

Solutions:

  • Try different move types
  • Improve initial assignment
  • Simplify problem (fewer goals/constraints)

Problem: Stuck in local optimum​

Diagnosis:

  • Terminates quickly with NO_IMPROVING_MOVE
  • Objective value seems poor compared to expectations

Solutions:

  • Use more powerful move types (TripleLoop, KLSearch)
  • Try multiple runs with different seeds
  • Use better initial assignment
  • Consider using Optimal solver for comparison

Problem: Too slow​

Diagnosis:

  • Taking too long for problem size
  • Not enough iterations in time limit

Solutions:

  • Use simpler move types (SingleMove only)
  • Reduce time limit (accept worse solution)
  • Simplify problem
  • Check for performance bottlenecks in goals/constraints

Comparison with Optimal Solver​

AspectLocal SearchOptimal
Solution quality95-99% of optimal100% optimal*
SpeedFast (seconds)Slow (minutes to hours)
Scalability1M+ objects<10K objects
GuaranteesNoneOptimality gap
DeterminismRandom (without seed)Deterministic
MemoryLowHigh (can OOM)

* Given enough time

Recommendation: Use Local Search for production, Optimal for validation/small problems.

Advanced: Multi-Stage Solving​

Local Search supports multi-stage solving using LocalSearchStageSolverSpec, where each stage can use different move types and focus on different objectives:

from rebalancer.specs import (
    LocalSearchSolverSpec,
    LocalSearchStageSolverSpec,
    LocalSearchStageSpec,
    MoveTypeSpec,
    SingleFastMoveTypeSpec,
    SingleMoveTypeSpec,
    SolverSpec,
)

# Stage 1: Fast coarse moves
stage1 = LocalSearchStageSpec(
    name="coarse",
    begin=0,
    end=2,  # Focus on objectives 0-1
    solverSpec=LocalSearchSolverSpec(
        moveTypeList=[
            MoveTypeSpec(singleFastMoveTypeSpec=SingleFastMoveTypeSpec())
        ],
        stopAfterMoves=10000,
    ),
)

# Stage 2: Fine-tuning with more expensive moves
stage2 = LocalSearchStageSpec(
    name="fine-tuning",
    begin=0,
    end=3,  # Focus on all objectives 0-2
    solverSpec=LocalSearchSolverSpec(
        moveTypeList=[MoveTypeSpec(singleMoveTypeSpec=SingleMoveTypeSpec())],
        stopAfterMoves=5000,
    ),
)

solver.add_solver(
    SolverSpec(
        localSearchStageSolverSpec=LocalSearchStageSolverSpec(
            stageSpecs=[stage1, stage2],
            solveTime=60000,  # Overall time limit
        )
    )
)

See Solver Strategies for multi-stage solving.

Troubleshooting​

Problem: Non-deterministic results​

Cause: Random seed not set

Solution:

solver.addSolver(SolverSpecs(localSearchSolverSpec=LocalSearchSolverSpec(seed=42)))

Problem: Violating constraints​

Cause: Constraints initially broken, being treated as goals

Solution: Check initial assignment, or increase constraint penalty:

solver.add_constraint(spec, invalid_cost=1000.0)

Problem: Different results each run​

Cause: Default random seed varies

Solution: Set explicit seed for reproducibility

Next Steps​