Skip to main content

Swap

Move Type: Swap Complexity: O(objects²)

Exchange two objects between containers. Essential for capacity-constrained problems where you can't simply add objects without removing others.

Overview​

Swap evaluates exchanging pairs of objects between the hot container and other containers. This is critical when containers are near capacity and single moves would violate constraints.

Use when:

  • Capacity constraints are tight
  • Moving an object requires making room first
  • Single moves alone aren't finding improvements

Avoid when:

  • Problem is unconstrained (Single is faster and sufficient)
  • Problem is very large (>10K objects - use SwapSampled instead)

Quick Example​

# Use Swap for capacity-constrained problems
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleMoveTypeSpec(),  # Try single moves first
                SwapMoveTypeSpec(),  # Then swaps for capacity constraints
            ]
        )
    )
)

Parameters​

ParameterTypeRequiredDefaultDescription
partitionNameToExploreSwapsWithinObjectGroupstringNonullOnly swap objects within same group
greedyOnSrcboolNofalseExit early when swapping source objects
greedyOnDstboolNofalseExit early when swapping destination objects
destinationsToExploreDestinationsToExploreOptionsNonullRestrict destination containers
sampleSizeSampleSizeNonullSample subset of objects on both sides
swapRatioDimensionStringKeyValueMapNonullDimension for uneven k:1 swaps
objectBundleFormationHintsObjectBundleFormationHintsNonullBundle objects for certain containers

How It Works​

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

  1. Select hot object: Pick one object from the hot container
  2. Select destination container: Pick a different container
  3. Select other object: Pick one object from the destination container
  4. Evaluate: Test swapping the two objects (hot object ↔ other object)
  5. Repeat: Try all combinations of (hot object, destination container, other object)
  6. Apply best: Apply the swap that improves the objective most

Visual Example​

Before:                          After (if swap applied):
┌─────────────┐                 ┌─────────────┐
│ Hot         │                 │ Hot         │
│ Container   │    ┌─swap─┐    │ Container   │
│  • obj1     │ ───┤      │──> │  • objX ←─┐ │
│  • obj2     │    │      │    │  • obj2   │ │
│  • obj3     │ ←──┤      │─── │  • obj3   │ │
└─────────────┘    └──────┘    └───────────┼─┘
┌─────────────┐                 ┌───────────┼─┐
│ Other       │                 │ Other     ↓ │
│ Container   │                 │ Container   │
│  • objX     │                 │  • obj1  ←  │
│  • objY     │                 │  • objY     │
└─────────────┘                 └─────────────┘

Complexity​

Moves evaluated per iteration: O(N × M × C)

  • Simplifies to O(N²) when containers have similar sizes

Where:

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

Example:

  • Hot container has 100 objects
  • Each destination container has ~100 objects
  • System has 50 containers
  • Moves evaluated = 100 × 100 × 50 = 500,000 moves

Warning: Swap is much more expensive than Single. Use judiciously.

Usage Patterns​

Basic Capacity-Constrained Problem​

Most common usage - combine Single with Swap:

# Capacity is tight - need swaps to make progress
solver.addConstraint(
    ConstraintSpecs(
        capacitySpec=CapacitySpec(
            name="memory-capacity",
            scope="host",
            dimension="memory",
            limit=Limit(globalLimit=64.0),
        )
    )
)

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleMoveTypeSpec(),  # Single moves when there's room
                SwapMoveTypeSpec(),  # Swaps when capacity is tight
            ]
        )
    )
)

Greedy Swap (Faster)​

Use greedy flags for faster convergence:

# Exit early when improvement found (faster)
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SwapMoveTypeSpec(
                    greedyOnSrc=True,  # Try src objects one by one, exit on improvement
                    greedyOnDst=True,  # Try dst objects one by one, exit on improvement
                ),
            ]
        )
    )
)

Sampled Swap (Large Problems)​

For large problems, sample objects to reduce cost:

# For large problems, sample subset of objects
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SwapMoveTypeSpec(
                    sampleSize=SampleSize(
                        defaultSampleSize=100,  # Sample 100 objects on each side
                    ),
                ),
            ]
        )
    )
)

Swap Within Groups​

Only swap objects within the same partition group:

# Only swap objects from the same group (e.g., same database shard)
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SwapMoveTypeSpec(
                    partitionNameToExploreSwapsWithinObjectGroup="shard",
                ),
            ]
        )
    )
)

Restricted Destinations​

Limit which containers to explore:

# Only swap within the same rack (limit destinations)
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SwapMoveTypeSpec(
                    destinationsToExplore=MoveToCurrentScopeItemSpec(
                        scopeNameForExploringMovesToCurrentScopeItem="rack",
                    ),
                ),
            ]
        )
    )
)

Performance Optimization​

When Swap is Slow​

Greedy flags: Exit early when improvement found

SwapMoveTypeSpec(
    greedyOnSrc=True,  # Try src objects one by one, exit on improvement
    greedyOnDst=True,  # Try dst objects one by one, exit on improvement
)

Sampling: Evaluate subset of swaps

SwapMoveTypeSpec(
    sampleSize=SampleSize(
        defaultSampleSize=100,  # Only sample 100 objects per side
    ),
)

Destination filtering: Limit containers to explore

SwapMoveTypeSpec(
    destinationsToExplore=MoveToCurrentScopeItemSpec(
        scopeNameForExploringMovesToCurrentScopeItem="rack",
    ),
)
ObjectsContainersConfiguration
<1K<100Default Swap (no sampling)
1K-10K100-1KGreedy flags + sampling (100-500)
>10K>1KSwapSampled with aggressive sampling

Comparison with Variants​

Move TypeSpeedCompletenessUse Case
SwapSlowCompleteDefault swap, thorough
SwapSampledMediumSampledLarge problems
SwapFullContainersMediumFull containers onlyContainer-level swaps
SwapFullWithEmptyFastEmpty targets onlyConsolidation

Troubleshooting​

Problem: Swap is too slow​

Diagnosis: O(N²) complexity too expensive for problem size

Solutions:

  • Enable greedyOnSrc=True and greedyOnDst=True
  • Add sampling: sampleSize=SampleSize(defaultSampleSize=100)
  • Switch to SwapSampled for large problems
  • Restrict destinations with destinationsToExplore
  • Use SwapFullWithEmpty if applicable

Problem: Swap not improving objective​

Diagnosis: May need more complex moves

Solutions:

  • Ensure Single moves tried first (Swap should be after Single)
  • Add SingleEndChain for 2-move sequences
  • Check if swaps are actually beneficial for your problem
  • Verify capacity constraints are preventing Single moves

Problem: Swap causing constraint violations​

Diagnosis: Swapped objects have different dimensions

Solutions:

  • Check that swapped objects satisfy constraints
  • Use partitionNameToExploreSwapsWithinObjectGroup to swap similar objects
  • Review capacity and group count constraints
  • May need different move type (e.g., SingleEndChain)

Variants:

Alternatives:

  • SingleEndChain - 2-move sequence (often better than Swap)
  • Single - Simpler, use when capacity not tight

Complementary:

  • Single - Always use Single before Swap

Source Code​

Next Steps​