SingleChainFast

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

Like SingleChain but stops as soon as ANY improving chain is found. Much faster convergence but may miss better moves.

Overview

SingleChainFast evaluates 2-object chain moves with early exit: stops as soon as it finds a chain that improves the objective. Like SingleChain, the hot container is in the middle (gives one, receives another), but the search terminates early.

Use when:

• Need faster chain moves than SingleChain
• Speed more important than solution quality
• Hot container capacity-constrained (must receive back)
• SingleChain too slow

Avoid when:

• Solution quality critical (use SingleChain)
• Hot should empty (use SingleEndChain)
• Problem is small (overhead not worth it)
• Need deterministic results

Quick Example

Python

# Fast chain moves with early exit
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleChainFastMoveTypeSpec(),  # Stop at first improving chain
            ]
        )
    )
)

C++

void quickExample() {
  // Fast chain moves with early exit
  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().singleChainFastMoveTypeSpec() =
      SingleChainFastMoveTypeSpec{};

  solver.addSolver(solverSpec);
}

Parameters

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

Parameter Details

partitionNameToExploreFastChainsWithinObjectGroup:

• Restricts which objects can replace the hot object
• Only objects in same partition group will be considered
• Useful for type-based constraints

specialFastColdContainer:

• Forces hot object to move to specific container
• Reduces search space significantly
• Useful when destination is known

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 in parallel (multi-threaded)
6. Early exit: If chain improves objective → STOP and apply it
7. Continue: If not, try next combination
8. Worst case: If no improving chain found, try all combinations

Visual Example

Hot Container (1000 objects):
  obj1 → Try chain with replObj1 from Container A: improvement! ✓ STOP HERE

SingleChainFast returns after evaluating just 1 chain!

Comparison with SingleChain:
- SingleChainFast:  Tries ~1-100 chains, finds improvement, stops
- SingleChain:      Tries 1,000,000 chains (1000² × 1 containers), picks best

Comparison with SingleChain

Aspect	SingleChain	SingleChainFast
Evaluation	All combinations	Stop at first improvement
Typical chains evaluated	Millions	1-100
Quality	Best chain	First improving chain
Speed	Slow	Much faster
Parallelism	No	Yes (multi-threaded)

Complexity

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

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

Worst case: O(N² × C) - No improving chains found (same as SingleChain)

Where:

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

Example - Medium problem:

• Hot container: 1,000 objects
• System: 100 containers
• Typical run: Finds improvement in 10-100 chains (vs 100M for SingleChain)
• Speedup: 1,000-10,000x

Usage Patterns

Fast Chain Moves

Default usage for speed:

Python

# Fastest chain moves (early exit + parallelism)
solver = ProblemSolver(service_name="example", service_scope="test")

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

C++

void fastChains() {
  // Fastest chain moves (early exit + parallelism)
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  LocalSearchSolverSpec solverSpec;
  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().singleChainFastMoveTypeSpec() =
      SingleChainFastMoveTypeSpec{};

  solver.addSolver(solverSpec);
}

Type-Restricted Fast Chains

Only replace with same type, with early exit:

Python

# Fast chains restricted to same type
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleChainFastMoveTypeSpec(
                    partitionNameToExploreChainsWithinObjectGroup="task_type",
                ),
            ]
        )
    )
)

C++

void restricted() {
  // Fast chains restricted to 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", std::move(taskTypes));

  LocalSearchSolverSpec solverSpec;

  SingleChainFastMoveTypeSpec chainSpec;
  chainSpec.partitionNameToExploreFastChainsWithinObjectGroup() = "task_type";

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

  solver.addSolver(solverSpec);
}

Fixed Destination Fast

When you know destination and want speed:

Python

# Fast chains to specific destination
solver = ProblemSolver(service_name="example", service_scope="test")

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

C++

void fixedDest() {
  // Fast chains to specific destination
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  LocalSearchSolverSpec solverSpec;

  SingleChainFastMoveTypeSpec chainSpec;
  chainSpec.specialFastColdContainer() = "new_server"; // Fixed destination

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

  solver.addSolver(solverSpec);
}

Multi-Stage Strategy

Fast chains first, then thorough if needed:

Python

# Multi-stage: fast first, quality later
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleFastMoveTypeSpec(),  # Simple moves first
                SingleChainFastMoveTypeSpec(),  # Fast chains for quick wins
                SingleChainMoveTypeSpec(),  # Thorough chains if needed
            ]
        )
    )
)

C++

void multistage() {
  // Multi-stage: fast first, quality later
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");
  solver.setObjectName("task");
  solver.setContainerName("server");

  LocalSearchSolverSpec solverSpec;

  // Add SingleFast
  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().singleFastMoveTypeSpec() =
      SingleFastMoveTypeSpec{};

  // Add SingleChainFast
  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().singleChainFastMoveTypeSpec() =
      SingleChainFastMoveTypeSpec{};

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

  solver.addSolver(solverSpec);
}

Performance Characteristics

Speed vs Quality

Metric	SingleChainFast	SingleChain
Speed	Very Fast	Slow
Chains evaluated	1-100	100K-100M
Solution quality	60-80% optimal	95-100% optimal
Iteration time	<1s	10-60s
Parallelism	Yes (multi-threaded)	No

When Does It Help?

SingleChainFast helps when:

• Speed critical: Need fast convergence
• Hot capacity-constrained: Must receive object back
• Frequent small improvements: Easy to find some improvement quickly
• Multi-core available: Can leverage parallelism

SingleChainFast does NOT help when:

• Quality critical: Need best chain move
• Rare improvements: Takes long to find ANY improving chain
• Hot should empty: Use SingleEndChain instead
• Simple moves work: Use Single or SingleFast

Comparison with Alternatives

Move Type	Early Exit	Hot Role	Parallelism	Use Case
Single	No	Gives only	No	General moves
SingleFast	Yes (per object)	Gives only	No	Faster single moves
SingleEndChain	No	End (gives)	No	2-object chains (default)
SingleChain	No	Middle (gives+receives)	No	Best chain quality
SingleChainFast	Yes (per chain)	Middle (gives+receives)	Yes	Fast chains

Decision tree:

1. Hot should empty? → SingleEndChain
2. Hot must balance + need speed? → SingleChainFast
3. Hot must balance + need quality? → SingleChain
4. Simple moves sufficient? → SingleFast

Troubleshooting

Problem: Making many small chain moves but not improving much

Diagnosis: Early exit finding local improvements, missing better global chains

Solutions:

• Switch to SingleChain for better chain quality
• Use SingleChainFast for quick wins, then SingleChain for refinement
• Combine with other move types
• Increase iteration limit to let fast chains make more sequential improvements

Problem: Not finding any improving chains

Diagnosis: Already at local optimum OR improvements are rare

Solutions:

• This is expected at local optimum
• Try SingleEndChain (different neighborhood)
• Check if simple moves (Single) work
• May need different move types (Swap)

Problem: Solution quality worse than expected

Diagnosis: Early exit too aggressive, missing much better chains

Solutions:

• Use SingleChain for better quality
• Run SingleChainFast multiple times
• Use as warm-start, then refine with SingleChain
• May need different approach

Problem: Still too slow

Diagnosis: Even with early exit, problem too large

Solutions:

• Set specialFastColdContainer to reduce search space
• Use partitionNameToExploreFastChainsWithinObjectGroup to filter
• Set strict solveTime limit
• Problem may be too large for chain moves
• Try simpler move types

When to Use SingleChainFast

DO use when:

• Hot container capacity-constrained (must receive back)
• Need faster chain moves than SingleChain
• Speed critical (<10s response time needed)
• Have multiple CPU cores (leverage parallelism)
• Problem is medium-large (1K-10K objects)

DO NOT use when:

• Solution quality is critical → Use SingleChain
• Hot should empty → Use SingleEndChain
• Simple moves work → Use SingleFast
• Need deterministic results

Related Move Types

Chain variants:

• SingleEndChain - Default choice for chains
• SingleChain - Best quality, slower
• SingleChainFast - Fastest, early exit (this)

Simpler alternatives:

• SingleFast - Faster single moves with early exit
• Single - Full single move exploration

Use together:

1. First: SingleFast
2. If stuck: SingleEndChain or SingleChainFast
3. For quality: SingleChain

Source Code

• Thrift definition: interface/thrift/SolverSpecs.thrift:573
• Implementation: solver/moves/SingleChainFastMoveType.h
• Tests: solver/moves/tests/

Next Steps

• Try SingleEndChain first - better default for chains
• Learn about SingleChain for best chain quality
• Review Move Types Overview for choosing move types
• See SingleFast for faster single moves