Skip to main content

Move Types Reference

Move types define how Local Search explores the solution space. Each move type searches a different "neighborhood" of solutions by trying different types of object reassignments.

Overview​

When using the Local Search solver, you specify which move types to use. The solver tries each move type in order, looking for improvements to the objective function.

Key Concepts:

  • Hot container: The container contributing most to the objective (highest cost/constraint violation)
  • Move evaluation: Testing how a potential move affects the objective
  • Neighborhood: The set of solutions reachable by a specific move type

Quick Reference​

Move TypeCategoryComplexityUse When
SingleBasicO(objects × containers)Always - fundamental move type
SingleFastBasicO(objects × containers)Need faster convergence, can accept local optimum
SingleGreedyBasicO(objects × containers)Speed critical, single-threaded OK
SwapSwapO(objects²)Capacity constrained problems
SwapFullContainersSwapO(containers²)Moving full containers together
SwapFullWithEmptySwapO(objects × containers)Consolidating to free containers
SwapSampledSwapO(sample²)Large problems, need sampling
SingleChainChainO(objects² × containers)Capacity constrained, need 2-move chains
SingleChainFastChainO(objects² × containers)Chain moves with early termination
SingleEndChainChainO(objects² × containers)Better than SingleChain (recommended)
TripleLoopAdvancedO(objects³)Need to escape deep local optima
KLSearchAdvancedExpensiveGraph partitioning problems
ColocateGroupsGroupVariesNeed to move related objects together
GroupRoutingGroupVariesRouting with failover groups
FixedDestFixedO(objects)Filling specific containers
FixedSourceFixedO(objects × containers)Draining specific containers (ToFree)

Categories​

Basic Moves​

Single-object moves that form the foundation of most local search strategies:

Swap Moves​

Exchange objects between containers (useful when capacity-constrained):

Chain Moves​

Multi-move sequences where objects move in a chain:

Group Moves​

Move multiple related objects together:

Fixed Source/Destination​

Moves with predetermined source or destination containers:

Advanced Moves​

Complex move types for escaping local optima:

Choosing Move Types​

Default Configuration​

For most problems, start with:

solver_spec = {
    "localSearchSolverSpec": {
        "moveTypeList": [
            {"singleMoveTypeSpec": {}},  # Basic single-object moves
            {"swapMoveTypeSpec": {}},    # Add swap for capacity-constrained problems
        ]
    }
}
solver.add_solver(solver_spec)

By Problem Type​

Unconstrained or soft-constrained:

  • Start with Single only
  • Add SingleFast if convergence too slow

Capacity-constrained:

  • Use Single + Swap
  • Add SingleEndChain for better quality
  • Consider SwapSampled for large problems

Group placement:

  • Use ColocateGroups when groups must be together
  • Use GroupRouting for routing-aware placement

Container draining (ToFree):

  • Use FixedSource for draining specific containers
  • Much faster than exploring all source containers

Stuck in local optimum:

  • Add TripleLoop for deeper search
  • Try KLSearch for graph partitioning problems
  • Use multiple runs with different seeds

Performance Trade-offs​

PriorityMove TypesNotes
SpeedSingle or SingleFast onlyFast but may miss better solutions
QualitySingle + Swap + SingleEndChainBalanced speed/quality
Best SolutionAll applicable move typesSlow but thorough

Move Type Order Matters​

Move types are tried in the order specified. The solver:

  1. Tries moves from hottest container using first move type
  2. If improvement found → applies move, restart from step 1
  3. If no improvement → try second move type on same container
  4. If still no improvement → move to second hottest container, restart from step 1
  5. Continue until no improving move found from any container with any move type

Recommendation: Order move types from fast to slow:

move_type_list = [
    {"singleFastMoveTypeSpec": {}},      # Try fast moves first
    {"singleMoveTypeSpec": {}},          # Then thorough single moves
    {"swapMoveTypeSpec": {}},            # Then swaps
    {"singleEndChainMoveTypeSpec": {}},  # Finally, expensive chain moves
]

Common Patterns​

Fast Interactive Solving​

Quick responses for UI/dashboards:

# Use fast move types only
move_type_list = [{"singleFastMoveTypeSpec": {}}]

Production Rebalancing​

Balance speed and quality:

# Good default for most production use cases
move_type_list = [
    {"singleMoveTypeSpec": {}},
    {"swapMoveTypeSpec": {}},
]

Offline Optimization​

Take time to find best solution:

# Use all applicable move types
move_type_list = [
    {"singleMoveTypeSpec": {}},
    {"swapMoveTypeSpec": {}},
    {"singleEndChainMoveTypeSpec": {}},
    {"tripleLoopMoveTypeSpec": {}},
]

Draining Containers​

When using ToFreeSpec:

# Much faster than exploring all containers
move_type_list = [
    {
        "singleFixedSourceMoveTypeSpec": {
            "scopeItemList": {
                "scopeName": "container",
                "scopeItems": ["host1", "host2"],  # Containers to drain
            }
        }
    }
]

Configuring Move Types​

Each move type has its own configuration options. See individual move type pages for details.

Example: Configuring Swap with Sampling​

from rebalancer.specs import MoveTypeSpec, SampleSize, SwapMoveTypeSpec

swap_spec = MoveTypeSpec(
    swapMoveTypeSpec=SwapMoveTypeSpec(
        greedyOnSrc=True,  # Exit early on source objects
        sampleSize=SampleSize(
            defaultSampleSize=100,  # Sample 100 objects
        ),
    )
)

Example: Configuring Fixed Destination​

from rebalancer.specs import FixedDestMoveTypeSpec, MoveTypeSpec, SampleSize

fixed_dest_spec = MoveTypeSpec(
    fixedDestMoveTypeSpec=FixedDestMoveTypeSpec(
        specialContainer="spare_capacity_container",
        sampleSize=SampleSize(defaultSampleSize=50),
    )
)

Complexity Analysis​

Understanding complexity helps choose appropriate move types for your problem size:

Move TypePer-Container ComplexityProblem Size Limit
SingleO(N × C)100K+ objects
SingleFastO(N × C) with early exit100K+ objects
SwapO(N²)10K objects
SingleChainO(N² × C)5K objects
TripleLoopO(N³)1K objects

Where N = objects per container, C = number of containers

Tip: For large problems (>10K objects), prefer:

  • Single, SingleFast, or SingleRandomStratified (sampled)
  • SwapSampled instead of Swap
  • Avoid TripleLoop and KLSearch

Troubleshooting​

Problem: Solver too slow​

Diagnosis: Too many objects or expensive move types

Solutions:

  • Use faster move types (SingleFast, SingleGreedy)
  • Add sampling to expensive types (SwapSampled)
  • Reduce time limits per move type
  • Use stratified sampling moves

Problem: Stuck in local optimum​

Diagnosis: Terminates quickly with NO_IMPROVING_MOVE but poor objective

Solutions:

  • Add more powerful move types (SingleEndChain, TripleLoop)
  • Use better initial assignment
  • Try multiple runs with different random seeds
  • Check if problem is feasible

Problem: Not improving constraints​

Diagnosis: Solution violates constraints

Solutions:

  • Verify constraints are achievable
  • Use move types that can escape constraint violations (Swap, Chain moves)
  • Check if initial assignment is extremely broken
  • Increase constraint penalties (invalidCost)

Next Steps​

  • Choose a move type from the categories above to see detailed documentation
  • Review Local Search Solver to understand how move types fit into the solver
  • See Solver Strategies for multi-stage solving with different move types
  • Check Performance Guide for tuning move type performance

Source Code​