Skip to main content

SingleGreedy

Move Type: Basic Complexity: O(1) to O(objects × containers) with early termination

Stop as soon as ANY improving move is found. Ultra-fast convergence, but may miss better moves. Use when speed matters more than solution quality.

Overview​

SingleGreedy evaluates single object moves but stops immediately when it finds the first move that improves the objective. Unlike SingleFast which explores at least one object fully, SingleGreedy can stop even earlier - mid-way through exploring destinations for a single object.

Use when:

  • Speed is critical (interactive/real-time systems)
  • Quick "good enough" solution needed
  • Problem updates frequently (re-runs are cheap)
  • Initial assignment is already decent

Avoid when:

  • Solution quality is important
  • Making many moves at once (may thrash)
  • Problem is small (overhead dominates)
  • Need deterministic/reproducible results

Quick Example​

# Ultra-fast: stops at first improving move
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleGreedyMoveTypeSpec(),  # Fastest convergence
            ]
        )
    )
)

Parameters​

ParameterTypeRequiredDefaultDescription
(none)---SingleGreedy has no configuration parameters

How It Works​

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

  1. Select object: Pick object from hot container
  2. Try destination: Pick a different container
  3. Evaluate move: Test moving object to that container
  4. Early exit: If move improves objective → STOP and apply it
  5. Continue: Otherwise, try next destination or next object
  6. Worst case: If no improving move found, try all combinations

Visual Example​

Hot Container (100 objects):
  obj1 → container_A: improvement found! ✓ STOP HERE

SingleGreedy returns after evaluating just 1 move!

Comparison with other move types:
- SingleGreedy:  Tries 1 move, finds improvement, stops
- SingleFast:    Tries 1000 moves (all destinations for obj1), picks best
- Single:        Tries 100,000 moves (all objects × all destinations), picks best

Greedy vs Fast vs Full​

Move TypeEvaluation StrategyTypical Moves EvaluatedQuality
SingleGreedyStop at first improvement1-100Lowest
SingleFastTry all destinations for first improving object100-1KMedium
SingleTry all objects and destinations10K-1MHighest

Complexity​

Best case: O(1) - First move tried improves objective

Average case: O(N × C / k) where k = improvement frequency

Worst case: O(N × C) - No improving moves found

Where:

  • N = number of objects in hot container
  • C = number of containers
  • k = average number of moves tried before finding improvement

Example - Interactive system:

  • Hot container: 1,000 objects
  • System: 100 containers
  • Typical run: Finds improvement in 10-100 moves (vs 100K for Single)

Usage Patterns​

Real-Time/Interactive Systems​

Ultra-fast response for dashboards and UIs:

# Ultra-fast solver for UI/dashboard (100ms limit)
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            solveTime=0.1,  # 100ms limit for interactive response
            moveTypeList=[
                SingleGreedyMoveTypeSpec(),  # First improvement = instant response
            ],
        )
    )
)

Continuous Rebalancing​

Frequent small adjustments:

# Run every 10 seconds for continuous rebalancing
# Each run makes 1-2 quick improvements
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            solveTime=1,  # 1 second per run
            moveTypeList=[
                SingleGreedyMoveTypeSpec(),  # Fast incremental improvements
            ],
        )
    )
)

Combined with Slower Moves​

Use greedy for quick wins, then thorough search:

# Multi-stage: greedy for quick wins, then thorough search
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleGreedyMoveTypeSpec(),  # Quick improvements first
                SingleMoveTypeSpec(),  # Then thorough exploration
                SwapMoveTypeSpec(),  # Finally handle capacity constraints
            ]
        )
    )
)

Quick Warm-Start​

Fast initial solution before refinement:

# Stage 1: Fast warm-start with greedy
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            solveTime=5,  # Quick 5 second warm-start
            moveTypeList=[
                SingleGreedyMoveTypeSpec(),  # Get to "good enough" quickly
            ],
        )
    )
)

# Stage 2: Refine with thorough search
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            solveTime=60,  # Spend more time refining
            moveTypeList=[
                SingleMoveTypeSpec(),  # Find best moves
                SwapMoveTypeSpec(),  # Handle capacity constraints
            ],
        )
    )
)

Performance Characteristics​

Speed vs Quality Trade-off​

MetricSingleGreedySingleFastSingle
SpeedFastestFastSlow
Moves evaluated1-100100-1K10K-1M
Solution quality60-80% optimal80-95% optimal95-100% optimal
Iteration time<1ms1-10ms10-1000ms
ConvergenceFast (many iterations)MediumSlow (few iterations)

When Does It Help?​

SingleGreedy helps when:

  • Frequent updates: Problem changes often, re-runs are common
  • Good initial state: Already near optimal, just need tweaks
  • Interactive use: Human waiting for response
  • Many small improvements: Easy to find some improvement quickly

SingleGreedy does NOT help when:

  • Poor initial state: Need big improvements, not first improvement
  • Rare improvements: Takes long to find ANY improvement
  • Quality critical: Can't accept mediocre solutions
  • One-shot optimization: Single run needs to be as good as possible

Comparison with Variants​

Move TypeEarly Exit StrategyExploration LevelUse Case
SingleNoneFull (all objects × all destinations)Quality critical
SingleFastFirst improving objectOne object fullyBalanced
SingleGreedyFirst improving moveMinimalSpeed critical
SingleRandomBatchesBatch-basedRandom samplesVery large problems

Decision tree:

  1. Need best solution? → Single
  2. Balanced quality/speed? → SingleFast
  3. Need fastest response? → SingleGreedy
  4. Problem huge (100K+ objects)? → SingleRandomBatches

Troubleshooting​

Problem: Making many small moves, but objective not improving much​

Diagnosis: Greedy approach finding local improvements but missing better global moves

Solutions:

  • Switch to SingleFast or Single for better moves
  • Use SingleGreedy for quick wins, then switch to thorough search
  • Combine with other move types (Swap, Chain)
  • Increase iteration limit to let greedy make more sequential moves

Problem: Not finding any improving moves​

Diagnosis: Already at local optimum OR improvements are rare

Solutions:

  • This is expected at local optimum - switch to more powerful move types
  • Try Swap or SingleEndChain
  • Check if constraints are too restrictive
  • Verify objective function is correct

Problem: Solution quality much worse than expected​

Diagnosis: Greedy strategy too aggressive, missing much better moves

Solutions:

  • Use SingleFast for better quality (small speed cost)
  • Use Single for best quality (larger speed cost)
  • Run greedy multiple times with different random seeds
  • Use greedy for warm-start, then refine with Single

Problem: Still too slow for interactive use​

Diagnosis: Even single move evaluation is expensive

Solutions:

  • Check objective function efficiency (is evaluation O(1)?)
  • Reduce problem size (fewer objects/containers)
  • Set strict solveTime limit (e.g., 100ms)
  • Pre-filter candidate destinations
  • Consider if full rebalancing is needed for every change

When to Use SingleGreedy​

DO use when:

  • Interactive systems (dashboards, UIs)
  • Continuous rebalancing (frequent small changes)
  • Speed critical (<10ms response time needed)
  • Initial solution is already decent
  • Running frequently (can iterate to good solution over time)

DO NOT use when:

  • One-shot optimization (single run needs to be optimal)
  • Solution quality is critical
  • Making infrequent large-scale changes
  • Need deterministic/reproducible results
  • Poor initial assignment (need big improvements)

Similar speed optimization:

Better quality alternatives:

  • Single - Full exploration, best single moves
  • Swap - Capacity-constrained problems

Complementary:

  • Use SingleGreedy first for quick wins
  • Follow with Single/Swap for refinement
  • Combine in multi-stage solver

Source Code​

Next Steps​