Skip to main content

SingleRandomObjectStratified

Move Type: Basic Complexity: O(object_strata × sample_size) instead of O(objects)

Sample objects from stratified groups for more intelligent source selection. Reduces search space while maintaining coverage across different object types.

Overview​

SingleRandomObjectStratified evaluates single object moves but samples source objects in a stratified manner - taking samples from different object groups rather than uniformly. This is the inverse of SingleRandomStratified which stratifies destination containers.

Use when:

  • Objects naturally group into strata (e.g., by size, type, priority)
  • Want balanced exploration across object types
  • Problem has many objects (millions)
  • Random object selection gives poor coverage

Avoid when:

  • Objects are homogeneous (no natural grouping)
  • Problem has few objects (<10K, use Single)
  • Don't have meaningful object partitions
  • Need exhaustive object exploration

Quick Example​

# Stratified object sampling across size classes
solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleRandomObjectStratifiedMoveTypeSpec(
                    objectsToExploreOptions=ObjectsToExploreOptions(
                        objectsFromGroupSpec=ObjectsFromGroupsSpec(
                            groupList=GroupList(
                                partitionName="size_class",
                            ),
                        ),
                    ),
                    stratifiedSampleSize=SampleSize(
                        defaultSampleSize=300,  # 300 objects per size class
                    ),
                ),
            ]
        )
    )
)

Parameters​

ParameterTypeRequiredDefaultDescription
stratifiedSampleSizeSampleSizeYes-Sample size per object stratum
objectsToExploreOptionsObjectsToExploreOptionsYes-Defines object strata (groups/partitions)

Parameter Details​

stratifiedSampleSize:

  • Number of objects to sample per object group
  • Uses SampleSize struct with defaultSampleSize
  • Total objects sampled = sample_size × number_of_object_groups

objectsToExploreOptions:

  • Defines the object stratification - how to group objects
  • Typically uses objectsFromGroupSpec with partition name
  • Example: group partition creates strata by object group

How It Works​

Given a cold container (underutilized destination):

  1. Define object strata: Group objects by partition (e.g., size, type)
  2. Sample per stratum: Take sample_size random objects from each group
  3. Evaluate samples: Test moving each sampled object to cold container
  4. Apply best: Apply the move that improves objective most

Visual Example​

System with 3 million objects stratified into 5 groups by size:

Group 1 (Very Small) Group 2 (Small)    Group 3 (Medium)   Group 4 (Large)    Group 5 (Very Large)
+------------------+ +------------------+ +------------------+ +------------------+ +------------------+
| 600K objects     | | 600K objects     | | 600K objects     | | 600K objects     | | 600K objects     |
|                  | |                  | |                  | |                  | |                  |
| Sample 300       | | Sample 300       | | Sample 300       | | Sample 300       | | Sample 300       |
+------------------+ +------------------+ +------------------+ +------------------+ +------------------+

Total objects evaluated: 300 × 5 = 1,500 (instead of 3,000,000!)
Coverage: Guaranteed samples from each size class

Comparison with Container Stratification​

AspectSingleRandomStratifiedSingleRandomObjectStratified
What's stratifiedDestination containersSource objects
Sample fromContainer groupsObject groups
Use caseMany heterogeneous containersMany heterogeneous objects
Best forDestination diversitySource diversity

Complexity​

Moves evaluated per iteration: O(S × K × C)

Where:

  • S = sample size per object group (stratifiedSampleSize)
  • K = number of object groups
  • C = number of destination containers (per sampled object)

Effective complexity: O(S × K) for object sampling

Example - Large object problem:

  • Total objects: 3,000,000
  • Object groups: 5
  • Sample per group: 300
  • Objects sampled: 300 × 5 = 1,500 (vs 3M for full Single)
  • Speedup: 2000x

Usage Patterns​

Size-Based Object Stratification​

Sample across object sizes:

# Ensure coverage across object size classes
# Assumes objects are partitioned into size-based groups
solver.addPartition(
    "size_class",
    {
        "very_small": ["task0"],
        "small": ["task1"],
        "medium": ["task2"],
        "large": ["task3"],
        "very_large": ["task4"],
    },
)

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleRandomObjectStratifiedMoveTypeSpec(
                    objectsToExploreOptions=ObjectsToExploreOptions(
                        objectsFromGroupSpec=ObjectsFromGroupsSpec(
                            groupList=GroupList(
                                partitionName="size_class",
                            ),
                        ),
                    ),
                    stratifiedSampleSize=SampleSize(
                        defaultSampleSize=300,  # Sample 300 per size class
                    ),
                ),
            ]
        )
    )
)

Type-Based Stratification​

Ensure coverage across object types:

# Stratify by object type/workload
solver.addPartition(
    "workload_type",
    {
        "batch": ["task0"],
        "realtime": ["task1"],
        "ml_training": ["task2"],
        "serving": ["task3"],
    },
)

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleRandomObjectStratifiedMoveTypeSpec(
                    objectsToExploreOptions=ObjectsToExploreOptions(
                        objectsFromGroupSpec=ObjectsFromGroupsSpec(
                            groupList=GroupList(
                                partitionName="workload_type",
                            ),
                        ),
                    ),
                    stratifiedSampleSize=SampleSize(
                        defaultSampleSize=200,  # Sample 200 per workload type
                    ),
                ),
            ]
        )
    )
)

Very Large Object Sets​

Millions of objects with stratification:

# Very large: 3M objects across 5 size groups
# Sample 300 per group = 1500 total (2000x reduction)
solver.addPartition(
    "size_class",
    {
        "xs": ["task0"],
        "s": ["task1"],
        "m": ["task2"],
        "l": ["task3"],
        "xl": ["task4"],
    },
)

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleRandomObjectStratifiedMoveTypeSpec(
                    objectsToExploreOptions=ObjectsToExploreOptions(
                        objectsFromGroupSpec=ObjectsFromGroupsSpec(
                            groupList=GroupList(
                                partitionName="size_class",
                            ),
                        ),
                    ),
                    stratifiedSampleSize=SampleSize(
                        defaultSampleSize=300,  # Small sample, many strata
                    ),
                ),
            ]
        )
    )
)

Priority-Based Stratification​

Sample by object priority:

# Stratify by priority level, with higher sampling for critical objects
solver.addPartition(
    "priority",
    {
        "critical": ["task0"],
        "high": ["task1"],
        "medium": ["task2"],
        "low": ["task3"],
    },
)

solver.addSolver(
    SolverSpecs(
        localSearchSolverSpec=LocalSearchSolverSpec(
            moveTypeList=[
                SingleRandomObjectStratifiedMoveTypeSpec(
                    objectsToExploreOptions=ObjectsToExploreOptions(
                        objectsFromGroupSpec=ObjectsFromGroupsSpec(
                            groupList=GroupList(
                                partitionName="priority",
                            ),
                        ),
                    ),
                    stratifiedSampleSize=SampleSize(
                        defaultSampleSize=100,  # Default sample
                        # Can override per priority if needed
                    ),
                ),
                SingleMoveTypeSpec(),  # Final exhaustive pass
            ]
        )
    )
)

Performance Characteristics​

Object Stratification Benefit​

Object GroupsSample/GroupTotal SamplesTotal ObjectsSpeedupCoverage
53001.5K3M2000xExcellent
101001K1M1000xExcellent
20501K5M5000xGood
11K1K3M3000xPoor (no stratification)

Key insight: Object stratification is most valuable when you have many heterogeneous objects.

When Does It Help?​

SingleRandomObjectStratified helps when:

  • Heterogeneous objects: Different sizes/types/priorities
  • Need coverage: Important to try all object types
  • Very large object sets: Millions of objects
  • Object partitions exist: Natural object grouping
  • Biased objectives: Some object types heavily preferred

SingleRandomObjectStratified does NOT help when:

  • Homogeneous objects: All similar, no natural grouping
  • Small object sets: Overhead not worth it
  • No partitions: Can't define meaningful object groups
  • Container stratification more important: Use SingleRandomStratified

Comparison with Variants​

Move TypeWhat's StratifiedSample FromUse Case
SingleNothingAll objects, all containersSmall problems
SingleFastNothing (early exit)Objects in orderMedium problems
SingleRandomBatchesNothing (batches)Random containersLarge + multi-core
SingleRandomStratifiedContainersContainers per stratumLarge + container diversity
SingleColdestStratifiedContainers (coldest)Coldest containers per stratumCapacity balancing
SingleRandomObjectStratifiedObjectsObjects per groupLarge + object diversity

Decision tree:

  1. Many heterogeneous objects? → SingleRandomObjectStratified
  2. Many heterogeneous containers? → SingleRandomStratified
  3. Both? → Combine both strategies
  4. Neither? → Single or SingleFast

Troubleshooting​

Problem: Poor solution quality despite object stratification​

Diagnosis: Sample size too small per group OR grouping not meaningful

Solutions:

  • Increase stratifiedSampleSize
  • Verify object groups are meaningful (similar objects in same group)
  • Check if objects vary significantly within groups
  • Try different partition/grouping
  • Combine with Single for final refinement

Problem: Not seeing speedup vs uniform sampling​

Diagnosis: Objects are homogeneous OR too few groups

Solutions:

  • Check if objects naturally group by partition
  • May not need object stratification (use Single)
  • Verify number of groups is reasonable (5-20 ideal)
  • Ensure groups have balanced sizes

Problem: Missing good moves for rare object types​

Diagnosis: Some groups have few objects but small sample size

Solutions:

  • Increase sample size for small groups
  • Use per-group sample size overrides in SampleSize
  • Consider group size when setting samples
  • May need different grouping approach

Problem: Non-deterministic results​

Diagnosis: Random sampling produces different results

Solutions:

  • Set randomSeed in LocalSearchSolverSpec
  • Increase sample size for stability
  • Run multiple times and pick best
  • Accept variance as trade-off for speed

Choosing Object Stratification​

Good object stratification characteristics:

  1. Meaningful groups: Objects in same group are similar
  2. Balanced sizes: Groups have roughly equal number of objects
  3. Diverse outcomes: Moving different groups has different effects
  4. Reasonable count: 5-20 groups ideal

Common object stratification strategies:

  • Size: Small/medium/large objects
  • Type: Object type, class, category
  • Priority: High/medium/low priority
  • Resource usage: CPU/memory/disk bins

Example partition hierarchies:

size_class > object_type > object
priority_level > team > object
resource_bin > workload_type > object

Stratified variants:

Sampling alternatives:

Use together:

  1. SingleRandomObjectStratified for object diversity
  2. Can combine with container stratification for double stratification
  3. Follow with Single for final refinement

Source Code​

Next Steps​