Lot Sizing

Lot Sizing

You are an expert in dynamic lot-sizing models for production planning. This skill covers the uncapacitated single-item problem (ULS) solved exactly by the Wagner-Whitin dynamic program, the multi-item capacitated lot-sizing problem (CLSP) with setup costs and setup times, strong reformulations (facility-location, (l,S) valid inequalities), the big-bucket vs small-bucket model families, and fix-and-optimize matheuristics for large instances. Use the framework below to classify the variant, pick the right formulation strength, and deliver a validated production plan with a defensible optimality gap.

Initial Assessment

Establish these facts before formulating anything:

• Capacity. Is per-period production capacity binding? Uncapacitated single-item problems are polynomially solvable; capacity makes even the single-item case NP-hard.
• Number of items and periods. N items × T periods sets the binary count (N·T setup variables). N·T ≤ a few thousand is comfortable MIP territory; beyond that plan for matheuristics.
• Bucket size. Are periods long (weeks/months, many setups per period — big bucket) or short (shifts/hours, at most one or two products per period — small bucket)? This decides the model family before any code is written.
• Setup structure. Setup costs only, or also setup times that consume capacity? Setup times change the complexity class of the feasibility question. Ask about setup carryover across periods and sequence-dependent setups.
• Cost structure. Time-varying or constant setup/holding/production costs? Constant unit production cost can be dropped from the objective (total production equals total demand when backlog is forbidden).
• Backlogging and lost sales. Hard demand satisfaction, backlog at a cost, or lost sales? This changes the flow-balance constraints and the validity of zero-inventory-ordering arguments.
• Lot-size restrictions. Minimum lot sizes, batch multiples, or all-or-nothing production invalidate the Wagner-Whitin structure and need extra integer variables.
• Demand certainty. Deterministic forecast, or stochastic demand needing safety stock / scenario models? A deterministic model re-solved in a rolling horizon is the common practical pattern.
• Horizon usage. One-shot plan or rolling horizon? Rolling horizons need end-of-horizon inventory rules and frozen periods to control nervousness.
• Quality requirement and time budget. Proven optimality (MIP with strong formulation), small gap in minutes (matheuristic), or instant answer (DP / construction heuristic)?
• Solver availability. Gurobi license, or open-source only? The DP and the metaheuristic below need only numpy; the MIP sections need a MILP solver.
• Data format. Demand matrix orientation (items × periods), units of capacity (hours vs pieces), and whether quantities must be integral (usually production quantities may stay continuous).

Problem Variants and Formulations

Notation

Items $i = 1,\dots,N$; periods $t = 1,\dots,T$. Data: demand $d{it} \ge 0$, setup cost $fi$, holding cost $hi$ per unit per period, processing time $ai$ capacity units per unit, setup time $sti$, capacity $Ct$. Variables: production $x{it} \ge 0$, end-of-period inventory $s{it} \ge 0$ (with $s{i0} = 0$), setup indicator $y{it} \in \{0,1\}$.

ULS — uncapacitated single-item lot sizing

$$ \min \sum{t=1}^{T} \big( ft\, yt + ht\, st \big) \quad \text{s.t.} \quad s{t-1} + xt = dt + st,\qquad xt \le \Big(\sum{u=t}^{T} du\Big)\, yt,\qquad xt, st \ge 0,\; yt \in \{0,1\}. $$

Zero-inventory ordering (ZIO). Wagner & Whitin (1958) proved an optimal solution exists with $s{t-1}\, xt = 0$ for all $t$: you never produce while still holding stock. So each demand $d_u$ is produced entirely in one period $t \le u$, and the horizon splits into regeneration intervals. This yields an $O(T^2)$ dynamic program; refinements reach $O(T \log T)$ (Federgruen & Tzur 1991; Wagelmans, van Hoesel & Kolen 1992; Aggarwal & Park 1993). ULS is the textbook entry point of dynamic-programming for planning problems.

CLSP — capacitated multi-item, big bucket

$$ \min \sum{i=1}^{N}\sum{t=1}^{T} \big( fi\, y{it} + hi\, s{it} \big) $$

$$ s{i,t-1} + x{it} = d{it} + s{it} \;\;\forall i,t; \qquad \sum{i=1}^{N} \big( ai\, x{it} + sti\, y{it} \big) \le Ct \;\;\forall t; \qquad x{it} \le M{it}\, y_{it} \;\;\forall i,t, $$

with the tightest valid big-M $M{it} = \min\big( \sum{u \ge t} d{iu},\; (Ct - sti)/ai \big)$.

Complexity. Single-item lot sizing with general time-varying capacities is NP-hard (Florian, Lenstra & Rinnooy Kan 1980; Bitran & Yanasse 1982); with constant capacity and integer data it admits an $O(T^4)$ DP (Florian & Klein 1971). For the multi-item CLSP with positive setup times, even deciding feasibility is NP-complete (Maes, McClain & Van Wassenhove 1991) — that is why practical codes add overtime variables.

Big-bucket vs small-bucket model families

| Model | Bucket | Per-period structure | Sequencing | Key reference | |-------|--------|----------------------|------------|---------------| | CLSP | big | many items, one setup each | none inside period | Trigeiro, Thomas & McClain (1989) | | CLSPL | big | CLSP + setup carryover between periods | first/last item only | Suerie & Stadtler (2003) | | DLSP | small | ≤1 item, all-or-nothing at full capacity | implicit | Fleischmann (1990) | | CSLP | small | ≤1 item, any quantity up to capacity | implicit | Karmarkar & Schrage (1985) | | PLSP | small | ≤1 setup change, so up to 2 items | implicit | Drexl & Haase (1995) | | GLSP | hybrid | macro-period capacity, micro-period sequence | full | Fleischmann & Meyr (1997) |

Use big-bucket models when periods are weeks or months and shop-floor sequencing is decided downstream. Switch to small-bucket or GLSP models when setups carry over between short periods or are sequence-dependent — there, lot sizing and scheduling cannot be separated.

Strong reformulations

The big-M linking constraint makes the standard LP relaxation notoriously weak. Two classical repairs, both from the single-item polyhedron, also tighten every item's substructure inside the CLSP (Pochet & Wolsey 2006, Production Planning by Mixed Integer Programming):

Facility-location reformulation (Krarup & Bilde 1977). Disaggregate production: $w{itu}$ = quantity produced in period $t$ to serve demand $d{iu}$, $t \le u$:

$$ \min \sum{i,t} fi\, y{it} + \sum{i,\, t \le u} hi (u-t)\, w{itu} \quad \text{s.t.} \quad \sum{t \le u} w{itu} = d{iu} \;\;\forall i,u; \qquad w{itu} \le d{iu}\, y{it}. $$

For uncapacitated single-item instances, its LP relaxation has an integral optimal $y$ — it describes the convex hull. Cost: $O(N T^2 / 2)$ variables.

(l,S) valid inequalities (Barany, Van Roy & Wolsey 1984). For each $l \in \{1,\dots,T\}$ and each $S \subseteq \{1,\dots,l\}$:

$$ \sum{t \in S} xt \;\le\; sl + \sum{t \in S} d{t,l}\; yt, \qquad d{t,l} = \sum{u=t}^{l} d_u . $$

Together with the trivial inequalities these give the full convex hull of ULS solutions. There are exponentially many, but exact separation is $O(T^2)$ per item: given an LP point $(x^, y^, s^)$, the most violated set is $S^ = \{ t \le l : x^t > d{t,l}\, y^_t \}$. So the small standard model plus a cut loop reaches the same bound as the large FL model.

Method selection

| Situation | Method | |-----------|--------| | Single item, no capacity | Wagner-Whitin DP, exact in $O(T^2)$ | | Single item, constant capacity, integer data | Florian-Klein DP, $O(T^4)$ | | CLSP, up to a few thousand setup binaries | MIP with FL reformulation or (l,S) cut loop | | Large CLSP, setup times, overtime | fix-and-optimize / relax-and-fix (see matheuristics) | | Setup carryover or sequence-dependent setups | CLSPL / GLSP models, metaheuristics | | Stochastic demand | static-dynamic strategies, two-stage scenario models |

Instance Generation and Validation

Build these two functions first: every later section reuses the instance container and reports through the independent validator. The generator follows the design of the classic Trigeiro, Thomas & McClain (1989) CLSP test bed: setup costs are derived from a target time-between-orders (TBO) via the EOQ relation $TBO = \sqrt{2 f / (h \bar d)}$, and capacity is set from a target utilization.

from dataclasses import dataclass

import numpy as np

@dataclass(frozen=True)
class ClspInstance:
    """Multi-item big-bucket CLSP data. Shapes: demand (N, T); item arrays (N,); capacity (T,)."""
    demand: np.ndarray        # d[i, t] >= 0
    setup_cost: np.ndarray    # f[i]
    holding_cost: np.ndarray  # h[i] per unit per period
    prod_time: np.ndarray     # a[i] capacity units per produced unit
    setup_time: np.ndarray    # st[i] capacity units per setup
    capacity: np.ndarray      # C[t]

def generate_clsp_instance(n_items: int, n_periods: int, seed: int,
                           tbo: float = 2.0, utilization: float = 0.85,
                           demand_cv: float = 0.35) -> ClspInstance:
    """Trigeiro-style CLSP generator: TBO sets setup costs, utilization sets capacity tightness."""
    rng = np.random.default_rng(seed)
    mean_demand = rng.uniform(50.0, 150.0, n_items)
    demand = rng.normal(mean_demand[:, None], demand_cv * mean_demand[:, None],
                        (n_items, n_periods))
    demand = np.clip(np.rint(demand), 0.0, None)
    holding_cost = rng.uniform(0.5, 1.5, n_items)
    setup_cost = 0.5 * tbo ** 2 * holding_cost * demand.mean(axis=1)  # EOQ-derived
    prod_time = np.ones(n_items)
    setup_time = rng.uniform(10.0, 50.0, n_items)
    mean_load = (prod_time[:, None] * demand).sum(axis=0).mean()
    capacity_value = (mean_load + setup_time.sum() / tbo) / utilization
    capacity = np.full(n_periods, capacity_value)
    return ClspInstance(demand, setup_cost, holding_cost, prod_time, setup_time, capacity)

inst = generate_clsp_instance(n_items=4, n_periods=8, seed=42)
print(inst.demand.shape, float(inst.demand.sum()), round(float(inst.capacity[0]), 1))
# Expected: (4, 8) 3870.0 646.4 — identical numbers on every rerun with seed 42.

Raise utilization toward 1.0 and tbo above 3 to create hard instances; setup-time-heavy, tightly capacitated instances are the hardest in the Trigeiro set. The validator below recomputes everything from raw data — never trust the model's own bookkeeping when reporting results:

import numpy as np

def validate_clsp_solution(inst: ClspInstance, x: np.ndarray, y: np.ndarray,
                           tol: float = 1e-6) -> tuple[bool, float, list[str]]:
    """Independent feasibility check and objective recomputation; no solver objects involved."""
    violations: list[str] = []
    inventory = np.cumsum(x - inst.demand, axis=1)
    if (x  tol) & (y  tol) & (y  inst.capacity + tol).any():
        t = int(np.argwhere(load > inst.capacity + tol)[0][0])
        violations.append(f"capacity exceeded in period {t}")
    objective = float((inst.setup_cost[:, None] * y).sum()
                      + (inst.holding_cost[:, None] * np.clip(inventory, 0.0, None)).sum())
    return (not violations, objective, violations)

inst = generate_clsp_instance(n_items=4, n_periods=8, seed=42)
x_lfl = inst.demand.astype(float)              # lot-for-lot plan
y_lfl = (inst.demand > 0).astype(float)
ok, obj, viol = validate_clsp_solution(inst, x_lfl, y_lfl)
print(ok, round(obj, 1), viol)
# Expected: False 6802.5 ['capacity exceeded in period 2'] — lot-for-lot pays a setup
# for every item in every period, and the setup hours overload the tight periods.

Wagner-Whitin Dynamic Program

The exact ULS solver. State: $F(t)$ = minimum cost of satisfying demands $1..t$, with $F(0) = 0$. By ZIO, the last regeneration interval is produced entirely in some period $j$:

$$ F(t) = \min{1 \le j \le t} \Big\{ F(j-1) + fj + \sum{u=j}^{t} \Big( \sum{v=j}^{u-1} hv \Big) du \Big\}. $$

Prefix sums make each candidate cost $O(1)$, so the whole DP is $O(T^2)$ — instant for any practical horizon. The implementation supports time-varying setup and holding costs and skips the setup charge on zero-demand intervals:

import numpy as np

def wagner_whitin(demand: np.ndarray, setup_cost: np.ndarray,
                  holding_cost: np.ndarray) -> tuple[float, list[int]]:
    """O(T^2) DP for single-item uncapacitated lot sizing (Wagner & Whitin 1958).

    Returns (optimal cost, 0-indexed setup periods). Supports time-varying f_t, h_t.
    """
    T = len(demand)
    cum_h = np.concatenate(([0.0], np.cumsum(holding_cost)))        # sum h[0..t-1]
    cum_d = np.concatenate(([0.0], np.cumsum(demand)))
    cum_hd = np.concatenate(([0.0], np.cumsum(cum_h[:T] * demand)))
    F = np.full(T + 1, np.inf)
    F[0] = 0.0
    pred = np.zeros(T + 1, dtype=int)
    for t in range(T):
        j = np.arange(t + 1)
        interval_demand = cum_d[t + 1] - cum_d[j]
        produce_cost = setup_cost[j] + (cum_hd[t + 1] - cum_hd[j]) - cum_h[j] * interval_demand
        produce_cost = np.where(interval_demand > 0, produce_cost, 0.0)  # no demand, no setup
        total = F[j] + produce_cost
        k = int(np.argmin(total))
        F[t + 1] = total[k]
        pred[t + 1] = k
    setups, t = [], T
    while t > 0:
        j = pred[t]
        if cum_d[t] - cum_d[j] > 0:
            setups.append(int(j))
        t = j
    return float(F[T]), setups[::-1]

cost, setups = wagner_whitin(np.array([10.0, 20.0, 30.0]),
                             np.array([40.0, 40.0, 40.0]),
                             np.array([1.0, 1.0, 1.0]))
print(cost, setups)
# Expected: 100.0 [0, 2] — produce 30 units in period 0 (holding d_2 one period costs 20)
# and 30 units in period 2; all four ZIO plans cost 120/110/100/120.

Use Wagner-Whitin three ways inside capacitated work: as the exact solver when capacity never binds, as a per-item lower-bounding and seeding device (solve each item alone, ignore capacity), and as the subproblem inside Lagrangian or column-generation schemes for the CLSP. The $O(T \log T)$ refinements matter only when ULS is called millions of times inside such loops. For deeper recursion-design guidance see dynamic-programming.

Exact MIP Models in gurobipy

Standard CLSP with constraint-builder functions

Each constraint family lives in its own builder so it can be unit-tested and reused by the reformulation and the matheuristic. Note model.update() at the end of the builder: gurobipy's lazy updates otherwise leave relax() and getVars() looking at an empty model.

import gurobipy as gp
import numpy as np
from gurobipy import GRB

def add_flow_balance_constraints(model: gp.Model, v: dict, data: ClspInstance) -> None:
    """Inventory balance s[i,t-1] + x[i,t] == d[i,t] + s[i,t], with s[i,-1] = 0."""
    N, T = data.demand.shape
    x, s = v["x"], v["s"]
    for i in range(N):
        for t in range(T):
            prev = s[i, t - 1] if t > 0 else 0.0
            model.addConstr(prev + x[i, t] == data.demand[i, t] + s[i, t],
                            name=f"flow[{i},{t}]")

def add_setup_linking_constraints(model: gp.Model, v: dict, data: ClspInstance) -> None:
    """x[i,t]  None:
    """Production plus setup time within period capacity: sum_i a_i x[i,t] + st_i y[i,t]  tuple[gp.Model, dict]:
    """Standard inventory-and-setup CLSP MIP."""
    N, T = data.demand.shape
    model = gp.Model("clsp")
    model.Params.OutputFlag = 0
    v = {"x": model.addVars(N, T, lb=0.0, name="x"),
         "s": model.addVars(N, T, lb=0.0, name="s"),
         "y": model.addVars(N, T, vtype=GRB.BINARY, name="y")}
    add_flow_balance_constraints(model, v, data)
    add_setup_linking_constraints(model, v, data)
    add_capacity_constraints(model, v, data)
    model.setObjective(
        gp.quicksum(data.setup_cost[i] * v["y"][i, t] + data.holding_cost[i] * v["s

…

## Source & license

This open-source skill is cataloged on AgentStack and links to its original source — we do not rehost the code.

- **Author:** [hajibabaie](https://github.com/hajibabaie)
- **Source:** [hajibabaie/combinatorial-optimization-skills](https://github.com/hajibabaie/combinatorial-optimization-skills)
- **License:** MIT

Install and usage instructions live in the source repository linked above.