SingleEndChain

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

Perform 2-move chains where an object leaves the hot container and another object moves to a different container (not back to hot container). Often better than Swap for capacity-constrained problems.

Overview

SingleEndChain evaluates 2-move sequences where:

1. Object A moves from hot container → container X
2. Object B moves from container X → container Y (different from hot container)

The hot container is at the end of the chain (receives no object back), unlike SingleChain where the hot container is in the middle.

Use when:

• Capacity constraints are tight (alternative to Swap)
• Need 2-move sequences to improve objective
• Swap moves aren't finding improvements

Prefer over SingleChain:

• SingleEndChain is generally more effective
• Recommended default for chain moves

Quick Example

Python

# Use SingleEndChain for high-quality capacity-constrained solutions
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleMoveTypeSpec(),
                SwapMoveTypeSpec(),
                SingleEndChainMoveTypeSpec(),  # Expensive but effective
            ]
        )
    )
)

C++

void quickExample() {
  // Use SingleEndChain for high-quality capacity-constrained solutions
  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().singleMoveTypeSpec() = SingleMoveTypeSpec{};

  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().swapMoveTypeSpec() = SwapMoveTypeSpec{};

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

  solver.addSolver(solverSpec);
}

Parameters

Parameter	Type	Required	Default	Description
(none)	-	-	-	SingleEndChain has no configuration parameters

How It Works

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

1. Select hot object: Pick object from hot container
2. Select intermediate container: Pick container X (receives hot object)
3. Select other object: Pick object from container X
4. Select final container: Pick container Y ≠ hot container
5. Evaluate chain: Test moving hot object → X, other object → Y (simultaneously)
6. Repeat: Try all combinations
7. Apply best: Apply the 2-move chain improving objective most

Visual Example

Before:                          After (if chain applied):
┌─────────────┐                 ┌─────────────┐
│ Hot         │                 │ Hot         │
│ Container   │  ─────(1)────>  │ Container   │
│  • obj1     │                 │  • obj2     │
│  • obj2     │                 │  • obj3     │
│  • obj3     │                 └─────────────┘
└─────────────┘
┌─────────────┐                 ┌─────────────┐
│ Container X │                 │ Container X │
│  • objA     │  ─────(2)────>  │  • obj1  ←─┐│
│  • objB     │                 │  • objB   ││
└─────────────┘                 └───────────┼┘
┌─────────────┐                 ┌───────────┼┐
│ Container Y │                 │ Container Y││
│  • objX     │                 │  • objX   ││
│  • objY     │                 │  • objY   ││
└─────────────┘                 │  • objA ←─┘│
                                └─────────────┘

Chain: obj1 (Hot→X), objA (X→Y)

Comparison with SingleChain

SingleEndChain (Recommended):

Hot Container → Container X → Container Y
  gives obj1      gives objA    receives objA
  (net: -1)       (net: 0)      (net: +1)

SingleChain (Less recommended):

Hot Container ← Container X → Container Y
  receives objB   gives objA    receives objA
  (net: 0)       gives objB     (net: +1)
                 (net: -1)

Why SingleEndChain is better: Hot container is "broken" (highest cost), so we want to reduce its load, not keep it the same.

Complexity

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

• Simplifies to O(N² × C) for uniform container sizes

Where:

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

Example:

• Hot container has 100 objects
• Each container has ~100 objects
• System has 50 containers
• Moves evaluated = 100 × 100 × 50² ≈ 25M moves

Warning: Very expensive! Use after simpler move types.

Usage Patterns

Basic Configuration

Use after Single and Swap for better quality:

Python

# Use after Single and Swap for better quality
solver = ProblemSolver(service_name="example", service_scope="test")

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleMoveTypeSpec(),
                SwapMoveTypeSpec(),
                SingleEndChainMoveTypeSpec(),
            ]
        )
    )
)

C++

void basicConfiguration() {
  // Use after Single and Swap for better quality
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  LocalSearchSolverSpec solverSpec;

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

  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().swapMoveTypeSpec() = SwapMoveTypeSpec{};

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

  solver.addSolver(solverSpec);
}

Capacity-Constrained with High Quality Needs

When you need best possible solution for tight capacity:

Python

# Best quality for capacity-constrained problems
solver = ProblemSolver(service_name="example", service_scope="test")

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            solveTime=600,  # 10 minutes - allow time for expensive moves
            moveTypeList=[
                SingleMoveTypeSpec(),
                SwapMoveTypeSpec(),
                SingleEndChainMoveTypeSpec(),
            ],
        )
    )
)

C++

void highQuality() {
  // Best quality for capacity-constrained problems
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  LocalSearchSolverSpec solverSpec;
  solverSpec.solveTime() = 600; // 10 minutes - allow time for expensive moves

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

  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().swapMoveTypeSpec() = SwapMoveTypeSpec{};

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

  solver.addSolver(solverSpec);
}

Production Rebalancing

Balance quality and time:

Python

# Balance quality and time for production
solver.addConstraint(
    ConstraintSpecs(
        capacitySpec=CapacitySpec(
            name="memory-capacity",
            scope="host",
            dimension="memory",
            limit=Limit(globalLimit=10.0),
        )
    )
)

solver.addGoal(
    GoalSpecs(
        balanceSpec=BalanceSpec(
            name="balance-memory", scope="host", dimension="memory"
        )
    ),
    weight=10.0,
)

solver.addGoal(
    GoalSpecs(minimizeMovementSpec=MinimizeMovementSpec(name="minimize-moves")),
    weight=1.0,
)

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            solveTime=300,  # 5 minutes limit
            moveTypeList=[
                SingleMoveTypeSpec(),
                SwapMoveTypeSpec(),
                SingleEndChainMoveTypeSpec(),  # Gets remaining time
            ],
        )
    )
)

C++

void productionRebalancing() {
  // Balance quality and time for production
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");
  solver.setObjectName("shard");
  solver.setContainerName("host");

  CapacitySpec capacitySpec;
  capacitySpec.name() = "memory-capacity";
  capacitySpec.scope() = "host";
  capacitySpec.dimension() = "memory";
  Limit limit;
  limit.globalLimit() = 10.0;
  capacitySpec.limit() = std::move(limit);
  solver.addConstraint(std::move(capacitySpec));

  BalanceSpec balanceSpec;
  balanceSpec.name() = "balance-memory";
  balanceSpec.scope() = "host";
  balanceSpec.dimension() = "memory";
  solver.addGoal(std::move(balanceSpec), 10.0);

  MinimizeMovementSpec moveSpec;
  moveSpec.name() = "minimize-moves";
  solver.addGoal(std::move(moveSpec), 1.0);

  LocalSearchSolverSpec solverSpec;
  solverSpec.solveTime() = 300; // 5 minutes limit

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

  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().swapMoveTypeSpec() = SwapMoveTypeSpec{};

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

  solver.addSolver(solverSpec);
}

Performance Characteristics

Scalability

Objects	Containers	Typical Time per Iteration	Recommendation
<100	<10	<1s	Safe to use
100-1K	10-100	1-30s	Use with time limits
>1K	>100	>30s	Consider avoiding

Time Limits

Since SingleEndChain is expensive, often used with time limits:

LocalSearchSolverSpec(
    solveTime=300,  # 5 minutes total
    moveTypeList=[
        SingleMoveTypeSpec(),      # Fast
        SwapMoveTypeSpec(),        # Medium
        SingleEndChainMoveTypeSpec(),  # Expensive - gets remaining time
    ]
)

Recommended Problem Sizes

• Use freely: <1K objects, <100 containers
• Use cautiously: 1K-10K objects, 100-1K containers (with time limits)
• Avoid: >10K objects or >1K containers

Comparison with Alternatives

Move Type	Speed	Quality	Capacity-Aware	Use Case
Single	Fast	Good	No	Unconstrained problems
Swap	Medium	Better	Yes	Capacity-constrained
SingleEndChain	Slow	Best	Yes	High-quality capacity solutions
SingleChain	Slow	Good	Yes	Less effective than SingleEndChain
SingleChainFast	Medium	Good	Yes	Faster chain variant

Recommendation: For capacity-constrained problems:

1. Start with Single + Swap
2. Add SingleEndChain if you need better quality and can afford the time
3. Consider SingleChainFast as middle ground

Troubleshooting

Problem: SingleEndChain too slow

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

Solutions:

• Remove SingleEndChain for large problems (>10K objects)
• Use SingleChainFast instead (parallelized with early exit)
• Add solveTime limit to prevent excessive time
• Try Swap instead (simpler, often sufficient)

Problem: Not finding improvements

Diagnosis: May need even more complex moves or better initial state

Solutions:

• Ensure Single and Swap tried first (SingleEndChain should be last)
• Add TripleLoop for 3-object moves (very expensive)
• Check if initial assignment is feasible
• Verify constraints allow chain moves

Problem: Taking too long per iteration

Diagnosis: Many objects/containers = expensive evaluation

Solutions:

• Set solveTime to limit total time
• Use SingleEndChain only in final optimization stage
• Consider whether chain moves are necessary for your problem
• Profile to check if other issues (slow constraints/objectives)

When to Use vs Swap

Use Swap when:

• Problem size is large (>10K objects)
• Need capacity-aware moves quickly
• Simple swaps are sufficient

Use SingleEndChain when:

• Need highest quality solution
• Have time budget for expensive search
• Swap alone isn't finding good solutions
• Problem size is small-medium (<10K objects)

Use both when:

moveTypeList=[
    SingleMoveTypeSpec(),
    SwapMoveTypeSpec(),          # Try swaps first (faster)
    SingleEndChainMoveTypeSpec(),  # Then chains (slower, higher quality)
]

Related Move Types

Variants:

• SingleChain - Chain with hot container in middle (less effective)
• SingleChainFast - Parallelized chain with early exit

Alternatives:

• Swap - Simpler 2-object exchange (often sufficient)
• Single - Simple 1-object moves

More Complex:

• TripleLoop - 3-object cyclic moves (even more expensive)

Source Code

• Thrift definition: interface/thrift/SolverSpecs.thrift:535
• Implementation: solver/moves/SingleEndChainMoveType.h
• Tests: solver/moves/tests/

Next Steps

• Compare with SingleChain to understand the difference
• Try SingleChainFast for faster chain moves
• Learn about Swap as simpler alternative
• Review Performance Guide for optimization