TripleLoop

Move Type: Advanced Complexity: O(objects³)

Evaluate 3-object cyclic moves to escape deep local optima. Very expensive - use only when simpler move types fail.

Overview

TripleLoop evaluates moving three objects in a cycle: object A from hot container to container X, object B from container X to container Y, and object C from container Y back to hot container. This powerful but expensive move type can escape local optima that simpler moves cannot.

Use when:

Stuck in deep local optimum with simpler move types
Problem requires complex multi-object rearrangements
Solution quality is critical and time is available
Problem size is small (<1K objects)

Avoid when:

Problem is large (>1K objects) - will be extremely slow
Simpler move types (Single, Swap, Chain) work
Time constraints are strict
Running in production with strict SLAs

Quick Example

Python
C++

# Only use TripleLoop for small problems or as last resort
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleMoveTypeSpec(),
                SwapMoveTypeSpec(),
                TripleLoopMoveTypeSpec(),  # Last resort for deep local optima
            ]
        )
    )
)

void quickExample() {
  // Only use TripleLoop for small problems or as last resort
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  LocalSearchSolverSpec solverSpec;

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

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

  // Add TripleLoop
  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().tripleLoopMoveTypeSpec() =
      TripleLoopMoveTypeSpec{};

  solver.addSolver(solverSpec);
}

Parameters

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

How It Works

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

Select hot object: Pick object A from hot container
Select container X: Pick different container X
Select object B: Pick object B from container X
Select container Y: Pick different container Y (≠ hot, ≠ X)
Select object C: Pick object C from container Y
Evaluate cycle: Test the 3-move cycle:
- Move A: hot → X
- Move B: X → Y
- Move C: Y → hot
Repeat: Try all combinations
Apply best: Apply the 3-move cycle improving objective most

Visual Example

Before:                          After (if triple loop applied):
┌─────────────┐                 ┌─────────────┐
│ Hot         │  ─────(1)────>  │ Hot         │
│ Container   │                 │ Container   │
│  • objA ──┐ │  <────(3)─────  │  • objC  ←─┐│
│  • obj2   │ │                 │  • obj2    ││
└───────────┼─┘                 └────────────┼┘
            │                                │
┌───────────┼─┐                 ┌────────────┼┐
│ Container X│ │                 │ Container X││
│  • objB ──┼─┘  ─────(2)────>  │  • objA ←──┘│
│  • objY   │                   │  • objY     │
└───────────┘                   └─────────────┘
┌─────────────┐                 ┌─────────────┐
│ Container Y │                 │ Container Y │
│  • objC  ───┘                 │  • objB  ←──┘
│  • objZ     │                 │  • objZ     │
└─────────────┘                 └─────────────┘

Cycle: A (Hot→X), B (X→Y), C (Y→Hot)

Why TripleLoop Helps

Problem: Swap and Chain moves can't fix this:

Swapping any two objects makes things worse
2-move chains don't create right configuration

Solution: 3-object cycle can rearrange in ways that 2-object moves cannot

Explores neighborhood unreachable by simpler moves
Can escape "deep" local optima

Complexity

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

Simplified to O(N³) when containers have similar sizes

Where:

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

Example - Small problem:

Hot container: 100 objects
System: 50 containers
Moves evaluated ≈ 100³ × 50 = 50 million moves per iteration

Example - Medium problem (impractical):

Hot container: 1,000 objects
System: 100 containers
Moves evaluated ≈ 1,000³ × 100 = 100 billion moves per iteration

Warning: This is extremely expensive. Only use for small problems.

Usage Patterns

Last Resort for Stuck Solver

Use after simpler moves fail:

Python
C++

# Try progressively more powerful moves
solver = ProblemSolver(service_name="example", service_scope="test")

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleMoveTypeSpec(),  # Add Single
                SwapMoveTypeSpec(),  # Add Swap
                SingleEndChainMoveTypeSpec(),  # Add SingleEndChain
                TripleLoopMoveTypeSpec(),  # Add TripleLoop - last resort
            ]
        )
    )
)

void lastResort() {
  // Try progressively more powerful moves
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  LocalSearchSolverSpec solverSpec;

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

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

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

  // Add TripleLoop - last resort
  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().tripleLoopMoveTypeSpec() =
      TripleLoopMoveTypeSpec{};

  solver.addSolver(solverSpec);
}

Small Problem Only

Only for problems known to be small:

Python
C++

# For problems with <100 objects per container
# WARNING: Do not use with large problems!
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleMoveTypeSpec(),
                TripleLoopMoveTypeSpec(),  # Safe for small problems only
            ]
        )
    )
)

void smallProblem() {
  // For problems with <100 objects per container
  // WARNING: Do not use with large problems!
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  LocalSearchSolverSpec solverSpec;

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

  // Add TripleLoop - safe for small problems only
  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().tripleLoopMoveTypeSpec() =
      TripleLoopMoveTypeSpec{};

  solver.addSolver(solverSpec);
}

With Strict Time Limits

Prevent TripleLoop from running too long:

Python
C++

# Strict time limit to prevent expensive TripleLoop from taking too long
solver = ProblemSolver(service_name="example", service_scope="test")

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            solveTime=60,  # Maximum 60 seconds total
            moveTypeList=[
                SingleMoveTypeSpec(),  # Add Single
                SwapMoveTypeSpec(),  # Add Swap
                TripleLoopMoveTypeSpec(),  # Add TripleLoop - will stop after 60s
            ],
        )
    )
)

void timeLimits() {
  // Strict time limit to prevent expensive TripleLoop from taking too long
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  LocalSearchSolverSpec solverSpec;
  solverSpec.solveTime() = 60; // Maximum 60 seconds total

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

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

  // Add TripleLoop - will stop after 60s
  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().tripleLoopMoveTypeSpec() =
      TripleLoopMoveTypeSpec{};

  solver.addSolver(solverSpec);
}

Offline Optimization

Taking time for best possible solution:

Python
C++

# Offline optimization - take time to find best solution
# Use when solution quality is critical and time is available
solver = ProblemSolver(service_name="example", service_scope="test")

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            solveTime=3600,  # Allow 1 hour
            moveTypeList=[
                SingleMoveTypeSpec(),  # Add Single
                SwapMoveTypeSpec(),  # Add Swap
                SingleEndChainMoveTypeSpec(),  # Add SingleEndChain
                TripleLoopMoveTypeSpec(),  # Add TripleLoop - thorough search for best solution
            ],
        )
    )
)

void offline() {
  // Offline optimization - take time to find best solution
  // Use when solution quality is critical and time is available
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  LocalSearchSolverSpec solverSpec;
  solverSpec.solveTime() = 3600; // Allow 1 hour

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

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

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

  // Add TripleLoop - thorough search for best solution
  solverSpec.moveTypeList()->emplace_back();
  solverSpec.moveTypeList()->back().tripleLoopMoveTypeSpec() =
      TripleLoopMoveTypeSpec{};

  solver.addSolver(solverSpec);
}

Performance Characteristics

Scalability

Objects	Containers	Time per Iteration	Practical?
10	10	<1s	✓ Yes
50	50	10-60s	△ Marginal
100	100	5-30 minutes	✗ No
>100	>100	Hours+	✗ Absolutely not

Hard limit: Do not use TripleLoop with >100 objects per container.

When Does It Help?

TripleLoop helps when:

Graph partitioning problems (need 3-way swaps)
Highly constrained problems (few feasible moves)
Complex dependencies between objects
Stuck at local optimum, no simpler moves improve

TripleLoop does NOT help when:

Problem is just large (won't finish)
Initial assignment is terrible (too many broken things)
Constraints are impossible (no amount of searching helps)

Comparison with Alternatives

Move Type	Complexity	Max Problem Size	Escape Power	Use Case
Single	O(N × C)	100K+ objects	Low	Default choice
Swap	O(N²)	10K objects	Medium	Capacity-constrained
SingleEndChain	O(N² × C)	1K objects	Medium-High	2-move sequences
TripleLoop	O(N³)	100 objects	Highest	Deep local optima
KLSearch	Expensive	1K objects	Very High	Graph partitioning

Recommendation: Try in order: Single → Swap → Chain → TripleLoop (last resort)

Troubleshooting

Problem: TripleLoop taking forever

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

Solutions:

Remove TripleLoop if >100 objects per container
Set strict solveTime limit
Only use for final refinement stage with small time budget
Check if problem is actually small enough

Problem: TripleLoop not helping

Diagnosis: Not the right move type for this problem

Solutions:

Problem may not need 3-object cycles
Try KLSearch instead (graph partitioning)
Check if constraints allow ANY improvement
Improve initial assignment instead
Accept current local optimum

Problem: Running out of memory

Diagnosis: Too many move evaluations

Solutions:

Problem is too large for TripleLoop
Use simpler move types
Reduce problem size (fewer objects/containers)
This is a sign TripleLoop is wrong choice

Problem: Solution not improving despite time

Diagnosis: Exploring many moves but none improve

Solutions:

May already be at good local optimum
Check if constraints are blocking all moves
Try multiple runs with different initial assignments
Consider that current solution may be near-optimal

When to Use TripleLoop

DO use when:

Problem is small (<100 objects per container)
Stuck at local optimum with all simpler moves
Solution quality is critical
Have time budget (offline optimization)
Graph partitioning or complex rearrangement problem

DO NOT use when:

Problem is medium/large (>100 objects)
Production environment with time constraints
Simpler moves are still finding improvements
Just starting optimization (try simple moves first)

Simpler alternatives (try first):

Single - O(N × C)
Swap - O(N²)
SingleEndChain - O(N² × C)

Similar complexity:

KLSearch - Also expensive, for graph partitioning

When to use each:

First: Single, Swap
If stuck: SingleEndChain
If still stuck and small: TripleLoop
For graph problems: KLSearch

Source Code

Thrift definition: interface/thrift/SolverSpecs.thrift:559
Implementation: solver/moves/TripleLoopMoveType.h
Tests: solver/moves/tests/

Next Steps

Try SingleEndChain before TripleLoop (less expensive)
Consider KLSearch for graph partitioning problems
Review Performance Guide for optimization strategies
See Move Types Overview for choosing appropriate move types

Overview​

Quick Example​

Parameters​

How It Works​

Visual Example​

Why TripleLoop Helps​

Complexity​

Usage Patterns​

Last Resort for Stuck Solver​

Small Problem Only​

With Strict Time Limits​

Offline Optimization​

Performance Characteristics​

Scalability​

When Does It Help?​

Comparison with Alternatives​

Troubleshooting​

Problem: TripleLoop taking forever​

Problem: TripleLoop not helping​

Problem: Running out of memory​

Problem: Solution not improving despite time​

When to Use TripleLoop​

Related Move Types​

Source Code​

Next Steps​

Overview

Quick Example

Parameters

How It Works

Visual Example

Why TripleLoop Helps

Complexity

Usage Patterns

Last Resort for Stuck Solver

Small Problem Only

With Strict Time Limits

Offline Optimization

Performance Characteristics

Scalability

When Does It Help?

Comparison with Alternatives

Troubleshooting

Problem: TripleLoop taking forever

Problem: TripleLoop not helping

Problem: Running out of memory

Problem: Solution not improving despite time

When to Use TripleLoop

Related Move Types

Source Code

Next Steps