Clark-Scarf

425. Clark-Scarf

The foundational result for stochastic multi-echelon inventory in serial systems (Clark & Scarf 1960). Shows that the multi-echelon problem decomposes into independent single-echelon problems — one per stage, each solved as a newsvendor-like base-stock problem with an induced penalty cost.

425.1. Setup: serial system

Stages numbered $1$ (most upstream) to $𝑁$ (most downstream = retailer). Customer demand $𝐷$ hits stage $𝑁$ only. Each stage:

Holds inventory $𝐼_{𝑖}$
Receives shipments from upstream stage $𝑖 - 1$ with lead time $𝐿_{𝑖}$
Ships to downstream stage $𝑖 + 1$
Stage $𝑁$ also faces backorder cost $𝑏$ per unit per period

Holding cost rates: $ℎ_{𝑖}$ at stage $𝑖$ (assume $ℎ_{1} < ℎ_{2} < \dots < ℎ_{𝑁}$ — inventory is more expensive downstream where it carries more added value).

425.2. Echelon stock

Define echelon stock at stage $𝑖$ :

𝐸_{𝑖} = 𝐼_{𝑖} + \sum_{𝑗 = 𝑖 + 1}^{𝑁} 𝐼_{𝑗} + in-transit to 𝑗 > 𝑖

— what’s at stage $𝑖$ plus everything below it. Holding cost on echelon stock is incremental:

ℎ_{𝑖}^{𝐸} = ℎ_{𝑖} - ℎ_{𝑖 - 1}

(with $ℎ_{0} = 0$ ). This is the marginal holding cost as inventory moves from stage $𝑖 - 1$ to stage $𝑖$ .

425.3. Optimal policy: echelon base-stock

The optimal policy is echelon base-stock: at each review, stage $𝑖$ orders to bring its echelon stock up to a target $𝑆_{𝑖}^{*}$ .

The Clark-Scarf decomposition shows that $𝑆_{𝑖}^{*}$ at each stage solves a single-stage newsvendor problem with:

Demand: lead-time demand $𝐷_{𝐿_{𝑖}}$ from the most upstream (stage 1) feeding through
Underage cost: an induced penalty ${\hat{𝑏}}_{𝑖}$ that propagates upstream
Overage cost: $ℎ_{𝑖}^{𝐸}$ (incremental echelon holding cost)

425.4. Induced penalty

The recursion (downstream → upstream):

{\hat{𝑏}}_{𝑁} = 𝑏 (retailer faces real backorder cost)

{\hat{𝑏}}_{𝑖 - 1} = 𝐸 [{(𝐷_{𝐿_{𝑖}} - shortage at stage 𝑖)}^{+}] \cdot {\hat{𝑏}}_{𝑖} + ℎ_{𝑖}^{𝐸} \cdot ...

Formally: each stage’s penalty depends on the optimal cost-to-go from downstream — a backward DP. The decomposition magic is that, despite this coupling, the form of each stage’s optimal policy is base-stock with parameters depending only on local data + the induced penalty.

425.5. Worked sketch (2-stage)

Stages: warehouse (1) → retailer (2). $𝐿_{1}, 𝐿_{2}$ lead times. $ℎ_{1}, ℎ_{2} = ℎ_{1}^{𝐸} + ℎ_{2}^{𝐸}$ . Backorder cost $𝑏$ at retailer.

Retailer (stage 2): classical newsvendor with critical ratio $\frac{𝑏}{𝑏 + ℎ_{2}^{𝐸}}$ . Solve for $𝑆_{2}^{*}$ .

Warehouse (stage 1): newsvendor with critical ratio $\frac{{\hat{𝑏}}_{1}}{{\hat{𝑏}}_{1} + ℎ_{1}^{𝐸}}$ where ${\hat{𝑏}}_{1}$ is the expected cost the warehouse imposes on the retailer when warehouse stockouts cause retailer delays.

425.6. Penalty-function recursion

For this construction, index stages $1$ = downstream (demand-facing) to $𝑛$ = upstream (vendor) — the reverse of the setup above.

Consider a serial system with $𝑛$ stages, where stage $1$ faces stochastic customer demand and each is replenished from stage $𝑗 + 1$ with deterministic lead time $𝐿_{𝑗}$ :

Solve stages $1 \to 2 \to 𝑛$ . Each stage $𝑗$ does three things:

receives the penalty function from below
solves its own newsvendor balance
produces a new penalty function to pass up

Base case (stage 1). No stage below it, so $𝐺_{0} = 0$ . Stage 1′s expected cost as a function of its echelon level $𝑦$ :

𝐶_{1} (𝑦) = ℎ_{1} 𝔼 [{(𝑦 - 𝐷_{𝐿_{1}})}^{+}] + 𝑝 𝔼 [{(𝐷_{𝐿_{1}} - 𝑦)}^{+}]

where $𝐷_{𝐿_{1}}$ is demand over the lead-time window. This is convex; its minimizer is the fractile:

𝑆_{1} = 𝐹_{𝐿_{1}}^{- 1} (\frac{𝑝}{𝑝 + ℎ_{1}})

Inductive step (stage $𝑗$ ). Stage $𝑗$ has received $𝐺_{𝑗 - 1}$ from below. Its cost combines its own echelon holding with the penalty it inflicts downstream when it can’t fully supply:

𝐶_{𝑗} (𝑦) = ℎ_{𝑗} 𝔼 [{(𝑦 - 𝐷_{𝐿_{𝑗}})}^{+}] + 𝔼 [𝐺_{𝑗 - 1} (𝑦 - 𝐷_{𝐿_{𝑗}})]

Minimize over $𝑦$ to get $𝑆_{𝑗} = arg {min}_{𝑦} 𝐶_{𝑗} (𝑦)$ .

Produce the penalty to pass up. The clamp-and-floor operation:

𝐺_{𝑗} (𝑥) = 𝐶_{𝑗} (min (𝑥, 𝑆_{𝑗})) - 𝐶_{𝑗} (𝑆_{𝑗})

Zero when $𝑥 \geq 𝑆_{𝑗}$ (stage $𝑗$ isn’t constrained), positive and rising as $𝑥$ drops below $𝑆_{𝑗}$ . Hand $𝐺_{𝑗}$ to stage $𝑗 + 1$ .

Example: 3-stage serial system

Stage 1. Window $𝐿_{1} + 1 = 2$ , fractile $\frac{27}{27 + 3} = 0.9$ , $𝑧 = 1.282$ :

𝑆_{1} = 10 (2) + 1.282 \cdot 2 \sqrt{2} = 20 + 2.63 \approx 23.63

Stage 2. Window $𝐿_{2} + 1 = 2$ , fractile $\frac{27}{27 + 3 + 2} = \frac{27}{32} = 0.844$ , $𝑧 = 1.011$ :

𝑆_{2} = 20 + 1.011 \cdot 2 \sqrt{2} = 20 + 2.86 \approx 22.86

Stage 3. Window $𝐿_{3} + 1 = 3$ , fractile $\frac{27}{27 + 6} = \frac{27}{33} = 0.818$ , $𝑧 = 0.908$ :

𝑆_{3} = 10 (3) + 0.908 \cdot 2 \sqrt{3} = 30 + 3.25 \approx 33.15

The local stock held at each stage is the echelon-difference: $𝑆_{3} - 𝑆_{2}$ at stage 3, $𝑆_{2} - 𝑆_{1}$ at stage 2, $𝑆_{1}$ at stage 1.

The fractile formula $𝑝 / (𝑝 + \sum_{𝑖 < 𝑗} ℎ_{𝑖})$ with window $𝐿_{𝑗} + 1$ is the exact stage-1 newsvendor and a standard approximation upstream. The exact Clark-Scarf $𝑆_{2}, 𝑆_{3}$ come from minimizing $𝐶_{𝑗} (𝑦) = ℎ_{𝑗} 𝔼 [{(𝑦 - 𝐷_{𝐿_{𝑗}})}^{+}] + 𝔼 [𝐺_{𝑗 - 1} (𝑦 - 𝐷_{𝐿_{𝑗}})]$ numerically, since $𝐺_{𝑗 - 1}$ isn’t a clean newsvendor cost.

# pip install stockpyl
from stockpyl.ssm_serial import optimize_base_stock_levels

# Nodes indexed 1=downstream(demand-facing) ... 3=upstream(vendor-facing)
S_star, C_star = optimize_base_stock_levels(
    num_nodes=3,
    echelon_holding_cost=[3, 2, 1],   # h_1, h_2, h_3
    stockout_cost=27,                 # p, charged at downstream node
    lead_time=[1, 1, 2],              # L_1, L_2, L_3 (into each stage)
    demand_mean=10,
    demand_standard_deviation=2,
)
print(S_star)   # exact echelon base-stock levels
print(C_star)   # optimal expected cost

425.7. Why echelon stocks decouple the problem

If stage $𝑖$ ’s order pulls from infinite supply (or upstream is always available), each stage is independent. Real life: upstream isn’t always available. The induced penalty charges upstream for the downstream cost of its stockouts — capturing the coupling exactly.

425.8. Limitations

Serial systems only: pure chains, no branching
Stationary demand: i.i.d. demand each period
Costly to compute for many stages and long horizons

For general networks, see Graves-Willems guaranteed-service.

425.9. See also

Multi-Echelon — overview
Graves-Willems — alternative for general networks
Base Stock Policy
Newsvendor