SingleChain

Move Type: Chain Complexity: O(objects² × containers)

Evaluate 2-object chain moves where hot container gives one object and receives another. More expensive than SingleEndChain but explores different neighborhood.

Overview

SingleChain evaluates 2-object chain moves where the hot container is in the middle of the chain:

1. Hot object moves from hot container → other container 2
2. Other object moves from other container 1 → hot container (fills the gap)

This differs from SingleEndChain where the hot container is at the end and doesn't receive an object back.

Use when:

• Hot container has capacity constraints (must receive object back)
• Need balanced exchanges (one out, one in)
• SingleEndChain not finding good moves
• Capacity-neutral chain moves required

Avoid when:

• Hot container should empty (use SingleEndChain)
• Problem is large (>10K objects, too expensive)
• Simple moves work (try Single first)
• SingleEndChain works (it's faster)

Quick Example

Python

# 2-object chains: hot container gives one, receives another
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleChainMoveTypeSpec(),  # Balanced chain moves
            ]
        )
    )
)

C++

void quickExample() {
  // 2-object chains: hot container gives one, receives another
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");
  solver.setObjectName("task");
  solver.setContainerName("host");

  LocalSearchSolverSpec solverSpec;
  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().singleChainMoveTypeSpec() =
      SingleChainMoveTypeSpec{};

  solver.addSolver(solverSpec);
}

Parameters

Parameter	Type	Required	Default	Description
partitionNameToExploreChainsWithinObjectGroup	string	No	null	Restrict replacement objects to same partition
specialColdContainer	string	No	null	Fixed destination for hot object

Parameter Details

partitionNameToExploreChainsWithinObjectGroup:

• Restricts which objects can replace the hot object
• Only objects in same partition group will be considered
• Useful for type-based constraints (e.g., only replace task with same type task)

specialColdContainer:

• Forces hot object to move to specific container
• Useful when you know the destination (e.g., new server)
• Reduces search space significantly

How It Works

Given a hot container (most broken):

1. Select hot object: Pick object from hot container
2. Select destination: Pick other container 2 for hot object
3. Select source: Pick other container 1 (source of replacement)
4. Select replacement: Pick object from other container 1
5. Evaluate chain: Test 2-move chain:
   • Move hot object: hot container → other container 2
   • Move replacement: other container 1 → hot container
6. Repeat: Try all combinations
7. Apply best: Apply the 2-move chain improving objective most

Visual Example

Before chain:                          After chain:
┌──────────────┐                      ┌──────────────┐
│ Hot          │                      │ Hot          │
│ Container    │  ─────(1)────>       │ Container    │
│  • hotObj ──┐│                      │  • replObj ←─┼─┐
│  • obj2     ││                      │  • obj2      │ │
└─────────────┼┘                      └──────────────┘ │
              │                                        │
┌─────────────┼┐                      ┌────────────────┼┐
│ Other       ││                      │ Other          ││
│ Container 1 ││  <────(2)────        │ Container 1    ││
│  • replObj ─┼┘                      │  (gave replObj)│ │
│  • objX     │                       │  • objX        │ │
└─────────────┘                       └────────────────┘ │
┌─────────────┐                       ┌────────────────┐ │
│ Other       │                       │ Other          │ │
│ Container 2 │                       │ Container 2    │ │
│  • objY     │                       │  • hotObj ←────┼─┘
│  • objZ     │                       │  • objY        │
└─────────────┘                       │  • objZ        │
                                      └────────────────┘

Chain: hotObj (Hot→Other2), replObj (Other1→Hot)
Hot container: gives hotObj, receives replObj (balanced)

Comparison with SingleEndChain

Aspect	SingleChain	SingleEndChain
Hot container role	Middle (gives + receives)	End (gives only)
Hot container change	Object swapped	Object removed
Complexity	O(N² × C)	O(N × C²)
Use case	Capacity-constrained hot	Empty hot container
Default choice	No	Yes

Recommendation: Try SingleEndChain first - it's more commonly useful.

Complexity

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

Where:

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

Example - Medium problem:

• Hot container: 1,000 objects
• System: 100 containers
• Moves evaluated ≈ 1,000² × 100 = 100 million moves per iteration

Warning: Very expensive for large problems. Use SingleEndChain or restrict parameters.

Usage Patterns

Basic Chain Moves

Default usage for capacity-constrained scenarios:

Python

# Hot container must remain balanced (one out, one in)
solver = ProblemSolver(service_name="example", service_scope="test")

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleChainMoveTypeSpec(),
            ]
        )
    )
)

C++

void basic() {
  // Hot container must remain balanced (one out, one in)
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  LocalSearchSolverSpec solverSpec;
  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().singleChainMoveTypeSpec() =
      SingleChainMoveTypeSpec{};

  solver.addSolver(solverSpec);
}

Restricted by Object Type

Only replace with same type objects:

Python

# Only replace hot object with same type
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleChainMoveTypeSpec(
                    partitionNameToExploreChainsWithinObjectGroup="task_type",
                ),
            ]
        )
    )
)

C++

void restricted() {
  // Only replace hot object with same type
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  // Define object type partition
  std::unordered_map<std::string, std::vector<std::string>> taskTypes = {
      {"batch", {"task1", "task2"}},
      {"realtime", {"task3", "task4"}},
      {"ml", {"task5", "task6"}},
  };
  solver.addPartition("task_type", taskTypes);

  LocalSearchSolverSpec solverSpec;

  SingleChainMoveTypeSpec chainSpec;
  chainSpec.partitionNameToExploreChainsWithinObjectGroup() = "task_type";

  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().singleChainMoveTypeSpec() = chainSpec;

  solver.addSolver(solverSpec);
}

Fixed Destination

When you know where hot object should go:

Python

# Move hot objects to specific destination, find replacements
solver = ProblemSolver(service_name="example", service_scope="test")

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleChainMoveTypeSpec(
                    specialColdContainer="new_server",  # Fixed destination
                ),
            ]
        )
    )
)

C++

void fixedDest() {
  // Move hot objects to specific destination, find replacements
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  LocalSearchSolverSpec solverSpec;

  SingleChainMoveTypeSpec chainSpec;
  chainSpec.specialColdContainer() = "new_server"; // Fixed destination

  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().singleChainMoveTypeSpec() = chainSpec;

  solver.addSolver(solverSpec);
}

Combined Strategy

Use with other move types:

Python

# Multi-stage: simple moves first, then chains
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleMoveTypeSpec(),  # Try simple moves first
                SingleEndChainMoveTypeSpec(),  # Then end chains (more common)
                SingleChainMoveTypeSpec(),  # Finally middle chains if needed
            ]
        )
    )
)

C++

void combined() {
  // Multi-stage: simple moves first, then chains
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");
  solver.setObjectName("task");
  solver.setContainerName("host");

  LocalSearchSolverSpec solverSpec;

  // Add Single
  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().singleMoveTypeSpec() = SingleMoveTypeSpec{};

  // Add SingleEndChain
  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().singleEndChainMoveTypeSpec() =
      SingleEndChainMoveTypeSpec{};

  // Add SingleChain
  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().singleChainMoveTypeSpec() =
      SingleChainMoveTypeSpec{};

  solver.addSolver(solverSpec);
}

Performance Characteristics

Scalability

Objects	Containers	Chain Moves Evaluated	Time	Practical?
100	50	500K	<1s	✓ Yes
1K	100	100M	10-60s	△ Marginal
10K	100	10B	Hours	✗ No
>10K	>100	Too many	N/A	✗ Absolutely not

Hard limit: Do not use SingleChain with >1K objects per container.

When Does It Help?

SingleChain helps when:

• Hot container capacity-constrained: Must receive object back
• Balanced exchanges needed: One out, one in
• Type constraints: Replacement must match hot object type
• SingleEndChain not applicable (hot can't empty)

SingleChain does NOT help when:

• Hot should empty: Use SingleEndChain instead
• Problem too large: O(N²) too expensive
• Simple moves work: Use Single first
• No capacity constraints: Single is faster

Comparison with Alternatives

Move Type	Hot Container Role	Complexity	Capacity	Use Case
Single	Gives only	O(N × C)	Hot empties	General moves
SingleEndChain	End (gives)	O(N × C²)	Hot empties	2-object chains
SingleChain	Middle (gives+receives)	O(N² × C)	Balanced	Capacity-constrained
SingleChainFast	Middle (early exit)	O(N² × C)	Balanced	Faster SingleChain
Swap	Paired exchange	O(N²)	Balanced	Direct swaps

Decision tree:

1. Hot should empty? → SingleEndChain
2. Hot must stay balanced? → SingleChain
3. Need speed? → SingleChainFast
4. Direct swaps? → Swap

Troubleshooting

Problem: SingleChain too slow

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

Solutions:

• Use SingleChainFast instead (early exit)
• Set specialColdContainer to reduce search space
• Use partitionNameToExploreChainsWithinObjectGroup to filter
• Consider if SingleEndChain works instead
• Problem may be too large for chain moves

Problem: Not finding good chain moves

Diagnosis: Wrong move type OR constraints too restrictive

Solutions:

• Try SingleEndChain (different neighborhood)
• Remove partitionNameToExploreChainsWithinObjectGroup restriction
• Check if simple Single moves work
• May already be at local optimum
• Verify capacity constraints aren't blocking all moves

Problem: Hot container not staying balanced

Diagnosis: This is expected - SingleChain should balance

Solutions:

• This move type is designed for balance (one in, one out)
• If seeing imbalance, check implementation
• Verify objective function rewards balance
• May need capacity constraints

Problem: Getting worse results than expected

Diagnosis: Wrong move type for problem

Solutions:

• Try SingleEndChain first (usually better)
• Check if Single + Swap sufficient
• May need different objective function
• Verify hot container selection is correct

When to Use SingleChain

DO use when:

• Hot container capacity-constrained (must receive back)
• Need balanced exchanges (one out, one in)
• Type-based replacement constraints
• SingleEndChain doesn't apply
• Problem is small-medium (<1K objects)

DO NOT use when:

• Hot container should empty → Use SingleEndChain
• Problem is large (>1K objects) → Too expensive
• Simple moves work → Use Single
• SingleEndChain works → It's the better default

Related Move Types

Chain variants:

• SingleEndChain - Default choice for chains
• SingleChain - Capacity-constrained variant (this)
• SingleChainFast - Faster with early exit

Simpler alternatives:

• Single - Try first
• Swap - Direct object swaps

When to use each:

1. First: Single
2. If stuck: SingleEndChain (not SingleChain!)
3. If hot must balance: SingleChain
4. Need speed: SingleChainFast

Source Code

• Thrift definition: interface/thrift/SolverSpecs.thrift:568
• Implementation: solver/moves/SingleChainMoveType.h
• Tests: solver/moves/tests/

Next Steps

• Try SingleEndChain first - better default choice for chains
• Learn about SingleChainFast for faster chain moves
• Review Move Types Overview for choosing move types
• See Capacity for capacity constraints