SwapN

Move Type: Advanced Complexity: O(N! × I) where N = concurrent objects, I = iterations Primary Use: Satisfy exact-limit constraints by swapping N objects simultaneously

Swap N objects simultaneously to satisfy complex exact-limit constraints that simpler move types cannot handle.

Overview

SwapN (also known as SWAP_N) is a highly specialized move type designed for problems with exact-limit constraints where you need to move N objects together to maintain balance. It was originally created for the Capacity Request Portal (CRP) problem.

Instead of moving objects one at a time, SwapN:

Selects N objects from a source set
Tries placing them in N different destination containers
Swaps them with N objects already in those containers
Evaluates if this simultaneous N-way swap improves the objective

This allows satisfying constraints like "exactly 3 requests per pod" that are impossible with single-object moves.

Use when:

Have exact-limit constraints (MIN + MAX with same value)
Simple moves get stuck due to constraints
Need to move N objects simultaneously
Know which objects and destinations to consider
Very specific capacity allocation problems

Avoid when:

No exact-limit constraints
Simple moves work fine
Don't have specific source objects
Generic optimization (very expensive)
N is large (>5)

Quick Example

Python
C++

# Swap 3 objects simultaneously to satisfy exact-limit constraints
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SwapNMoveTypeSpec(
                    swapNConcurrentObjects=3,
                    swapNSourceObjects=[
                        "req0",
                        "req1",
                        "req2",
                        "req3",
                        "req4",
                        "req5",
                    ],
                    swapNDestinationScope=[
                        ["rack0", "rack1", "rack2"],  # Pod 0 racks
                        ["rack3", "rack4", "rack5"],  # Pod 1 racks
                    ],
                    swapNIterations=1000,
                ),
            ]
        )
    )
)

void quickExample() {
  // Swap 3 objects simultaneously to satisfy exact-limit constraints
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  LocalSearchSolverSpec solverSpec;

  SwapNMoveTypeSpec swapNSpec;
  swapNSpec.swapNConcurrentObjects() = 3;
  swapNSpec.swapNSourceObjects() = {
      "req0", "req1", "req2", "req3", "req4", "req5"};
  swapNSpec.swapNDestinationScope() = {
      {"rack0", "rack1", "rack2"}, // Pod 0 racks
      {"rack3", "rack4", "rack5"}, // Pod 1 racks
  };
  swapNSpec.swapNIterations() = 1000;

  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().swapNMoveTypeSpec() = swapNSpec;

  solver.addSolver(solverSpec);
}

Parameters

Parameter	Type	Required	Default	Description
`swapNConcurrentObjects`	int	No	1	Number of objects to swap simultaneously
`swapNSourceObjects`	list<string>	Yes	null	Source objects to consider
`swapNDestinationScope`	list<list<string>>	Yes	null	Grouped destination containers
`swapNIterations`	int	No	1000000	Max random iterations to try

Parameter Details

swapNConcurrentObjects:

Number of objects to swap simultaneously (N)
Example: 3 means swap 3 objects at once
Higher N = exponentially more expensive
Typically 2-5

swapNSourceObjects:

List of object names to consider as sources
Only these objects will be moved
Example: ["request0", "request1", "request2", "request3"]
Typically unassigned or pending objects

swapNDestinationScope:

Nested list of container groups
Outer list: groups (e.g., pods)
Inner lists: containers in each group (e.g., racks per pod)
Example: [["rack0", "rack1"], ["rack2", "rack3"]]
Each group represents mutually exclusive destinations

swapNIterations:

Maximum random sampling iterations
Algorithm tries random combinations up to this limit
Higher = better quality but slower
Default 1M is usually sufficient

How It Works

For each iteration (up to swapNIterations):

Random selection: Pick N random objects from swapNSourceObjects
Random destinations: Pick N random destination containers from swapNDestinationScope (one from each group if possible)
Generate swap: Create N-way swap moving selected objects to destinations
Evaluate: Test if this swap improves objective
Track best: Keep the best swap found so far
Repeat: Try different random combinations

Visual Example

Problem: Allocate 6 requests to 2 pods, exactly 3 requests per pod

Source: unallocated = [req0, req1, req2, req3, req4, req5]

Destinations:
  Pod0: [rack0, rack1, rack2, ...]  (10 racks)
  Pod1: [rack10, rack11, rack12, ...]  (10 racks)

swapNConcurrentObjects = 3

Iteration 1:
  Select: [req0, req2, req4]
  Destinations: [rack1 (pod0), rack3 (pod0), rack11 (pod1)]  ✗ Invalid (2 in pod0, 1 in pod1)

Iteration 2:
  Select: [req1, req3, req5]
  Destinations: [rack0 (pod0), rack2 (pod0), rack4 (pod0)]  ✗ Invalid (all in pod0)

Iteration 3:
  Select: [req0, req1, req2]
  Destinations: [rack1 (pod0), rack11 (pod1), rack12 (pod1)]  ✗ Invalid (1 in pod0, 2 in pod1)

Iteration 100:
  Select: [req0, req2, req4]
  Destinations: [rack0 (pod0), rack2 (pod0), rack4 (pod0)]  ✓ Valid! (3 in pod0)

Then continue to place remaining 3 in pod1...

Complexity

Per iteration: O(N!)

Where:

N = swapNConcurrentObjects

Total: O(N! × I)

Where:

I = iterations attempted (up to swapNIterations)

Examples:

N=2, I=1000: ~2,000 combinations
N=3, I=1000: ~6,000 combinations
N=4, I=1000: ~24,000 combinations
N=5, I=10000: ~1,200,000 combinations

⚠️ Factorial growth: N=6 is 720x more expensive than N=2!

Usage Patterns

Exact-Limit Allocation

Allocate requests with exact pod limits:

Python
C++

# Exactly 3 requests per pod using SwapN
solver.addConstraint(
    ConstraintSpecs(
        groupCountSpec=GroupCountSpec(
            scope="pod",
            dimension="request_count",
            partitionName="request_group",
            bound=GroupCountSpecBound.EXACT,
            limit=GroupLimitSpec(defaultLimit=3),
        )
    )
)

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SwapNMoveTypeSpec(
                    swapNConcurrentObjects=3,
                    swapNSourceObjects=[
                        "request0",
                        "request1",
                        "request2",
                        "request3",
                        "request4",
                        "request5",
                    ],
                    swapNDestinationScope=[
                        ["rack0", "rack1", "rack2"],  # Pod 0
                        ["rack3", "rack4", "rack5"],  # Pod 1
                    ],
                ),
            ]
        )
    )
)

void exactLimit() {
  // Exactly 3 requests per pod using SwapN
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");
  solver.setObjectName("request");
  solver.setContainerName("rack");

  // Define pod scope
  std::map<std::string, std::string> podScope = {
      {"rack0", "pod0"},
      {"rack1", "pod0"},
      {"rack2", "pod0"},
      {"rack3", "pod1"},
      {"rack4", "pod1"},
      {"rack5", "pod1"},
  };
  solver.addScope("pod", podScope);

  LocalSearchSolverSpec solverSpec;

  SwapNMoveTypeSpec swapNSpec;
  swapNSpec.swapNConcurrentObjects() = 3;
  swapNSpec.swapNSourceObjects() = {
      "request0",
      "request1",
      "request2",
      "request3",
      "request4",
      "request5",
  };
  swapNSpec.swapNDestinationScope() = {
      {"rack0", "rack1", "rack2"}, // Pod 0
      {"rack3", "rack4", "rack5"}, // Pod 1
  };

  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().swapNMoveTypeSpec() = swapNSpec;

  solver.addSolver(solverSpec);
}

Capacity Request Portal

Original use case - allocate N hosts per request:

Python
C++

# Capacity Request Portal: allocate hosts with exact pod constraints
solver = ProblemSolver(service_name="example", service_scope="test")
solver.setObjectName("host")
solver.setContainerName("rack")

# Define pod scope
solver.addScope(
    "pod",
    {
        "rack0": "pod0",
        "rack1": "pod0",
        "rack2": "pod1",
        "rack3": "pod1",
    },
)

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SwapNMoveTypeSpec(
                    swapNConcurrentObjects=3,  # 3 hosts per allocation
                    swapNSourceObjects=[
                        "host0",
                        "host1",
                        "host2",
                        "host3",
                        "host4",
                        "host5",
                    ],
                    swapNDestinationScope=[
                        ["rack0", "rack1"],  # Pod 0 racks
                        ["rack2", "rack3"],  # Pod 1 racks
                    ],
                    swapNIterations=1000000,  # 1M iterations
                ),
            ]
        )
    )
)

void crp() {
  // Capacity Request Portal: allocate hosts with exact pod constraints
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");
  solver.setObjectName("host");
  solver.setContainerName("rack");

  // Define pod scope
  std::map<std::string, std::string> podScope = {
      {"rack0", "pod0"},
      {"rack1", "pod0"},
      {"rack2", "pod1"},
      {"rack3", "pod1"},
  };
  solver.addScope("pod", podScope);

  LocalSearchSolverSpec solverSpec;

  SwapNMoveTypeSpec swapNSpec;
  swapNSpec.swapNConcurrentObjects() = 3; // 3 hosts per allocation
  swapNSpec.swapNSourceObjects() = {
      "host0", "host1", "host2", "host3", "host4", "host5"};
  swapNSpec.swapNDestinationScope() = {
      {"rack0", "rack1"}, // Pod 0 racks
      {"rack2", "rack3"}, // Pod 1 racks
  };
  swapNSpec.swapNIterations() = 1000000; // 1M iterations

  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().swapNMoveTypeSpec() = swapNSpec;

  solver.addSolver(solverSpec);
}

Limited Iterations

Control sampling for performance:

Python
C++

# Use fewer iterations for faster (but lower quality) results
solver = ProblemSolver(service_name="example", service_scope="test")

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SwapNMoveTypeSpec(
                    swapNConcurrentObjects=2,
                    swapNSourceObjects=["obj0", "obj1", "obj2", "obj3"],
                    swapNDestinationScope=[
                        ["container0", "container1"],
                        ["container2", "container3"],
                    ],
                    swapNIterations=100,  # Reduced from default 1M
                ),
            ]
        )
    )
)

void limitedIterations() {
  // Use fewer iterations for faster (but lower quality) results
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  LocalSearchSolverSpec solverSpec;

  SwapNMoveTypeSpec swapNSpec;
  swapNSpec.swapNConcurrentObjects() = 2;
  swapNSpec.swapNSourceObjects() = {"obj0", "obj1", "obj2", "obj3"};
  swapNSpec.swapNDestinationScope() = {
      {"container0", "container1"},
      {"container2", "container3"},
  };
  swapNSpec.swapNIterations() = 100; // Reduced from default 1M

  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().swapNMoveTypeSpec() = swapNSpec;

  solver.addSolver(solverSpec);
}

Performance Characteristics

When Does It Help?

SwapN helps when:

Exact-limit constraints: Have MIN + MAX with same value
Stuck simple moves: Single/Swap move types can't make progress
Known sources: Have specific objects to allocate
Small N: Need to move 2-5 objects simultaneously
Specific problem structure: Like CRP problem

SwapN does NOT help when:

No exact limits: Using ranges (MIN ≠ MAX)
Simple moves work: Other move types making progress
Large N: N > 5 (factorial explosion)
No source specification: Don't know which objects
General optimization: Too specialized and expensive

Complexity Explosion

N	Factorial	Iterations	Total Ops	Practical?
2	2	1,000	2K	✓ Fast
3	6	1,000	6K	✓ Good
4	24	1,000	24K	✓ OK
5	120	10,000	1.2M	⚠ Slow
6	720	10,000	7.2M	✗ Very slow
10	3,628,800	-	-	✗ Impractical

Comparison with Alternatives

Move Type	Simultaneous	Constraint Type	Use Case
Single	1 object	General	Standard moves
Swap	2 objects	Pairwise	Object swaps
SwapN	N objects	Exact-limit	CRP-like problems

Troubleshooting

Problem: No improving moves found

Diagnosis: Random sampling not finding valid combinations

Solutions:

Increase swapNIterations (try 10M)
Check if problem is actually solvable
Verify source objects and destinations are correct
May need different N value

Problem: Too slow

Diagnosis: N too large or too many iterations

Solutions:

Reduce swapNConcurrentObjects if possible
Reduce swapNIterations (try 1K or 10K)
Check if simpler move types can work
Consider if problem structure allows smaller N

Problem: Constraint violations

Diagnosis: Swaps violate constraints

Solutions:

Verify exact-limit constraints are set correctly
Check destination scope grouping is correct
Review capacity constraints
Ensure source objects are valid

Problem: Wrong destinations

Diagnosis: swapNDestinationScope structure incorrect

Solutions:

Verify outer list groups destinations correctly
Check inner lists contain right containers
Example: [["pod0_racks"], ["pod1_racks"]]
Each inner list should represent mutually exclusive group

When to Use SwapN

DO use when:

Have exact-limit constraints (MIN = MAX)
Simple moves stuck
Know source objects
N is small (2-5)
Have CRP-like problem structure

DO NOT use when:

Using constraint ranges (MIN ≠ MAX)
Simple moves working
N is large (>5)
Generic optimization needed
Don't have specific sources/destinations

Alternatives:

Single - For general moves
Swap - For 2-object swaps
KLSearch - For escaping local optima differently

When to try alternatives first:

Always try Single and Swap first
Only use SwapN when stuck on exact-limit constraints

Source Code

Thrift definition: interface/thrift/SolverSpecs.thrift:522
Implementation: solver/moves/SwapNMoveType.h
Tests: interface/tests/SwapNMoveTypeTest.cpp

Next Steps

Try KLSearch for different local optima escape
Review Move Types Overview for choosing move types
Learn about exact-limit constraints in capacity specs

Notes

⚠️ Highly Specialized: SwapN is designed for very specific problems with exact-limit constraints. It's expensive and should only be used when simpler move types fail.

⚠️ Factorial Complexity: Keep N ≤ 5. N=6 is 720x slower than N=2. N=10 is completely impractical.

💡 Original Use Case: Created for Capacity Request Portal (CRP) problem requiring "exactly N hosts per pod" allocation.

Overview​

Quick Example​

Parameters​

Parameter Details​

How It Works​

Visual Example​

Complexity​

Usage Patterns​

Exact-Limit Allocation​

Capacity Request Portal​

Limited Iterations​

Performance Characteristics​

When Does It Help?​

Complexity Explosion​

Comparison with Alternatives​

Troubleshooting​

Problem: No improving moves found​

Problem: Too slow​

Problem: Constraint violations​

Problem: Wrong destinations​

When to Use SwapN​

Related Move Types​

Source Code​

Next Steps​

Notes​

Overview

Quick Example

Parameters

Parameter Details

How It Works

Visual Example

Complexity

Usage Patterns

Exact-Limit Allocation

Capacity Request Portal

Limited Iterations

Performance Characteristics

When Does It Help?

Complexity Explosion

Comparison with Alternatives

Troubleshooting

Problem: No improving moves found

Problem: Too slow

Problem: Constraint violations

Problem: Wrong destinations

When to Use SwapN

Related Move Types

Source Code

Next Steps

Notes