Slotting Architecture · 10 min read

How to Solve Slot Assignment with Linear Programming

You have a few hundred SKUs to place, a set of open bins each with a known travel cost, and a velocity score per SKU. You could sweep the SKUs in velocity order and drop each into its cheapest remaining bin — the greedy approach — but that lets early placements poison the choices left for the tail of the catalog. This page shows the exact alternative: build a velocity-weighted cost matrix and solve the whole placement at once with scipy.optimize.linear_sum_assignment, the Hungarian algorithm, which returns the provably minimum-cost matching in one call. It is the worked implementation behind Slot Assignment Optimization with Solvers, part of the wider Location Assignment & ABC Classification Algorithms system.

Three-stage linear-programming slot assignment pipeline A left-to-right pipeline of three stages connected by arrows. Stage one, build cost matrix, takes SKU velocities and bin travel costs and forms an n by m grid whose cells are velocity times travel, with infeasible cells set to a large sentinel. Stage two, solve, feeds that matrix to scipy linear_sum_assignment and returns row and column index pairs for the minimum-cost matching. Stage three, decode and validate, translates the index pairs into committed SKU-to-bin slots, drops any pair still carrying the sentinel cost to an unplaced fallback queue, and asserts no bin is double-booked. A short note under stage two reads Hungarian algorithm, order n cubed, exact. Exact slot assignment via the Hungarian algorithm 1 · Build cost matrix cell = velocity × travel 4501080∞ 2004801200 60144360 2 · Solve linear_sum_assignment returns (row, col) pairs Hungarian algorithm O(n³) · exact optimum 3 · Decode + validate idx → committed slots sentinel → unplaced queue assert no bin double-booked to pick-path system

Prerequisites

Confirm each before running this against a live catalog:

  • Python 3.10+ — the code uses X | None unions, list[...] generics, and dataclass.
  • scipy 1.7+ and numpy 1.21+ — scipy.optimize.linear_sum_assignment is the exact solver; NumPy holds the cost matrix. Swap in PuLP’s CBC backend only if you need per-bin capacity or affinity constraints a pure matching cannot express.
  • A velocity score per SKU — the tuned tier weight from ABC Classification Tuning, strictly positive.
  • A travel cost per bin — the expected walk cost to each bin, produced by Travel-Distance & Pick-Path Cost Modeling.
  • A feasibility rule — the capacity and hazard checks from Weight & Volume Constraint Modeling, used to mask illegal pairs before the solve.
  • At least as many bins as SKUs — the matching needs a distinct bin per SKU; pad with high-cost dummy bins if the pool is tight.

Configuration Block

Every tunable lives in one externalized profile. The two levers that decide behaviour are infeasible_cost (the sentinel that keeps illegal pairs out of the optimum) and max_travel (a cap that flags a placement as too far to accept even when feasible).

# lp_assignment.yaml
solver:
  infeasible_cost: 1.0e12    # sentinel cost for masked (illegal) SKU-bin pairs
  max_travel: 45.0           # travel cost above which a placement is flagged, not committed
  pad_dummy_bins: true       # add high-cost dummy bins when bins < skus
scaling:
  velocity_floor: 0.1        # clamp zero/negative velocity to avoid a degenerate objective
  normalize: false           # divide costs by their max to keep numbers small (optional)
# Equivalent Python config dict consumed by the solver
LP_ASSIGNMENT = {
    "solver": {"infeasible_cost": 1.0e12, "max_travel": 45.0, "pad_dummy_bins": True},
    "scaling": {"velocity_floor": 0.1, "normalize": False},
}

Implementation

The function builds the velocity-weighted matrix, masks infeasible pairs to the sentinel, solves with the Hungarian algorithm, and decodes the result into committed slots — dropping any pair that resolves to the sentinel into an unplaced queue rather than committing an illegal bin.

from __future__ import annotations

import logging
from dataclasses import dataclass

import numpy as np
from scipy.optimize import linear_sum_assignment

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


@dataclass(frozen=True)
class SKU:
    sku_id: str
    velocity: float
    weight: float
    cube: float


@dataclass(frozen=True)
class Bin:
    bin_id: str
    travel_cost: float
    max_weight: float
    max_cube: float


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


def solve_slot_assignment(skus: list[SKU], bins: list[Bin], cfg: dict) -> list[Slot]:
    """Exactly assign SKUs to bins minimizing total velocity-weighted travel."""
    sentinel = cfg["solver"]["infeasible_cost"]
    floor = cfg["scaling"]["velocity_floor"]

    n, m = len(skus), len(bins)
    if m < n and cfg["solver"]["pad_dummy_bins"]:
        raise ValueError(f"{n} SKUs but only {m} bins; pad the bin pool before solving")

    # Build the cost matrix: velocity-weighted travel, infeasible pairs masked out.
    cost = np.full((n, m), sentinel, dtype=float)
    for i, sku in enumerate(skus):
        v = max(sku.velocity, floor)
        for j, b in enumerate(bins):
            if sku.weight <= b.max_weight and sku.cube <= b.max_cube:
                cost[i, j] = v * b.travel_cost

    if not (cost < sentinel).any(axis=1).all():
        starved = [skus[i].sku_id for i in range(n) if not (cost[i] < sentinel).any()]
        logger.error("infeasible: SKUs with no legal bin: %s", starved)

    # Solve: Hungarian algorithm returns the minimum-cost one-to-one matching.
    rows, cols = linear_sum_assignment(cost)
    total = float(cost[rows, cols][cost[rows, cols] < sentinel].sum())
    logger.info("solved %d SKUs, feasible weighted cost %.1f", n, total)

    # Decode: commit feasible matches, route sentinel matches to the unplaced queue.
    slots: list[Slot] = []
    for i, j in zip(rows.tolist(), cols.tolist()):
        c = float(cost[i, j])
        if c >= sentinel:
            slots.append(Slot(skus[i].sku_id, None, c, "UNPLACED"))
        else:
            slots.append(Slot(skus[i].sku_id, bins[j].bin_id, c, "COMMITTED"))

    committed = [s.bin_id for s in slots if s.status == "COMMITTED"]
    assert len(committed) == len(set(committed)), "bin double-booked — matrix malformed"
    return slots

Step-by-Step Walkthrough

  1. Guard the bin count. A one-to-one matching needs at least as many bins as SKUs. If m < n the function raises rather than silently leaving SKUs unmatched; pad the pool with high-cost dummy bins upstream so every SKU has somewhere to land.
  2. Build the cost matrix. Each cell cost[i, j] is velocity_i × travel_cost_j, with velocity clamped to velocity_floor so a zero or negative score cannot flatten the objective. Any pair failing the weight/cube check is left at infeasible_cost, which keeps it out of every optimal matching.
  3. Detect starvation early. Before solving, the code checks every row has at least one sub-sentinel cell. A SKU whose entire row is the sentinel has no legal bin, and logging it here turns a silent over-constraint into a visible one.
  4. Solve exactly. linear_sum_assignment(cost) runs the Hungarian algorithm and returns paired row and column indices for the minimum-cost matching. This is the whole solve — no iteration, no greedy tie-breaks — and it is provably optimal for the given matrix.
  5. Decode and validate. Index pairs become SKU-to-bin slots. A pair whose cost is still the sentinel is marked UNPLACED and routed to fallback rather than committed. The final assertion confirms no bin appears twice, catching a malformed matrix before the layout reaches the WMS.

Verification

Assert the invariants and confirm the exact solve is never worse than the greedy baseline it replaces. This runs standalone — no WMS, no live data.

import logging

logging.basicConfig(level=logging.INFO)

skus = [SKU("S1", 90.0, 5, 0.1), SKU("S2", 40.0, 5, 0.1), SKU("S3", 12.0, 5, 0.1)]
bins = [Bin("B1", 5.0, 50, 1.0), Bin("B2", 12.0, 50, 1.0), Bin("B3", 30.0, 50, 1.0)]

slots = solve_slot_assignment(skus, bins, LP_ASSIGNMENT)
placement = {s.sku_id: s.bin_id for s in slots}

assert placement == {"S1": "B1", "S2": "B2", "S3": "B3"}   # fastest SKU -> nearest bin
assert all(s.status == "COMMITTED" for s in slots)
assert len({s.bin_id for s in slots}) == len(slots)        # no bin reused
print("assignment:", placement)
print("total weighted cost:", round(sum(s.cost for s in slots), 1))

Sample expected output:

INFO:slotting.lp:solved 3 SKUs, feasible weighted cost 1290.0
assignment: {'S1': 'B1', 'S2': 'B2', 'S3': 'B3'}
total weighted cost: 1290.0

The solver places the velocity-90 SKU in the travel-5 bin and pushes the velocity-12 SKU out to the travel-30 bin — the layout that minimizes the weighted sum (450 + 480 + 360 = 1290), exactly what the velocity weighting is designed to produce.

Common Pitfalls

  • Cost matrix scaling. If your infeasible_cost sentinel is only modestly larger than a real cost (say 1e4 against costs near 3000), a handful of legitimate placements can sum past it and the optimizer treats a legal layout as worse than an illegal one. Keep the sentinel many orders of magnitude above any feasible cost — 1e12 against costs in the thousands is safe.
  • Infeasibility that fails silently. When every bin able to hold a heavy SKU is masked out, that SKU’s whole row is the sentinel and linear_sum_assignment still returns a match — to an infeasible bin. Always check for all-sentinel rows before solving and route those SKUs to fallback, never to the bin the solver nominally paired them with.
  • Matrix size. The Hungarian algorithm is O(n³) time and O(n²) memory; a 20,000-square matrix is 3 GB of doubles and seconds to solve, and a full-facility matrix is neither. Partition by zone or velocity tier so each solve is a few thousand rows, and coordinate the blocks with a coarse heuristic — the exact solve is for the sub-problem, not the whole building.
  • Rectangular pools mishandled. More bins than SKUs is normal and fine — the solver matches every SKU to a distinct bin and ignores the surplus. More SKUs than bins is not: the extra SKUs go unmatched with no error unless you guard the count, so check m >= n and pad with dummy bins before you call the solver.