Skip to main content

SwapSampled

Move Type: Swap Complexity: O(sample²) instead of O(objects²)

Sample a subset of objects for swapping instead of trying all combinations. Essential for large-scale capacity-constrained problems.

Overview​

SwapSampled uses SwapMoveTypeSpec with the sampleSize parameter to limit the number of swap combinations evaluated. Instead of trying all possible object pairs, it samples objects from both source and destination containers.

Use when:

  • Problem is large (>10K objects)
  • Full Swap is too slow
  • Capacity constraints require swaps but exhaustive search is impractical

Avoid when:

  • Problem is small enough for full Swap
  • Need to explore all possible swaps
  • Sample size might miss important swaps

Quick Example​

# Use SwapMoveTypeSpec with sampling for large problems
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleMoveTypeSpec(),
                SwapMoveTypeSpec(
                    sampleSize=SampleSize(
                        defaultSampleSize=100,  # Sample 100 objects on each side
                    ),
                ),
            ]
        )
    )
)

Parameters​

SwapSampled uses SwapMoveTypeSpec with these key parameters:

ParameterTypeRequiredDefaultDescription
sampleSizeSampleSizeYesnullControls sampling on both src and dst
partitionNameToExploreSwapsWithinObjectGroupstringNonullOnly swap within same group
greedyOnSrcboolNofalseExit early when trying src objects
greedyOnDstboolNofalseExit early when trying dst objects
destinationsToExploreDestinationsToExploreOptionsNonullRestrict destination containers

SampleSize Structure​

FieldTypeDescription
defaultSampleSizeint32Default sample size for all objects
objectToSampleSizemap<string, int32>Per-object sample size override

How It Works​

Given a hot container and cold container:

  1. Sample source objects: Select up to sampleSize objects from hot container
  2. Sample destination objects: Select up to sampleSize objects from cold container
  3. Evaluate swaps: Test swapping each sampled source object with each sampled destination object
  4. Apply best: Apply the best swap that improves the objective

Visual Example​

Full Swap (100 × 100 = 10,000 swaps):
Hot Container (100 objects) × Cold Container (100 objects)
  = 10,000 swap combinations to evaluate

SwapSampled with sampleSize=10 (10 × 10 = 100 swaps):
Hot Container (sample 10) × Cold Container (sample 10)
  = 100 swap combinations to evaluate (100x speedup!)

Comparison with Full Swap​

AspectSwapSwapSampled
CombinationsN × Msample × sample
SpeedSlow for large N,MMuch faster
QualityBest swap guaranteedGood swap likely
Use caseSmall/medium problemsLarge problems

Complexity​

Moves evaluated per iteration: O(S² × C)

Where:

  • S = sample size (from sampleSize parameter)
  • C = number of cold containers
  • Compare to full Swap: O(N × M × C) where N,M = object counts

Example - Large problem:

  • Hot container: 10,000 objects
  • Cold containers: 1,000 containers with ~10,000 objects each
  • Full Swap: 10,000 × 10,000 × 1,000 = 100 billion evaluations
  • SwapSampled (sample=100): 100 × 100 × 1,000 = 10 million evaluations (10,000x speedup!)

Usage Patterns​

Basic Sampling​

Default usage with reasonable sample size:

# Reasonable sample size for most large problems
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SwapMoveTypeSpec(
                    sampleSize=SampleSize(
                        defaultSampleSize=100,
                    ),
                ),
            ]
        )
    )
)

Per-Object Sample Size​

Different sample sizes for different objects:

# Higher sample size for important objects
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SwapMoveTypeSpec(
                    sampleSize=SampleSize(
                        defaultSampleSize=50,  # Default for most objects
                        objectToSampleSize={
                            "critical_obj1": 200,  # More sampling for critical objects
                            "critical_obj2": 200,
                        },
                    ),
                ),
            ]
        )
    )
)

Large Problem Configuration​

Aggressive sampling for very large problems:

# Small sample for problems with 100K+ objects
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SwapMoveTypeSpec(
                    sampleSize=SampleSize(
                        defaultSampleSize=50,  # Aggressive sampling for speed
                    ),
                ),
            ]
        )
    )
)

Combined with Greedy Flags​

Sample + early exit for maximum speed:

# Sample + early exit = maximum speed
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SwapMoveTypeSpec(
                    sampleSize=SampleSize(
                        defaultSampleSize=50,
                    ),
                    greedyOnSrc=True,  # Exit early when trying source objects
                    greedyOnDst=True,  # Exit early when trying destination objects
                ),
            ]
        )
    )
)

Adaptive Sampling Strategy​

Start with small sample, increase if needed:

# Start with small sample, increase in later stages
# Note: This would require LocalSearchStageSolverSpec
# Showing concept with single-stage for simplicity
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleMoveTypeSpec(),
                SwapMoveTypeSpec(
                    sampleSize=SampleSize(
                        defaultSampleSize=100,  # Start moderate
                    ),
                ),
                SwapMoveTypeSpec(
                    sampleSize=SampleSize(
                        defaultSampleSize=500,  # Increase for refinement
                    ),
                ),
            ]
        )
    )
)

Performance Characteristics​

Problem SizeObjects per ContainerRecommended Sample SizeSpeedup vs Full
Medium100-1K50-10010-100x
Large1K-10K100-500100-1000x
Very Large>10K500-10001000-10000x

Sampling Strategy​

Conservative (higher quality, slower):

  • Sample size = sqrt(object count)
  • Example: 10,000 objects → sample 100

Balanced (good trade-off):

  • Sample size = 100-200 (fixed)
  • Works well for most problems

Aggressive (maximum speed):

  • Sample size = 50 or less
  • Accept lower quality for speed

Comparison with Variants​

Move TypeSpeedCompletenessUse Case
SwapSlowCompleteSmall/medium (<10K objects)
SwapSampledFastSampledLarge (>10K objects)
SwapFullContainersMediumContainer-levelFull container swaps
SwapFullWithEmptyFastEmpty targets onlyConsolidation

Troubleshooting​

Problem: SwapSampled not finding good moves​

Diagnosis: Sample size too small, missing good swaps

Solutions:

  • Increase defaultSampleSize (try doubling it)
  • Use per-object sampling for important objects
  • Try multiple runs with different random seeds
  • Check if full Swap finds better moves (on smaller subset)

Problem: Still too slow​

Diagnosis: Sample size too large or problem extremely large

Solutions:

  • Reduce sample size (try 50 or less)
  • Enable greedyOnSrc and greedyOnDst for early exit
  • Restrict destinations with destinationsToExplore
  • Consider if swaps are necessary (try other move types)

Problem: Solution quality much worse than expected​

Diagnosis: Sampling missing critical swaps

Solutions:

  • Increase sample size for better coverage
  • Use stratified sampling (sample from different object groups)
  • Combine with full Swap in multi-stage approach
  • Try SingleEndChain as alternative

Problem: Non-deterministic results​

Diagnosis: Random sampling produces different results each run

Solutions:

  • Set randomSeed in LocalSearchSolverSpec for reproducibility
  • Use larger sample size for more stable results
  • Run multiple times and pick best result
  • Accept variance as trade-off for speed

Choosing Sample Size​

Rule of thumb: Sample size² should be > number of containers

Example calculation:

  • 1000 containers
  • sqrt(1000) ≈ 32
  • Recommended sample size: 50-100

Validation:

  • Run with sample size S
  • Run with sample size 2×S
  • If results similar → S is sufficient
  • If results much better with 2×S → increase S

Variants:

Alternatives:

Complementary:

  • Single - Try before SwapSampled (simpler)
  • Greedy flags - Combine for even faster convergence

Source Code​

Next Steps​