Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Sect. 10.1.1: the Clark-Scarf decomposition — echelon order-up-to levels (S1,S2)(S_1, S_2)(S1​,S2​) minimize the expected period cost of the two-level serial system

Proved
InventoryControl.clark_scarf_two_level

by naimengye · Sep 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

clark-scarfinventory-controlmulti-echelonoperations-researchoptimizationprobability

The Clark-Scarf decomposition for a two-level serial system, the central result of Chapter 10.

Installation 1 faces normally distributed period demand (mean μ\muμ, standard deviation σ>0\sigma > 0σ>0, independent across periods) and replenishes from installation 2, which replenishes from an outside supplier with infinite supply; lead-times are L1L_1L1​ and L2L_2L2​ periods, demand is backordered, and costs are echelon holding costs e1,e2≥0e_1, e_2 \ge 0e1​,e2​≥0 and a shortage cost b1>0b_1 > 0b1​>0 per unit and period, with h1=e1+e2h_1 = e_1 + e_2h1​=e1​+e2​ and h2=e2h_2 = e_2h2​=e2​. In an arbitrary period the total expected cost is determined by the echelon position y2y_2y2​ chosen at installation 2 and the realized position y1y_1y1​ at installation 1 a lead-time later, which is subject to y1≤y2−D(L2)y_1 \le y_2 - D(L_2)y1​≤y2​−D(L2​) and may depend on D(L2)D(L_2)D(L2​); after the reallocation (10.4)-(10.5) it is E[C~2(y2)+C~1(y1)]\mathbb{E}\big[\tilde C_2(y_2) + \tilde C_1(y_1)\big]E[C~2​(y2​)+C~1​(y1​)].

Let S1S_1S1​ be the newsboy level of Eq. (10.8), Φ((S1−μ1′′)/σ1′′)=(e2+b1)/(h1+b1)\Phi\big((S_1 - \mu_1'')/\sigma_1''\big) = (e_2 + b_1)/(h_1 + b_1)Φ((S1​−μ1′′​)/σ1′′​)=(e2​+b1​)/(h1​+b1​), and let S2S_2S2​ minimize the total cost C^2\hat C_2C^2​ of Eq. (10.9). Then:

  1. for every y2y_2y2​ and every allocation rule u↦a(u)u \mapsto a(u)u↦a(u) with a(u)≤y2−ua(u) \le y_2 - ua(u)≤y2​−u (and finite expected cost),
C^2(S2)  ≤  E[C~2(y2)+C~1(a(D(L2)))];\hat C_2(S_2) \;\le\; \mathbb{E}\big[\tilde C_2(y_2) + \tilde C_1\big(a(D(L_2))\big)\big];C^2​(S2​)≤E[C~2​(y2​)+C~1​(a(D(L2​)))];
  1. the echelon order-up-to policy (S1,S2)(S_1, S_2)(S1​,S2​), which sets y2=S2y_2 = S_2y2​=S2​ and y1=min⁡{S1,S2−D(L2)}y_1 = \min\{S_1, S_2 - D(L_2)\}y1​=min{S1​,S2​−D(L2​)}, attains C^2(S2)\hat C_2(S_2)C^2​(S2​).

In words: the optimal policy is an echelon-stock order-up-to policy at both installations, S1S_1S1​ is found from a newsboy problem that does not involve installation 2 at all, and S2S_2S2​ is then found by minimizing a convex function of one variable in which installation 2's inability to deliver appears as an induced shortage cost. This is the decomposition Clark and Scarf discovered, and the origin of the echelon-inventory measure. In Example 10.1 (L1=L2=5L_1 = L_2 = 5L1​=L2​=5, μ=10\mu = 10μ=10, σ=5\sigma = 5σ=5, e1=0.5e_1 = 0.5e1​=0.5, e2=1e_2 = 1e2​=1, b1=10b_1 = 10b1​=10) it gives S1=81.0S_1 = 81.0S1​=81.0 and S2=129.7S_2 = 129.7S2​=129.7 with total cost 39.439.439.4.

Formalization Note The theorem is the per-period decomposition the book derives; it does not model the infinite-horizon dynamics, in which the same stationary policy is applied in every period and is feasible because the outside supplier has infinite supply (the book's "obvious" step). Allocation rules are arbitrary functions of the realized lead-time demand with an explicit integrability hypothesis, since a rule with infinite expected cost is not a competitor. S1S_1S1​ and S2S_2S2​ are characterized rather than constructed; their existence for e1>0e_1 > 0e1​>0 is established by the other items of this mission.

Preamble
import Definitions.Def_InventoryControl_clarkScarf
Formal statement
namespace InventoryControl

theorem clark_scarf_two_level (e1 e2 b1 mu sigma : ℝ) (he1 : 0 ≤ e1) (he2 : 0 ≤ e2) (hb : 0 < b1)
    (hs : 0 < sigma) (L1 L2 : ℕ) (S1 : ℝ)
    (hS1 : ProbabilityTheory.cdf (ProbabilityTheory.gaussianReal 0 1)
      ((S1 - (L1 + 1) * mu) / (Real.sqrt (L1 + 1) * sigma)) = (e2 + b1) / (e1 + e2 + b1))
    (S2 : ℝ) (hS2 : ∀ y2 : ℝ, csTotalCost e1 e2 b1 mu sigma L1 L2 S1 S2
      ≤ csTotalCost e1 e2 b1 mu sigma L1 L2 S1 y2) :
    (∀ y2 : ℝ, ∀ a : ℝ → ℝ, (∀ u, a u ≤ y2 - u) →
        MeasureTheory.Integrable (fun u => csStage1Cost e1 e2 b1 mu sigma L1 (a u))
          (csDemand mu sigma L2) →
        csTotalCost e1 e2 b1 mu sigma L1 L2 S1 S2
          ≤ ∫ u, (csStage2Cost e2 mu L2 y2 + csStage1Cost e1 e2 b1 mu sigma L1 (a u))
              ∂(csDemand mu sigma L2))
      ∧ csTotalCost e1 e2 b1 mu sigma L1 L2 S1 S2
          = ∫ u, (csStage2Cost e2 mu L2 S2 + csStage1Cost e1 e2 b1 mu sigma L1 (min S1 (S2 - u)))
              ∂(csDemand mu sigma L2) := by sorry

end InventoryControl
Source
Sven Axsäter, Inventory Control, 3rd ed., Springer 2015, DOI 10.1007/978-3-319-15729-0, pp. 193-196, Sect. 10.1.1 'Serial System', Eq. (10.1)-(10.9) and the conclusions on p. 196: 'this optimal policy can be realized if we apply an (echelon stock) order-up-to-S policy with Se1 = y-hat*1' and 'it is optimal to apply an echelon stock order-up-to-S policy with Se2 = y*2'; after Clark and Scarf (1960) and Federgruen and Zipkin (1984)
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me