Skip to main content

Single

Move Type: Basic Complexity: O(objects × containers)

Move one object at a time to any destination container. This is the most fundamental move type and should be included in almost every Local Search configuration.

Overview​

Single evaluates moving each object from the hot container to every possible destination container. It explores all single-object moves in parallel using multi-threading.

Use when:

  • Always - this is the foundation of Local Search
  • Problems with soft constraints or unconstrained
  • Initial solver configuration

Avoid when:

  • Need faster convergence (use SingleFast instead)
  • Single-threaded environment required (use SingleGreedy)

Quick Example​

# Use Single move type (most basic - move one object at a time)
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleMoveTypeSpec(),  # Evaluate all single-object moves
            ]
        )
    )
)

Parameters​

ParameterTypeRequiredDefaultDescription
(none)---Single move type has no configuration parameters

How It Works​

Given a hot container (the container contributing most to the objective):

  1. Select object: Pick one object from the hot container (the "hot object")
  2. Select destination: Pick a different container (the "destination container")
  3. Evaluate: Test moving the hot object to the destination container
  4. Repeat: Try all combinations of (hot object, destination container)
  5. Apply best: Apply the move that improves the objective most

All moves are evaluated in parallel to benefit from multi-threading.

Visual Example​

Before:                          After (if move applied):
┌─────────────┐                 ┌─────────────┐
│ Hot         │                 │ Hot         │
│ Container   │                 │ Container   │
│  • obj1     │  ──move obj1──> │  • obj2     │
│  • obj2     │                 │  • obj3     │
│  • obj3     │                 └─────────────┘
└─────────────┘                 ┌─────────────┐
┌─────────────┐                 │ Dest        │
│ Dest        │                 │ Container   │
│ Container   │                 │  • obj4     │
│  • obj4     │                 │  • obj1  ←  │
└─────────────┘                 └─────────────┘

Complexity​

Moves evaluated per iteration: O(N × C)

Where:

  • N = number of objects in hot container
  • C = number of destination containers

Example:

  • Hot container has 100 objects
  • System has 50 containers
  • Moves evaluated = 100 × 50 = 5,000 moves

Parallelization: All moves evaluated in parallel using available CPU cores

Usage Patterns​

Basic Configuration​

Most common usage - include Single in move type list:

# Single move type is the foundation - include it in almost all configurations
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleMoveTypeSpec(),  # Always start with Single
            ]
        )
    )
)

Combined with Other Move Types​

Typical pattern - Single as foundation, other types for special cases:

# Typical pattern: Single as foundation, other types for special cases
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleMoveTypeSpec(),  # Try simple moves first
                SwapMoveTypeSpec(),  # Then try swaps for capacity-constrained
            ]
        )
    )
)

Load Balancing​

Use Single for straightforward load balancing:

# Balance CPU across hosts using Single moves
solver.addConstraint(
    ConstraintSpecs(
        capacitySpec=CapacitySpec(
            name="cpu-capacity",
            scope="host",
            dimension="cpu",
            limit=Limit(globalLimit=16.0),  # Max 16 cores per host
        )
    )
)

solver.addGoal(
    GoalSpecs(
        balanceSpec=BalanceSpec(name="balance-cpu", scope="host", dimension="cpu")
    ),
    weight=1.0,
)

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleMoveTypeSpec(),  # Single moves are sufficient for balancing
            ]
        )
    )
)

Performance Characteristics​

Scalability​

Problem SizeObjects/ContainerContainersTypical Time per Iteration
Small1010<1ms
Medium10010010-50ms
Large1,0001,0000.5-2s
Very Large10,00010,00010-60s

Multi-threading​

Single move type benefits significantly from multi-threading:

  • All object-destination pairs evaluated in parallel
  • Scales well up to 8-16 cores
  • CPU-bound (evaluation is fast, parallelization helps)

Memory Usage​

  • Minimal memory overhead beyond problem state
  • Each move evaluation is independent (no temporary state)
  • Safe for large problems (100K+ objects)

Comparison with Variants​

Move TypeSpeedThoroughnessUse Case
SingleMediumCompleteDefault choice, thorough search
SingleFastFastPartialFaster convergence, may miss optimal
SingleGreedyFastestGreedySingle-threaded, speed critical
SingleRandomBatchesFastSampledParallel batching for speed

Recommendation: Start with Single. Only switch to variants if:

  • Speed is critical → SingleFast or SingleGreedy
  • Problem is extremely large → SingleRandomBatches with sampling

Troubleshooting​

Problem: Single moves too slow​

Diagnosis: Large problem (many objects or containers)

Solutions:

  • Switch to SingleFast for early termination
  • Use SingleRandomStratified with sampling
  • Reduce problem size by filtering containers/objects
  • Check if moves are being evaluated inefficiently

Problem: Not finding good solutions​

Diagnosis: Single moves alone may not escape local optima

Solutions:

  • Add Swap for capacity-constrained problems
  • Add SingleEndChain for 2-move sequences
  • Try multiple solver runs with different random seeds
  • Improve initial assignment quality

Problem: Getting stuck in local optimum quickly​

Diagnosis: Simple moves can't improve objective further

Solutions:

  • Add more powerful move types (Swap, Chain, TripleLoop)
  • Check if constraints are blocking improvements
  • Verify initial assignment isn't extremely broken
  • Review objective function for issues

Variants:

Complementary:

Source Code​

Next Steps​