Amazon's SCOT and my RAPID: Sub-15ms Multi-Objective Constraint Propagation

How to solve NP-hard combinatorial order routing, fulfillment allocation, and multi-resource distribution in sub-15ms without expensive commercial LP solvers.

1. The NP-Hard Combinatorial Explosion Problem

• An order with 15 items across 25 warehouses yields $25^{15} \approx 9.31 \times 10^{20}$ possible combinations.
• A campaign allocator attempting to distribute 100 message batches across 10 worker nodes yields $10^{100}$ combinations—more than the total number of atoms in the observable universe.

1. License Costs: Millions of dollars per year in enterprise licensing fees.
2. Infrastructure Footprint: Heavy C++ native binaries, high memory consumption, and multi-second solving latencies.
3. Fragility: High latency spikes under sudden burst loads.

2. The Core Philosophy: Shrink First, Solve Second

"Don't waste compute searching an exponential space. Use constraint propagation to shrink the space first."

Phase 1: Constraint Propagation  →  Eliminate impossible routes (85-99% space reduction)
Phase 2: Adaptive Solver Selection→  B&B for small spaces (exact) | Greedy Set Cover for large
Phase 3: Pareto Evaluation       →  Balance Cost, Speed, Shipment Count, and Load
Phase 4: Incremental Recovery    →  Re-solve only affected items if a warehouse fails

High-Level Architecture Pipeline

3. Deep-Dive: The 4-Phase Pipeline Mechanics

Phase 1: Multi-Stage Constraint Propagation (AC-3 Engine)

• $X = \{x_1, x_2, \dots, x_N\}$: Variables (items or message batches).
• $D = \{D(x_1), D(x_2), \dots, D(x_N)\}$: Domains (set of eligible warehouses or workers).
• $C = \{c_1, c_2, \dots, c_K\}$: Hard constraints (stock levels, SLA delivery time limits, maximum shipments).

The AC-3 Arc Consistency Algorithm

Phase 2: Adaptive Solver Engine

1. Branch & Bound Solver ($\le 10,000$ Candidates): Performs a depth-first tree search combined with admissible lower-bound heuristic pruning. If the current sub-tree cost plus the estimated lower bound exceeds the best-known solution cost ($f(n) = g(n) + h(n) \ge \text{Cost}_{best}$), the sub-tree is pruned instantly.
2. Greedy Set Cover Solver ($> 10,000$ Candidates): When space remains huge, RAPID switches to a greedy set-covering heuristic that selects warehouses maximizing the cost-per-covered-item ratio. This yields an $O(N \log N)$ execution time with a proven $\ln(N)$ approximation ratio guarantee.

Phase 3: Multi-Objective Pareto Evaluation

1. Total Shipping Cost ($C_{cost}$): Minimize money spent on shipping carriers.
2. Delivery Speed ($C_{speed}$): Minimize maximum delivery time (P99 SLA).
3. Shipment Count ($C_{ship}$): Minimize splitting a single order into multiple packages.
4. Node Load Utilization ($C_{load}$): Prevent overloading a single warehouse.

COST_FIRST

SPEED_FIRST

BALANCED

LOAD_BALANCED

4. Architectural Code Blueprint

public class RAPIDAllocationEngine {

    public AllocationPlan solve(AllocationRequest request) {
        long startTime = System.nanoTime();

        // Phase 1: Constraint Propagation
        PropagationResult prop = propagateConstraints(request);
        if (prop.isInfeasible()) {
            return AllocationPlan.infeasible("Constraints violate all candidate combinations");
        }

        // Phase 2: Solver Selection
        List<CandidatePlan> candidatePlans;
        long remainingSpace = prop.calculateSearchSpaceSize();

        if (prop.isAllForced()) {
            candidatePlans = List.of(prop.toForcedPlan());
        } else if (remainingSpace <= 10_000) {
            candidatePlans = runBranchAndBound(prop);
        } else {
            candidatePlans = runGreedySetCover(prop);
        }

        // Phase 3: Pareto Frontier Evaluation
        List<CandidatePlan> paretoFront = ParetoEvaluator.filterDominated(candidatePlans);
        CandidatePlan selectedPlan = ParetoEvaluator.selectBest(paretoFront, request.getPolicy());

        long elapsedMs = (System.nanoTime() - startTime) / 1_000_000;
        return new AllocationPlan(selectedPlan, elapsedMs, paretoFront.size(), remainingSpace);
    }

    private PropagationResult propagateConstraints(AllocationRequest req) {
        Map<String, Set<String>> domains = req.getInitialDomains();

        // Node Consistency: Prune zero stock or SLA breaches
        for (String item : req.getItems()) {
            domains.get(item).removeIf(node -> 
                req.getStock(node, item) <= 0 || req.getDeliveryTimeMs(node, req.getDestination()) > req.getMaxSlaMs()
            );
        }

        // Forced Assignment Loop & AC-3 Arc Consistency
        boolean changed;
        do {
            changed = false;
            for (String item : req.getItems()) {
                Set<String> domain = domains.get(item);
                if (domain.size() == 1) {
                    String forcedNode = domain.iterator().next();
                    changed |= propagateCapacityLimits(forcedNode, domains, req);
                }
            }
        } while (changed);

        return new PropagationResult(domains);
    }
}

5. Production Integration Analysis Across My Apps

A. MetaPilot (WhatsApp Campaign Worker Allocator)

• Location:

  services/api/campaigns/services/allocation_engine.py

  &

  services/api/tests/engines/test_allocation_engine.py

• Use Case: Celery Campaign Batch Allocation.
• The Problem: Broadcast campaigns containing 100,000 recipients are broken into 100 batches. If all batches land on Worker 1 while Worker 2 and Worker 3 sit idle, campaign execution latency spikes dramatically.
• RAPID Solution:

  1. CampaignAllocator

     acts as Phase 1 constraint propagator, filtering out worker nodes whose CPU/memory load exceeds 85%.
  2. Runs Phase 2 greedy least-loaded allocation across active Celery worker nodes.
  3. Reduces worker load variance to $< 0.0015$, completing multi-batch distribution in 2.5 milliseconds.

B. Clodee POS (Multi-Location Retail Order Routing)

• Location:

  lib/algorithms/rapid/

  &

  docs/ALGORITHMS.md

• Use Case: Multi-Store Order Fulfillment Routing.
• The Problem: A customer places an online order for 4 retail items. Clodee must decide whether to ship from Store A (near customer, 3 items in stock), Store B (farther, all 4 items in stock), or split shipments between A and C.
• RAPID Solution:
  1. Clodee executes RAPID's Phase 1 AC-3 node consistency, eliminating stores without stock or unable to meet same-day delivery SLAs.
  2. Phase 3 Pareto evaluation balances shipping expense ($C_{cost}$) vs shipment splitting ($C_{ship}$).

C. Cartera (Fintech Treasury Liquidity Allocation)

• Location:

  services/wallet-service/src/main/java/com/cartera/wallet/rapid/RapidAllocationEngine.java

  &

  AllocationController.java

• Use Case: Multi-Bank & Card Processor Liquidity Allocation.
• The Problem: High-volume card payouts must be routed across 5 banking gateway nodes (Stripe, Plaid, Adyen, Banking Partner A, Banking Partner B). Each processor has daily transaction caps, processing fees, and latency SLAs.
• RAPID Solution:
  1. Cartera's

     RapidAllocationEngine

     treats liquidity pools as candidate nodes $W$ and payout chunks as items $X$.
  2. RAPID calculates optimal payout routing plans under 12ms, adhering strictly to banking partner daily liquidity limits and minimizing fee tariffs.

6. Empirical Performance Benchmarks

Benchmark Results

7. Lessons Learned & Production Engineering Trade-offs

1. Propagation Is Cheap, Search Is Expensive: Spending 2ms running AC-3 constraint propagation to eliminate 95% of candidate search space saves 500ms of exponential search time in Phase 2.
2. Pareto Frontiers Avoid Arbitrary Weights: Instead of inventing arbitrary magic formulas like $\text{Score} = 0.4 \cdot \text{Cost} + 0.6 \cdot \text{Speed}$, constructing a true Pareto-optimal front allows business operators to dynamically select strategy policies at runtime.
3. Adaptive Solver Fallbacks Ensure Reliability: Having Branch & Bound for exact small-space solving and Greedy Set Cover for large-space fallback guarantees that RAPID never times out, regardless of input problem scale.