Slot Assignment Optimization with Solvers

A greedy slotting pass places SKUs one at a time, and every placement it commits narrows the choices left for everything after it. Assign your fastest mover to the single best golden-zone bin and the second-fastest inherits a worse one, the third worse still — the errors compound down the velocity ranking until the tail of the catalog is slotted into whatever bins the greedy front-runners left behind. The fix is to stop deciding SKU-by-SKU and instead solve for all placements at once as a single optimization problem. This guide is the optimization core of the Location Assignment & ABC Classification Algorithms system: it formulates slot assignment as a mathematical program — a min-cost matching or mixed-integer linear program — rather than a greedy sweep, and shows when the exact solve is worth it and when a heuristic is the right call.

The thesis is that assignment is a global objective, not a sequence of local ones. Greedy answers “what is the best bin for this SKU right now”; the solver answers “what set of SKU-to-bin placements minimizes total expected travel across the whole catalog.” Those are different questions, and at facility scale they give materially different answers.

The Assignment Problem, Formally

Slot assignment is a bipartite matching: on one side the SKUs to be placed, on the other the available bins, and an edge cost for every SKU-bin pair equal to the expected travel that placement generates. Minimize the total cost of a matching in which every SKU gets exactly one bin and no bin is double-booked, and you have the optimal layout for that cost model.

The cost on edge (i, j) — placing SKU i in bin j — is the SKU’s pick frequency multiplied by the travel cost of reaching bin j from the pick tour’s reference point:

cost(i, j) = velocity_i × travel_cost_j

That single product is the whole reason velocity drives placement: a high-velocity SKU multiplies any distance heavily, so the optimizer pushes it toward low-travel_cost bins, while a slow SKU can absorb a distant bin cheaply. The travel cost per bin is exactly the output of Travel-Distance & Pick-Path Cost Modeling, and the velocity weight is the tier score from ABC Classification Tuning.

Two formulations sit on top of that cost matrix:

• Linear assignment (min-cost bipartite matching). When each SKU takes exactly one bin and each bin holds one SKU, the problem is the classic assignment problem, solvable exactly in polynomial time by the Hungarian algorithm — scipy.optimize.linear_sum_assignment. No integer variables, no branch-and-bound; it returns the provably optimal matching in milliseconds for thousands of rows.
• MILP (mixed-integer linear program). The moment placement carries side constraints that a pure matching cannot express — a bin holding multiple small SKUs up to a capacity, hazard segregation, affinity co-location bonuses, forbidden pairings — you add binary decision variables x[i,j] ∈ {0,1} and linear constraints, and hand it to a MILP solver such as PuLP’s CBC backend. More expressive, but NP-hard in general.

The engineering decision is which formulation your constraints actually require, and that is a scale-and-constraint trade-off, not a preference.

Input Data Requirements

The solver consumes three joined inputs: the SKUs to place with their velocity weights, the candidate bins with their travel costs, and the feasibility mask that says which pairings are even legal. Every SKU must carry a velocity score and every bin a travel cost; a missing weight collapses the objective and a missing travel cost makes the whole column meaningless.

from __future__ import annotations

from dataclasses import dataclass


@dataclass(frozen=True)
class SlotSKU:
    """A SKU awaiting placement, carrying its velocity weight and footprint."""
    sku_id: str
    velocity: float
    weight: float
    cube: float
    hazard_code: str | None = None


@dataclass(frozen=True)
class SlotBin:
    """A candidate bin, carrying its travel cost and physical capacity."""
    bin_id: str
    travel_cost: float
    max_weight: float
    max_cube: float
    reserved_for_hazard: str | None = None

The precondition that silently breaks solves is an infeasible mask: if every bin capable of holding a heavy SKU is already reserved, that row has no legal column and linear_sum_assignment will refuse the whole problem. Validate that each SKU has at least one feasible bin before building the matrix.

Step-by-Step Implementation

The pipeline runs in three passes: build the velocity-weighted cost matrix with infeasible pairs masked to a prohibitive cost, solve it, then decode and validate the assignment. Each pass is a pure function.

1. Build the Cost Matrix

The matrix is SKUs × bins, each cell the velocity-weighted travel cost. Feasibility — capacity, hazard segregation, and any affinity rule — is folded in by setting infeasible cells to a large sentinel cost so the optimizer never chooses them. This keeps the constraint logic out of the solver and in a single readable pass, and it reuses the same feasibility rules as Weight & Volume Constraint Modeling.

import logging

import numpy as np

logger = logging.getLogger("slotting.solver")

INFEASIBLE = 1e12  # sentinel cost that keeps a pair out of any optimal matching


def is_feasible(sku: SlotSKU, bin_: SlotBin) -> bool:
    """Capacity and hazard segregation gate for one SKU-bin pair."""
    if sku.weight > bin_.max_weight or sku.cube > bin_.max_cube:
        return False
    if sku.hazard_code and bin_.reserved_for_hazard != sku.hazard_code:
        return False
    return True


def build_cost_matrix(skus: list[SlotSKU], bins: list[SlotBin]) -> np.ndarray:
    """Velocity-weighted travel cost per SKU-bin pair; infeasible pairs masked out."""
    cost = np.full((len(skus), len(bins)), INFEASIBLE, dtype=float)
    for i, sku in enumerate(skus):
        for j, bin_ in enumerate(bins):
            if is_feasible(sku, bin_):
                cost[i, j] = sku.velocity * bin_.travel_cost
    feasible_cells = int((cost < INFEASIBLE).sum())
    logger.info("Cost matrix %dx%d built; %d feasible cells",
                len(skus), len(bins), feasible_cells)
    return cost

2. Solve With scipy linear_sum_assignment

For the pure one-SKU-one-bin case the Hungarian algorithm is the whole solve. scipy.optimize.linear_sum_assignment returns the row and column indices of the optimal matching; because the matrix may be rectangular (more bins than SKUs is normal), it matches every SKU to a distinct bin at minimum total cost. A matched pair whose cost is the INFEASIBLE sentinel signals that the problem was over-constrained and the SKU could not be legally placed — never a real assignment.

import logging

import numpy as np
from scipy.optimize import linear_sum_assignment

logger = logging.getLogger("slotting.solver")


def solve_assignment(cost: np.ndarray) -> list[tuple[int, int]]:
    """Return optimal (sku_idx, bin_idx) pairs via the Hungarian algorithm."""
    row_idx, col_idx = linear_sum_assignment(cost)
    pairs = list(zip(row_idx.tolist(), col_idx.tolist()))
    total = float(cost[row_idx, col_idx].sum())
    infeasible = [(i, j) for i, j in pairs if cost[i, j] >= INFEASIBLE]
    if infeasible:
        logger.error("%d SKUs matched only to infeasible bins", len(infeasible))
    logger.info("Solved assignment: %d pairs, total weighted cost %.1f",
                len(pairs), total)
    return pairs

3. Decode and Validate

The raw index pairs are translated back to SKU and bin ids, infeasible matches are dropped to a fallback queue rather than committed, and the committed set is checked for the invariants a valid layout must hold. These committed slots are the input the pick-path optimization layer optimizes against.

import logging
from dataclasses import dataclass

logger = logging.getLogger("slotting.solver")


@dataclass(frozen=True)
class Assignment:
    sku_id: str
    bin_id: str | None
    weighted_cost: float
    status: str  # COMMITTED | UNPLACED


def decode_assignment(pairs: list[tuple[int, int]], cost: np.ndarray,
                      skus: list[SlotSKU], bins: list[SlotBin]) -> list[Assignment]:
    """Translate solver indices to committed slots; route infeasible matches to fallback."""
    out: list[Assignment] = []
    for i, j in pairs:
        c = float(cost[i, j])
        if c >= INFEASIBLE:
            out.append(Assignment(skus[i].sku_id, None, c, "UNPLACED"))
            logger.warning("SKU %s unplaced: no feasible bin", skus[i].sku_id)
        else:
            out.append(Assignment(skus[i].sku_id, bins[j].bin_id, c, "COMMITTED"))
    committed = [a for a in out if a.status == "COMMITTED"]
    assert len({a.bin_id for a in committed}) == len(committed), "bin double-booked"
    logger.info("Committed %d/%d SKUs", len(committed), len(out))
    return out

When constraints exceed what a matching can express — a bin that legally holds several small SKUs, an affinity bonus for co-locating a family — the linear solve is replaced by a MILP. The full velocity-weighted MILP formulation, with binary x[i,j] variables and capacity constraints in PuLP, is worked end to end in How to Solve Slot Assignment with Linear Programming.

Tuning & Calibration

The solver has few knobs — its behaviour is set by the cost model feeding it — but the ones it has matter. The largest is the choice of method, which is a scale decision. The INFEASIBLE sentinel must be large enough to dominate any real cost sum but small enough to avoid float overflow; 1e12 against real costs in the hundreds is a safe gap. For MILP, the optimality gap and time limit trade solution quality against wall-clock.

# slot_solver.yaml — one profile per facility
solver:
  method: "hungarian"        # hungarian (exact matching) | milp (capacity/affinity) | greedy
  infeasible_cost: 1.0e12    # sentinel keeping illegal pairs out of the optimum
  affinity_bonus: 0.85       # cost multiplier (<1) applied to co-located family pairs
milp:
  time_limit_s: 30           # wall-clock cap before returning best-found
  optimality_gap: 0.01       # accept a solution within 1% of the bound
scale:
  max_exact_skus: 5000       # above this, switch hungarian -> local-search heuristic

# Equivalent Python config dict consumed by the solver
SLOT_SOLVER = {
    "solver": {"method": "hungarian", "infeasible_cost": 1.0e12, "affinity_bonus": 0.85},
    "milp": {"time_limit_s": 30, "optimality_gap": 0.01},
    "scale": {"max_exact_skus": 5000},
}

The method and max_exact_skus levers encode the core trade-off. The Hungarian algorithm is O(n³); at a few thousand SKUs it is instant, but a full 250,000-SKU re-slot in one matrix is neither necessary nor tractable. In practice you partition — solve exactly within a zone or a velocity tier where the matrix is small, and use a local-search heuristic across the coarse partition. affinity_bonus below 1.0 discounts the cost of placing a SKU near its co-picked family, biasing the optimum toward co-location without hard-constraining it.

Validation & Testing

Never commit a solved layout without asserting its invariants: the matching is one-to-one, no bin is double-booked, no committed pair is infeasible, and the exact solve is at least as good as the greedy baseline it replaces. The following pytest checks encode all four.

import numpy as np


def _fixture() -> tuple[list[SlotSKU], list[SlotBin]]:
    skus = [SlotSKU(f"S{i}", velocity=v, weight=5, cube=0.1)
            for i, v in enumerate([90.0, 40.0, 12.0])]
    bins = [SlotBin(f"B{j}", travel_cost=t, max_weight=50, max_cube=1.0)
            for j, t in enumerate([5.0, 12.0, 30.0])]
    return skus, bins


def test_matching_is_one_to_one() -> None:
    skus, bins = _fixture()
    result = decode_assignment(solve_assignment(build_cost_matrix(skus, bins)),
                               build_cost_matrix(skus, bins), skus, bins)
    bin_ids = [a.bin_id for a in result if a.status == "COMMITTED"]
    assert len(bin_ids) == len(set(bin_ids))


def test_exact_beats_greedy() -> None:
    skus, bins = _fixture()
    cost = build_cost_matrix(skus, bins)
    exact = float(cost[tuple(zip(*solve_assignment(cost)))].sum())
    # Greedy: place each SKU (velocity-desc) in its cheapest remaining bin.
    used: set[int] = set()
    greedy = 0.0
    for i in np.argsort([-s.velocity for s in skus]):
        j = min((c for c in range(len(bins)) if c not in used),
                key=lambda c: cost[i, c])
        used.add(j)
        greedy += cost[i, j]
    assert exact <= greedy, f"exact {exact} worse than greedy {greedy}"

A healthy run confirms the exact objective never exceeds the greedy baseline — on small symmetric matrices they coincide, but on realistic asymmetric cost matrices the exact solve consistently wins, which is the entire justification for running a solver.

Integration Points

Slot assignment optimization is the hinge between classification and pick-path optimization, so it consumes several upstream signals and produces the one output the downstream pick-path system depends on:

• Velocity tiers. The objective weight on every SKU is the tuned velocity score from ABC Classification Tuning; a mis-tiered catalog optimizes confidently toward the wrong layout.
• Physical feasibility. The mask that keeps illegal pairs out of the matrix is exactly the capacity and crush logic in Weight & Volume Constraint Modeling; the solver enforces those rules by construction, never as an afterthought.
• Affinity. The affinity_bonus that discounts co-location cost is derived from the lift map in Family & Affinity Grouping, turning a soft co-pick preference into a term in the objective.
• Travel cost. Every bin’s travel_cost is produced by Travel-Distance & Pick-Path Cost Modeling; the committed slots this solver emits then become the fixed layout that the pick-path optimization layer sequences and routes against.
• Move economics. A newly optimal layout is only worth executing if the travel savings beat the relocation labor, which is the break-even gate in Threshold Optimization for Re-slotting.

Failure Modes & Edge Cases

• Silent infeasibility. An over-constrained mask leaves a SKU with no legal bin, and linear_sum_assignment either matches it to the sentinel or raises. Remediation: assert every row has at least one sub-sentinel cell before solving, and route genuinely unplaceable SKUs to bulk reserve with a replenishment task.
• Cost-scale distortion. Mixing raw travel costs in the hundreds with an INFEASIBLE sentinel too small (say 1e6) lets a few real placements sum past the sentinel and corrupt the optimum. Remediation: keep the sentinel many orders of magnitude above any feasible cost sum, and normalize velocity and travel to comparable ranges.
• Solving the whole facility in one matrix. A single 250,000-square cost matrix is 60 GB of doubles and O(n³) to solve — neither feasible nor needed. Remediation: partition by zone or tier, solve each block exactly, and stitch with a coarse heuristic; set max_exact_skus as the switch.
• Treating the matching as capacity-aware. Pure linear_sum_assignment gives each bin exactly one SKU; if a bin legally holds several small items you are under-using space. Remediation: move to the MILP formulation with per-bin capacity constraints when bins are shared.
• Optimizing a layout you will not execute. The solver will happily relocate half the catalog for a 2% objective gain. Remediation: gate the committed set behind the re-slotting break-even and a per-cycle relocation cap so the paper optimum becomes floor labor only when it pays back.

FAQ

When is the Hungarian algorithm enough and when do I need a MILP?

Use linear_sum_assignment whenever placement is genuinely one-SKU-one-bin and your constraints (capacity, hazard) can be expressed as an infeasibility mask on the cost matrix. It is exact, polynomial, and needs no solver license. Reach for a MILP the moment a bin can hold multiple SKUs up to a capacity, or you need affinity co-location as a soft objective term, or you have forbidden-pair and count constraints — those require binary variables and linear constraints that a pure matching cannot represent.

How large a problem can I solve exactly?

The Hungarian algorithm is O(n³) in time and O(n²) in memory, so a few thousand SKUs solve in well under a second, but tens of thousands in a single dense matrix become memory-bound. The practical answer is that you almost never solve the whole facility at once — you partition by zone or velocity tier, where each block is small enough for an exact solve, and coordinate the blocks with a lighter heuristic. Set the exact-solve ceiling in config and fall back to local search above it.

Why weight the cost by velocity instead of just minimizing travel?

Because the goal is minimizing aggregate picker travel over time, and a SKU’s contribution to that total is its per-pick travel times how often it is picked. A bin 30 feet out costs almost nothing for a SKU picked twice a month but is ruinous for one picked 400 times a day. Multiplying travel by velocity makes the optimizer spend its cheap bins on the SKUs that walk them most, which is exactly the layout that minimizes total travel — not the one that minimizes travel per placement in isolation.

How does the solver avoid assigning a SKU to an unsafe bin?

Feasibility is enforced before the solve, not after. Every capacity or hazard violation sets that SKU-bin cell to a prohibitive sentinel cost, so any optimal matching provably avoids it — the constraint is baked into the objective. A matched pair that still carries the sentinel cost means the problem was over-constrained and the SKU genuinely has no legal bin, which the decode step routes to fallback rather than committing.

Related

• How to Solve Slot Assignment with Linear Programming — the worked scipy/PuLP implementation on a velocity-weighted cost matrix.
• ABC Classification Tuning — the velocity scores that weight the assignment objective.
• Weight & Volume Constraint Modeling — the capacity and crush rules that build the feasibility mask.
• Family & Affinity Grouping — the co-pick lift behind the affinity cost bonus.
• Travel-Distance & Pick-Path Cost Modeling — the per-bin travel costs the objective minimizes, and the system that consumes the committed slots.
• Location Assignment & ABC Classification Algorithms — the parent architecture this optimization core sits inside.