SingleColdestStratified

Move Type: Basic Complexity: O(strata × sample_size) with coldest-first ordering

Move objects to the coldest (least loaded) containers within each stratum. Combines stratified sampling with capacity-aware greedy selection.

Overview

SingleColdestStratified evaluates single object moves to the coldest containers (containers with lowest load/potential) within each stratum. Unlike random stratified sampling, this move type preferentially targets underutilized containers, making it excellent for capacity balancing and bin-packing.

Use when:

Capacity balancing is critical
Want to fill underutilized containers
Containers group into natural strata
Bin-packing or consolidation scenarios

Avoid when:

Load balancing across all containers equally important
Containers are homogeneous (no strata)
"Coldest" doesn't align with objective
Need deterministic results

Quick Example

Python
C++

# Move to coldest containers per stratum (legacy string-based)
spec = LocalSearchSolverSpec(
    stratifiedSampleSize=10,  # Sample 10 coldest per stratum
    moveTypeList=[
        MoveTypeSpec(moveTypeName="SINGLE_COLDEST_STRATIFIED"),
    ],
)
solver.addSolver(SolverSpecs(localSearchSolverSpec=spec))

void quickExample() {
  // Move to coldest containers per stratum (legacy string-based)
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");
  solver.setObjectName("task");
  solver.setContainerName("host");

  LocalSearchSolverSpec spec;
  spec.stratifiedSampleSize() = 10; // Sample 10 coldest per stratum

  spec.moveTypeList()->emplace_back();
  spec.moveTypeList()->back().moveTypeName() = "SINGLE_COLDEST_STRATIFIED";

  solver.addSolver(spec);

Parameters

Note: SingleColdestStratified uses the legacy string-based move type specification. Parameters are set on LocalSearchSolverSpec, not a dedicated move type spec.

Parameter	Type	Required	Default	Description
`moveTypeName`	string	Yes	-	Set to `"SINGLE_COLDEST_STRATIFIED"`
`stratifiedSampleSize`	int32	No	10	Sample size of coldest containers per stratum
`includeEqualSizeRandomSampleForSingleColdestMoveType`	bool	No	false	Double sample size by adding random containers

Parameter Details

stratifiedSampleSize:

Number of coldest containers to sample per stratum
Containers are ranked by "coldness" (low load/potential)
Default: 10 containers per stratum

includeEqualSizeRandomSampleForSingleColdestMoveType:

When true: Sample k coldest + k random containers per stratum (total 2k)
When false: Sample only k coldest containers per stratum
Helps avoid getting stuck in local optima by adding randomness

How It Works

Given a hot container and object to move:

Define strata: Group containers by scope or similarity
Find coldest per stratum: Rank containers by coldness (low load)
Sample coldest: Take stratifiedSampleSize coldest from each stratum
Optional random: If enabled, add equal number of random containers
Evaluate samples: Test moving object to each sampled container
Apply best: Apply the move that improves objective most

What is "Coldest"?

A container is cold if it has:

Low container potential: Low contribution to objective
Few objects: Underutilized capacity
Spare capacity: Room to accept more objects

Coldness ranking: Lower potential = colder = more preferred

Visual Example

System with 5 regions (strata), sample size = 2:

Region 1           Region 2           Region 3           Region 4           Region 5
+-----------+      +-----------+      +-----------+      +-----------+      +-----------+
| Coldest 1 |  ←   | Coldest 1 |  ←   | Coldest 1 |  ←   | Coldest 1 |  ←   | Coldest 1 |
| Coldest 2 |  ←   | Coldest 2 |  ←   | Coldest 2 |  ←   | Coldest 2 |  ←   | Coldest 2 |
|  (rest)   |      |  (rest)   |      |  (rest)   |      |  (rest)   |      |  (rest)   |
+-----------+      +-----------+      +-----------+      +-----------+      +-----------+

Total evaluations: 2 × 5 = 10 coldest containers

With includeEqualSizeRandomSampleForSingleColdestMoveType=true:
  2 coldest + 2 random per region = 4 per region
  Total evaluations: 4 × 5 = 20 containers

Comparison with Variants

Move Type	Selection Strategy	Coverage	Use Case
SingleRandomStratified	Random per stratum	Balanced	General stratified sampling
SingleColdestStratified	Coldest per stratum	Capacity-aware	Bin-packing, consolidation
SingleRandomObjectStratified	Random objects	Object diversity	Object-level stratification

Complexity

Moves evaluated per iteration: O(S × K)

Where:

S = stratifiedSampleSize (or 2×S if random sampling enabled)
K = number of strata

Example - Capacity balancing:

Regions (strata): 5
Sample per region: 10 coldest
Moves evaluated: 10 × 5 = 50
With random sampling: 20 × 5 = 100

Usage Patterns

Bin-Packing/Consolidation

Fill underutilized containers:

Python
C++

# Bin-packing: fill coldest (most empty) containers
solver.addGoal(
    GoalSpecs(
        minimizeContainersSpec=MinimizeContainersSpec(
            name="minimize-containers",
            scope="container",
        )
    ),
    weight=10.0,
)

spec = LocalSearchSolverSpec(
    stratifiedSampleSize=10,  # Try 10 coldest per stratum
    moveTypeList=[
        MoveTypeSpec(moveTypeName="SINGLE_COLDEST_STRATIFIED"),
    ],
)
solver.addSolver(SolverSpecs(localSearchSolverSpec=spec))

void binPacking() {
  // Bin-packing: fill coldest (most empty) containers
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");
  solver.setObjectName("task");
  solver.setContainerName("host");

  MinimizeContainersSpec minimizeSpec;
  minimizeSpec.name() = "minimize-containers";
  minimizeSpec.scope() = "host";
  solver.addGoal(std::move(minimizeSpec), 10.0);

  LocalSearchSolverSpec spec;
  spec.stratifiedSampleSize() = 10; // Try 10 coldest per stratum

  spec.moveTypeList()->emplace_back();
  spec.moveTypeList()->back().moveTypeName() = "SINGLE_COLDEST_STRATIFIED";

  solver.addSolver(spec);

Capacity Balancing Across Regions

Balance load while respecting regions:

Python
C++

# Move to coldest servers in each region for capacity balancing
spec = LocalSearchSolverSpec(
    stratifiedSampleSize=20,  # Sample 20 coldest per region
    moveTypeList=[
        MoveTypeSpec(moveTypeName="SINGLE_COLDEST_STRATIFIED"),
    ],
)
solver.addSolver(SolverSpecs(localSearchSolverSpec=spec))

void capacityBalancing() {
  // Move to coldest servers in each region for capacity balancing
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");
  solver.setObjectName("task");
  solver.setContainerName("server");

  LocalSearchSolverSpec spec;
  spec.stratifiedSampleSize() = 20; // Sample 20 coldest per region

  spec.moveTypeList()->emplace_back();
  spec.moveTypeList()->back().moveTypeName() = "SINGLE_COLDEST_STRATIFIED";

  solver.addSolver(spec);

With Random Sampling for Diversity

Add randomness to avoid local optima:

Python
C++

# Include random sampling for diversity: k coldest + k random
spec = LocalSearchSolverSpec(
    stratifiedSampleSize=10,  # 10 coldest
    includeEqualSizeRandomSampleForSingleColdestMoveType=True,  # + 10 random = 20 total
    moveTypeList=[
        MoveTypeSpec(moveTypeName="SINGLE_COLDEST_STRATIFIED"),
    ],
)
solver.addSolver(SolverSpecs(localSearchSolverSpec=spec))

void randomSampling() {
  // Include random sampling for diversity: k coldest + k random
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");

  LocalSearchSolverSpec spec;
  spec.stratifiedSampleSize() = 10; // 10 coldest
  spec.includeEqualSizeRandomSampleForSingleColdestMoveType() =
      true; // + 10 random = 20 total

  spec.moveTypeList()->emplace_back();
  spec.moveTypeList()->back().moveTypeName() = "SINGLE_COLDEST_STRATIFIED";

  solver.addSolver(spec);

Server Decommissioning

Empty servers by moving to coldest alternatives:

Python
C++

# Decommission servers: move shards to coldest available servers
# Use with toFree or nonAccepting constraints to mark servers for decommission
spec = LocalSearchSolverSpec(
    stratifiedSampleSize=15,  # Try 15 coldest alternatives per region
    moveTypeList=[
        MoveTypeSpec(moveTypeName="SINGLE_COLDEST_STRATIFIED"),
    ],
)
solver.addSolver(SolverSpecs(localSearchSolverSpec=spec))

void decommission() {
  // Decommission servers: move shards to coldest available servers
  // Use with toFree or nonAccepting constraints to mark servers for
  // decommission
  auto executor = std::make_shared<folly::CPUThreadPoolExecutor>(4);
  ProblemSolver solver(executor, "example", "test");
  solver.setObjectName("shard");
  solver.setContainerName("server");

  LocalSearchSolverSpec spec;
  spec.stratifiedSampleSize() = 15; // Try 15 coldest alternatives per region

  spec.moveTypeList()->emplace_back();
  spec.moveTypeList()->back().moveTypeName() = "SINGLE_COLDEST_STRATIFIED";

  solver.addSolver(spec);

Performance Characteristics

Sample Size Tuning

Sample Size	Random Enabled	Total Samples (5 strata)	Quality	Use Case
5	No	25	Low	Very fast, rough balancing
10 (default)	No	50	Medium	Balanced speed/quality
10	Yes	100	Higher	Add diversity
20	No	100	High	Thorough coldest search
20	Yes	200	Highest	Maximum quality

When Does It Help?

SingleColdestStratified helps when:

Capacity imbalance: Some containers nearly full, others nearly empty
Bin-packing: Want to minimize active containers
Consolidation: Fill existing containers before using new ones
Stratified structure: Containers naturally group (regions, sizes)
Greedy works: Moving to coldest aligns with objective

SingleColdestStratified does NOT help when:

All containers similar load: No "cold" containers to target
Coldest ≠ best: Objective doesn't favor underutilized containers
Need randomness: Deterministic coldest selection gets stuck
Homogeneous containers: No meaningful stratification

Comparison with Variants

Move Type	Selection	Randomness	Best For
Single	All containers	None	Small, complete search
SingleFast	Early exit	None	Medium, fast
SingleRandomBatches	Batches	Uniform random	Large, parallel
SingleRandomStratified	Per stratum	Stratified random	Large, balanced
SingleColdestStratified	Coldest per stratum	Optional random	Capacity balancing

Decision tree:

Capacity balancing needed? → SingleColdestStratified
General stratified? → SingleRandomStratified
No stratification? → Single or SingleFast

Troubleshooting

Problem: Always moving to same cold containers

Diagnosis: Sample size too small OR not using random sampling

Solutions:

Increase stratifiedSampleSize
Enable includeEqualSizeRandomSampleForSingleColdestMoveType=true
Check if "coldest" definition aligns with objective
May need different move type if cold containers filling up

Problem: Not balancing capacity well

Diagnosis: Coldness metric doesn't capture capacity

Solutions:

Verify objective function includes capacity terms
Check container potential calculation
May need explicit capacity constraints/goals
Consider MinimizeContainers goal

Problem: Getting stuck in local optimum

Diagnosis: Deterministic coldest selection

Solutions:

Enable includeEqualSizeRandomSampleForSingleColdestMoveType=true
Increase sample size for more options
Combine with SingleRandomStratified
Use multi-stage with different move types

Problem: Stratification not helping

Diagnosis: Strata not meaningful OR coldest similar across strata

Solutions:

Verify containers actually group into meaningful strata
Check coldness varies across strata
May need different stratification (different scope)
Consider SingleRandomBatches instead

When to Use SingleColdestStratified

DO use when:

Bin-packing or container consolidation
Capacity balancing across regions/groups
Filling underutilized containers
Decommissioning servers (move to cold alternatives)
Objective favors moving to less-loaded containers

DO NOT use when:

All containers equally loaded
Coldest selection doesn't align with objective
Need random exploration
Containers are homogeneous

Stratified variants:

SingleRandomStratified - Random per stratum
SingleColdestStratified - Coldest per stratum (this)
SingleRandomObjectStratified - Object stratification

Capacity-focused:

SwapFullWithEmpty - Move all to empty
MinimizeContainers - Goal for consolidation

Use together:

SingleColdestStratified for capacity balancing
Swap for fine-tuning
MinimizeContainers goal

Source Code

Move type name: "SINGLE_COLDEST_STRATIFIED" (legacy string-based)
Parameters: interface/thrift/SolverSpecs.thrift:168,174
Implementation: solver/moves/SingleColdestStratifiedMoveType.h
Tests: solver/moves/tests/

Next Steps

Learn about SingleRandomStratified for random stratified sampling
Try SingleRandomObjectStratified for object stratification
Review MinimizeContainers for consolidation goals
See Move Types Overview for choosing move types

Overview​

Quick Example​

Parameters​

Parameter Details​

How It Works​

What is "Coldest"?​

Visual Example​

Comparison with Variants​

Complexity​

Usage Patterns​

Bin-Packing/Consolidation​

Capacity Balancing Across Regions​

With Random Sampling for Diversity​

Server Decommissioning​

Performance Characteristics​

Sample Size Tuning​

When Does It Help?​

Comparison with Variants​

Troubleshooting​

Problem: Always moving to same cold containers​

Problem: Not balancing capacity well​

Problem: Getting stuck in local optimum​

Problem: Stratification not helping​

When to Use SingleColdestStratified​

Related Move Types​

Source Code​

Next Steps​

Overview

Quick Example

Parameters

Parameter Details

How It Works

What is "Coldest"?

Visual Example

Comparison with Variants

Complexity

Usage Patterns

Bin-Packing/Consolidation

Capacity Balancing Across Regions

With Random Sampling for Diversity

Server Decommissioning

Performance Characteristics

Sample Size Tuning

When Does It Help?

Comparison with Variants

Troubleshooting

Problem: Always moving to same cold containers

Problem: Not balancing capacity well

Problem: Getting stuck in local optimum

Problem: Stratification not helping

When to Use SingleColdestStratified

Related Move Types

Source Code

Next Steps