Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

OWMR model: dynamics, period cost, C(π)C(\pi)C(π), and OPT\mathrm{OPT}OPT

Definition
owmr_network_model

by Ming Hu · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmsinventoryinventory-theoryoperations-researchstochastic-control

An OWMR network with nnn retailers consists of a supplier lead time L0∈NL_0\in\mathbb NL0​∈N, retailer lead times Li∈NL_i\in\mathbb NLi​∈N, a probability measure μ\muμ on [0,∞)n[0,\infty)^n[0,∞)n (the common law of the demand vectors Dt=(D1,t,…,Dn,t)D_t=(D_{1,t},\dots,D_{n,t})Dt​=(D1,t​,…,Dn,t​), which are i.i.d. over periods t=0,1,2,…t=0,1,2,\dotst=0,1,2,…, with possibly dependent components), setup costs K0K_0K0​ (supplier) and KiK_iKi​ (retailers), holding rates hhh (warehouse) and HiH_iHi​ (retailers), and a common backlog penalty ppp. The standing assumptions are 0<EDi,t<∞0<\mathbb E D_{i,t}<\infty0<EDi,t​<∞ for every iii, K0,Ki≥0K_0,K_i\ge0K0​,Ki​≥0, and h,Hi,p>0h,H_i,p>0h,Hi​,p>0. Write Kmax⁡=max⁡iKiK_{\max}=\max_iK_iKmax​=maxi​Ki​.

In period ttt, scheduled shipments arrive; the warehouse places a supplier order q0,tq_{0,t}q0,t​, which arrives in period t+L0t+L_0t+L0​; it dispatches qi,tq_{i,t}qi,t​ to retailer iii, which arrives in period t+Lit+L_it+Li​; then demand occurs. A valid initial state prescribes warehouse stock W−1≥0W_{-1}\ge0W−1​≥0, retailer net inventories Ii,−1I_{i,-1}Ii,−1​, and nonnegative pipeline quantities arriving at the warehouse in periods t<L0t<L_0t<L0​ and at retailer iii in periods t<Lit<L_it<Li​. Inventories evolve by

Wt=Wt−1+q0,t−L0−∑iqi,t,Ii,t=Ii,t−1+qi,t−Li−Di,t,W_t=W_{t-1}+q_{0,t-L_0}-\sum_iq_{i,t},\qquad I_{i,t}=I_{i,t-1}+q_{i,t-L_i}-D_{i,t},Wt​=Wt−1​+q0,t−L0​​−i∑​qi,t​,Ii,t​=Ii,t−1​+qi,t−Li​​−Di,t​,

and the period cost (1) is

ct=K01{q0,t>0}+∑iKi1{qi,t>0}+hWt+∑i(HiIi,t++pIi,t−).c_t=K_0\mathbf 1_{\{q_{0,t}>0\}}+\sum_iK_i\mathbf 1_{\{q_{i,t}>0\}}+hW_t+\sum_i\big(H_iI_{i,t}^++pI_{i,t}^-\big).ct​=K0​1{q0,t​>0}​+i∑​Ki​1{qi,t​>0}​+hWt​+i∑​(Hi​Ii,t+​+pIi,t−​).

A policy chooses q0,tq_{0,t}q0,t​ and qi,tq_{i,t}qi,t​ from the demand history and auxiliary randomness uuu, drawn from a probability law ν\nuν independent of all demands. It is nonanticipative if the decisions of period ttt depend on demands only through D0,…,Dt−1D_0,\dots,D_{t-1}D0​,…,Dt−1​, and feasible if orders and dispatches are nonnegative and ∑iqi,t≤Wt−1+q0,t−L0\sum_iq_{i,t}\le W_{t-1}+q_{0,t-L_0}∑i​qi,t​≤Wt−1​+q0,t−L0​​. The long-run average cost and the optimal cost (2) are

C(π)=lim sup⁡T→∞1T Eπ∑t=0T−1ct,OPT=inf⁡π nonanticipative and feasibleC(π).C(\pi)=\limsup_{T\to\infty}\frac1T\,\mathbb E_\pi\sum_{t=0}^{T-1}c_t,\qquad\mathrm{OPT}=\inf_{\pi\ \text{nonanticipative and feasible}}C(\pi).C(π)=T→∞limsup​T1​Eπ​t=0∑T−1​ct​,OPT=π nonanticipative and feasibleinf​C(π).

Every guarantee of the mission compares the cost of a constructed policy with OPT\mathrm{OPT}OPT.

Formalization Note Demand vectors have type Fin n → ℝ≥0. The expected cost of periods 0,…,T−10,\dots,T-10,…,T−1 is the lower Lebesgue integral of ∑t<Tmax⁡(ct,0)\sum_{t<T}\max(c_t,0)∑t<T​max(ct​,0), as an extended nonnegative real, under ν⊗μ⊗T\nu\otimes\mu^{\otimes T}ν⊗μ⊗T, with the history D0,…,DT−1D_0,\dots,D_{T-1}D0​,…,DT−1​ extended by zero vectors (the costs of these periods involve no later demand); for feasible policies ct≥0c_t\ge0ct​≥0. Hence C(π),OPT∈[0,∞]C(\pi),\mathrm{OPT}\in[0,\infty]C(π),OPT∈[0,∞]. In OPT\mathrm{OPT}OPT the infimum ranges over every auxiliary probability space (U,ν)(U,\nu)(U,ν) with U : Type and every measurable, nonanticipative policy that is feasible for every uuu and every demand sequence. A deterministic policy is a policy on the one-point space.

Definition code
import Mathlib.MeasureTheory.Constructions.Pi
import Mathlib.MeasureTheory.Integral.Bochner.Basic
import Mathlib.MeasureTheory.Measure.Lebesgue.Basic
import Mathlib.Order.LiminfLimsup

/-!
# The one-warehouse multi-retailer (OWMR) model

Source: M. Hu, "A 5/2 Guarantee for Echelon Stock (s,S) Policies in One-Warehouse
Multi-Retailer Systems", Section 3 (Model and Main Results), equations (1) and (2).

A warehouse replenishes retailers `i : Fin n` from an outside supplier in discrete periods
`t = 0, 1, 2, …`. In each period: (1) shipments sent earlier arrive as scheduled; (2) the warehouse
may place a supplier order `q₀,t`; (3) it may dispatch `q_{i,t}` to each retailer from the stock
available in that period; (4) demand `D_{i,t}` occurs and is met from retailer stock or backlogged;
holding and backlog costs are charged on the resulting inventories. A supplier order placed in
period `t` arrives in period `t + L₀` (in time for that period's dispatches) and a dispatch to
retailer `i` in period `t` arrives in period `t + L_i` (in time for that period's demand).

The demand vectors `D_t = (D_{1,t}, …, D_{n,t})` are i.i.d. over periods with law `μ`; the
components of one vector may be dependent.
-/

open MeasureTheory
open scoped ENNReal NNReal

noncomputable section

namespace OWMR

/-- A demand vector: one nonnegative demand per retailer. -/
abbrev DemandVec (n : ℕ) := Fin n → ℝ≥0

/-- Primitive data of an OWMR network with `n` retailers. -/
structure Network (n : ℕ) where
  /-- supplier lead time `L₀` -/
  L0 : ℕ
  /-- retailer lead times `L_i` -/
  L : Fin n → ℕ
  /-- common law of the i.i.d. per-period demand vectors `D_t` -/
  μ : Measure (DemandVec n)
  /-- `μ` is a probability measure -/
  isProb : IsProbabilityMeasure μ
  /-- supplier setup cost `K₀` (per positive supplier order) -/
  K0 : ℝ
  /-- retailer setup costs `K_i` (per positive dispatch to retailer `i`) -/
  K : Fin n → ℝ
  /-- warehouse holding cost rate `h` -/
  h : ℝ
  /-- retailer holding cost rates `H_i` -/
  H : Fin n → ℝ
  /-- common backlog penalty rate `p` -/
  p : ℝ

attribute [instance] Network.isProb

variable {n : ℕ}

/-- The standing assumptions of Section 3: `0 < 𝔼 D_{i,t} < ∞` for every retailer,
`K₀, K_i ≥ 0`, `h > 0`, `H_i > 0`, `p > 0`. (Nonnegativity of demand is built into
`DemandVec`; finiteness of the lead times is built into `ℕ`.) -/
structure Network.Standing (N : Network n) : Prop where
  mean_pos : ∀ i, 0 < ∫⁻ x, (x i : ℝ≥0∞) ∂N.μ
  mean_lt_top : ∀ i, ∫⁻ x, (x i : ℝ≥0∞) ∂N.μ < ∞
  K0_nonneg : 0 ≤ N.K0
  K_nonneg : ∀ i, 0 ≤ N.K i
  h_pos : 0 < N.h
  H_pos : ∀ i, 0 < N.H i
  p_pos : 0 < N.p

/-- `K_max = max_i K_i`. -/
def Network.Kmax (N : Network n) : ℝ := ⨆ i, N.K i

/-- A prescribed initial state: warehouse stock `W`, retailer net inventories `I_i`, and the
pipelines, indexed by arrival period: `supPipe t` arrives at the warehouse in period `t`
(only `t < L₀` is used) and `retPipe i t` arrives at retailer `i` in period `t` (only `t < L_i`
is used). -/
structure InitState (n : ℕ) where
  W : ℝ
  I : Fin n → ℝ
  supPipe : ℕ → ℝ
  retPipe : Fin n → ℕ → ℝ

/-- A valid initial state has nonnegative warehouse stock and nonnegative pipeline quantities. -/
def InitState.Valid (x : InitState n) : Prop :=
  0 ≤ x.W ∧ (∀ t, 0 ≤ x.supPipe t) ∧ ∀ i t, 0 ≤ x.retPipe i t

/-- A policy with auxiliary randomness `u : U`: the supplier order `q₀,t = order t u D` and the
dispatches `q_{i,t} = dispatch t u D i` in period `t`, as functions of `u` and of the whole demand
sequence `D = (D_s)_{s ∈ ℕ}`. Nonanticipativity is the separate predicate
`Policy.Nonanticipative`. -/
structure Policy (n : ℕ) (U : Type) where
  order : ℕ → U → (ℕ → DemandVec n) → ℝ
  dispatch : ℕ → U → (ℕ → DemandVec n) → Fin n → ℝ

namespace Policy

variable {U : Type}

/-- Period-`t` decisions depend on the demand sequence only through `D_0, …, D_{t-1}`. -/
def Nonanticipative (π : Policy n U) : Prop :=
  ∀ (t : ℕ) (u : U) (d d' : ℕ → DemandVec n), (∀ s < t, d s = d' s) →
    π.order t u d = π.order t u d' ∧ π.dispatch t u d = π.dispatch t u d'

/-- Measurability of every decision in `(u, D)`. -/
def IsMeasurable [MeasurableSpace U] (π : Policy n U) : Prop :=
  ∀ t : ℕ, Measurable (fun ω : U × (ℕ → DemandVec n) => π.order t ω.1 ω.2) ∧
    ∀ i, Measurable (fun ω : U × (ℕ → DemandVec n) => π.dispatch t ω.1 ω.2 i)

/-- Quantity arriving at the warehouse in period `t`. -/
def supArrival (N : Network n) (x : InitState n) (π : Policy n U) (u : U)
    (d : ℕ → DemandVec n) (t : ℕ) : ℝ :=
  if t < N.L0 then x.supPipe t else π.order (t - N.L0) u d

/-- Quantity arriving at retailer `i` in period `t`. -/
def retArrival (N : Network n) (x : InitState n) (π : Policy n U) (u : U)
    (d : ℕ → DemandVec n) (i : Fin n) (t : ℕ) : ℝ :=
  if t < N.L i then x.retPipe i t else π.dispatch (t - N.L i) u d i

/-- Warehouse stock `W_t` after the dispatches of period `t`:
`W_t = W_{t-1} + q_{0,t-L₀} - ∑_i q_{i,t}`. -/
def whStock (N : Network n) (x : InitState n) (π : Policy n U) (u : U)
    (d : ℕ → DemandVec n) (t : ℕ) : ℝ :=
  x.W + ∑ s ∈ Finset.range (t + 1), (supArrival N x π u d s - ∑ i, π.dispatch s u d i)

/-- Stock available for dispatch in period `t`: `W_{t-1}` plus the supplier arrival of
period `t`. -/
def whAvailable (N : Network n) (x : InitState n) (π : Policy n U) (u : U)
    (d : ℕ → DemandVec n) (t : ℕ) : ℝ :=
  x.W + ∑ s ∈ Finset.range t, (supArrival N x π u d s - ∑ i, π.dispatch s u d i)
    + supArrival N x π u d t

/-- Retailer net inventory `I_{i,t}` after the demand of period `t`:
`I_{i,t} = I_{i,t-1} + q_{i,t-L_i} - D_{i,t}`. -/
def netInv (N : Network n) (x : InitState n) (π : Policy n U) (u : U)
    (d : ℕ → DemandVec n) (i : Fin n) (t : ℕ) : ℝ :=
  x.I i + ∑ s ∈ Finset.range (t + 1), (retArrival N x π u d i s - (d s i : ℝ))

/-- The period cost (1):
`c_t = K₀ 1{q₀,t > 0} + ∑_i K_i 1{q_{i,t} > 0} + h W_t + ∑_i (H_i I_{i,t}⁺ + p I_{i,t}⁻)`. -/
def periodCost (N : Network n) (x : InitState n) (π : Policy n U) (u : U)
    (d : ℕ → DemandVec n) (t : ℕ) : ℝ :=
  N.K0 * (if 0 < π.order t u d then 1 else 0)
    + ∑ i, N.K i * (if 0 < π.dispatch t u d i then 1 else 0)
    + N.h * whStock N x π u d t
    + ∑ i, (N.H i * max (netInv N x π u d i t) 0 + N.p * max (-netInv N x π u d i t) 0)

/-- Feasibility: nonnegative orders and dispatches, and dispatches never exceeding the warehouse
stock available in that period (for every value of the auxiliary randomness and every demand
sequence). -/
def Feasible (N : Network n) (x : InitState n) (π : Policy n U) : Prop :=
  ∀ (u : U) (d : ℕ → DemandVec n) (t : ℕ), 0 ≤ π.order t u d ∧ (∀ i, 0 ≤ π.dispatch t u d i) ∧
    ∑ i, π.dispatch t u d i ≤ whAvailable N x π u d t

end Policy

/-- Extension of a finite history `z_0, …, z_{T-1}` to a sequence, by zeros after `T`. -/
def padHist {α : Type} [Zero α] (T : ℕ) (z : Fin T → α) : ℕ → α :=
  fun t => if ht : t < T then z ⟨t, ht⟩ else 0

/-- Expected total cost of periods `0, …, T-1`: the auxiliary randomness has law `ν`,
independent of the demands, and `D_0, …, D_{T-1}` are i.i.d. with law `μ`. (Costs of periods
before `T` only involve these demands.) -/
def expCost {U : Type} [MeasurableSpace U] (N : Network n) (x : InitState n) (π : Policy n U)
    (ν : Measure U) (T : ℕ) : ℝ≥0∞ :=
  ∫⁻ ω, ∑ t ∈ Finset.range T, ENNReal.ofReal (π.periodCost N x ω.1 (padHist T ω.2) t)
    ∂(ν.prod (Measure.pi fun _ : Fin T => N.μ))

/-- The long-run average cost (2): `C(π) = limsup_{T→∞} T⁻¹ 𝔼_π ∑_{t<T} c_t`. -/
def avgCost {U : Type} [MeasurableSpace U] (N : Network n) (x : InitState n) (π : Policy n U)
    (ν : Measure U) : ℝ≥0∞ :=
  Filter.limsup (fun T : ℕ => (T : ℝ≥0∞)⁻¹ * expCost N x π ν T) Filter.atTop

/-- The optimal cost (2): the infimum of `C(π)` over all nonanticipative, feasible
(measurable) policies, which may use auxiliary randomness independent of all demands. -/
def OPT (N : Network n) (x : InitState n) : ℝ≥0∞ :=
  ⨅ (U : Type) (_ : MeasurableSpace U) (ν : Measure U) (_ : IsProbabilityMeasure ν)
    (π : Policy n U) (_ : π.Nonanticipative ∧ π.IsMeasurable ∧ π.Feasible N x),
    avgCost N x π ν

/-- A deterministic policy: decisions are functions of the demand sequence only. -/
structure DetPolicy (n : ℕ) where
  order : ℕ → (ℕ → DemandVec n) → ℝ
  dispatch : ℕ → (ℕ → DemandVec n) → Fin n → ℝ

/-- A deterministic policy as a policy with trivial auxiliary randomness. -/
def DetPolicy.toPolicy (π : DetPolicy n) : Policy n Unit :=
  ⟨fun t _ d => π.order t d, fun t _ d => π.dispatch t d⟩

/-- `C(π)` for a deterministic policy. -/
def DetPolicy.avgCost (N : Network n) (x : InitState n) (π : DetPolicy n) : ℝ≥0∞ :=
  OWMR.avgCost N x π.toPolicy (Measure.dirac ())

end OWMR
Source
M. Hu, "A 5/2 Guarantee for Echelon Stock (s,S) Policies in One-Warehouse Multi-Retailer Systems", working paper (manuscript of November 2026), Section 3 (Model and Main Results), pp. 6-7, equations (1) and (2).
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Overview. The file uses only Mathlib and puts everything in a namespace OWMR. It defines four data records (Network, InitState, Policy, DetPolicy), several real-valued quantities computed from them period by period, and three predicates on policies. It then defines a finite-horizon integral expCost, its normalized upper limit avgCost, and a number OPT in [0,∞][0,\infty][0,∞]. OPT is an infimum of avgCost over policies that may depend on an auxiliary random point. Two more predicates (Network.Standing, InitState.Valid) and the number Network.Kmax are defined, but no other declaration in the file uses them.

Notation and conventions.

  • n∈Nn\in\mathbb{N}n∈N is an implicit parameter of every declaration, and n=0n=0n=0 is allowed. The code numbers coordinates {0,…,n−1}\{0,\dots,n-1\}{0,…,n−1}. Here they are relabelled [n]={1,…,n}[n]=\{1,\dots,n\}[n]={1,…,n}, so a subscript 000 always means one of the separate scalar fields L0 or K0, never a coordinate. The coordinate index is only ever used in sums, suprema and "for all" statements, so the relabelling changes nothing.
  • Periods are t∈N={0,1,2,… }t\in\mathbb{N}=\{0,1,2,\dots\}t∈N={0,1,2,…}, starting at 000. They are not relabelled.
  • R≥0\mathbb{R}_{\ge0}R≥0​ is the set of nonnegative reals. [0,∞][0,\infty][0,∞] is the set of extended nonnegative reals, in which Mathlib sets 0−1=∞0^{-1}=\infty0−1=∞ and ∞⋅0=0\infty\cdot0=0∞⋅0=0.
  • All σ\sigmaσ-algebras are Mathlib's defaults: Borel on R\mathbb{R}R and R≥0\mathbb{R}_{\ge0}R≥0​, and product σ\sigmaσ-algebras on finite products, on sequence spaces and on U×(⋅)U\times(\cdot)U×(⋅).

DemandVec

DemandVec n is R≥0n\mathbb{R}_{\ge0}^{n}R≥0n​: vectors ξ=(ξ1,…,ξn)\xi=(\xi_1,\dots,\xi_n)ξ=(ξ1​,…,ξn​) with nonnegative real entries, with the product of the Borel σ\sigmaσ-algebras. For n=0n=0n=0 it is a one-point space. Nonnegativity is part of the type, so every demand entry below is automatically ≥0\ge0≥0. A demand sequence is any d=(dt)t∈Nd=(d_t)_{t\in\mathbb{N}}d=(dt​)t∈N​ with dt∈R≥0nd_t\in\mathbb{R}^n_{\ge0}dt​∈R≥0n​, and dt,id_{t,i}dt,i​ is the iii-th entry of dtd_tdt​. The set (R≥0n)N(\mathbb{R}^n_{\ge0})^{\mathbb{N}}(R≥0n​)N of all demand sequences carries the product (cylinder) σ\sigmaσ-algebra.

Network

A network NNN (type Network n) is a record with exactly these fields:

  • natural numbers L0L_0L0​ and LiL_iLi​ for i∈[n]i\in[n]i∈[n] (any of them may be 000);
  • a measure μ\muμ on R≥0n\mathbb{R}^n_{\ge0}R≥0n​, with a proof that μ\muμ is a probability measure. The proof is registered as an instance, so later definitions that need it, such as the product measures μ⊗T\mu^{\otimes T}μ⊗T, find it automatically;
  • real numbers K0K_0K0​, hhh, ppp, and real numbers KiK_iKi​, HiH_iHi​ for i∈[n]i\in[n]i∈[n].

The record imposes nothing beyond μ\muμ having total mass 111. The reals may have any sign. μ\muμ need not have finite or positive means, and nothing is said about how the coordinates of ξ∼μ\xi\sim\muξ∼μ depend on each other. ppp is a single number shared by all iii, while KiK_iKi​, HiH_iHi​ and LiL_iLi​ may vary with iii. For n=0n=0n=0 the indexed families are empty, and μ\muμ must be the unit mass on the single point.

Network.Standing

Standing N holds if and only if all seven of the following hold:

  • for every i∈[n]i\in[n]i∈[n]:   0<∫ξi μ(dξ)  \;0<\int\xi_i\,\mu(d\xi)\;0<∫ξi​μ(dξ) and   ∫ξi μ(dξ)<∞\;\int\xi_i\,\mu(d\xi)<\infty∫ξi​μ(dξ)<∞;
  • K0≥0K_0\ge0K0​≥0, and Ki≥0K_i\ge0Ki​≥0 for every iii;
  • h>0h>0h>0, Hi>0H_i>0Hi​>0 for every iii, and p>0p>0p>0.

Each integral is the Lebesgue integral, valued in [0,∞][0,\infty][0,∞], of the nonnegative measurable coordinate map ξ↦ξi\xi\mapsto\xi_iξ↦ξi​. In other words it is the mean of coordinate iii under μ\muμ, and the first condition says this mean is finite and strictly positive (equivalently, coordinate iii is integrable and not μ\muμ-almost surely 000). Nothing is required of L0L_0L0​, of the LiL_iLi​, or of the joint law beyond these means of single coordinates. For n=0n=0n=0 the indexed conditions are vacuous, and Standing reduces to K0≥0K_0\ge0K0​≥0, h>0h>0h>0, p>0p>0p>0. No other declaration in the file uses Standing. In particular, OPT is defined for every network, whether or not Standing holds.

Network.Kmax

Kmax N =sup⁡i∈[n]Ki=\sup_{i\in[n]}K_i=supi∈[n]​Ki​, computed in R\mathbb{R}R. For n≥1n\ge1n≥1 it equals max⁡iKi\max_iK_imaxi​Ki​. For n=0n=0n=0 the family is empty, and Mathlib's supremum of an empty family of reals is the junk value 000 (not −∞-\infty−∞). Nothing else in the file uses it.

InitState and InitState.Valid

An initial state xxx (type InitState n) is a record of:

  • a real number WWW;
  • real numbers IiI_iIi​ for i∈[n]i\in[n]i∈[n];
  • a real sequence (φt)t∈N(\varphi_t)_{t\in\mathbb{N}}(φt​)t∈N​ (field supPipe);
  • for each i∈[n]i\in[n]i∈[n], a real sequence (ψi,t)t∈N(\psi_{i,t})_{t\in\mathbb{N}}(ψi,t​)t∈N​ (field retPipe).

All values are arbitrary reals, and the record does not refer to any network. The sequences are infinite whatever L0L_0L0​ and LiL_iLi​ are, but later definitions read only φt\varphi_tφt​ for t<L0t<L_0t<L0​ and ψi,t\psi_{i,t}ψi,t​ for t<Lit<L_it<Li​. All other entries affect nothing.

Valid x is the proposition

W≥0,φt≥0  ∀t∈N,ψi,t≥0  ∀i∈[n], ∀t∈N.W\ge0,\qquad\varphi_t\ge0\ \ \forall t\in\mathbb{N},\qquad\psi_{i,t}\ge0\ \ \forall i\in[n],\ \forall t\in\mathbb{N}.W≥0,φt​≥0  ∀t∈N,ψi,t​≥0  ∀i∈[n], ∀t∈N.

It puts no condition on the IiI_iIi​, which may be negative. It also constrains the entries that are never read. No other declaration uses it; in particular OPT does not assume it.

Policy

Let UUU be any type in Lean's lowest universe Type, with no structure assumed. A policy π\piπ (type Policy n U) is a pair of completely arbitrary functions

q: N×U×(R≥0n)N→R,y: N×U×(R≥0n)N×[n]→R,q:\ \mathbb{N}\times U\times(\mathbb{R}^n_{\ge0})^{\mathbb{N}}\to\mathbb{R},\qquad y:\ \mathbb{N}\times U\times(\mathbb{R}^n_{\ge0})^{\mathbb{N}}\times[n]\to\mathbb{R},q: N×U×(R≥0n​)N→R,y: N×U×(R≥0n​)N×[n]→R,

written qt(u,d)q_t(u,d)qt​(u,d) (field order) and yt,i(u,d)y_{t,i}(u,d)yt,i​(u,d) (field dispatch). For each period ttt, these values may depend on the point u∈Uu\in Uu∈U and on the whole demand sequence ddd, including the entries dsd_sds​ with s≥ts\ge ts≥t. They may be negative, and nothing is assumed about measurability. Such restrictions come only from the separate predicates Nonanticipative, IsMeasurable and Feasible.

Policy.Nonanticipative

π\piπ is nonanticipative if and only if, for every t∈Nt\in\mathbb{N}t∈N, every u∈Uu\in Uu∈U and every two demand sequences d,d′d,d'd,d′ with ds=ds′d_s=d'_sds​=ds′​ for all s<ts<ts<t,

qt(u,d)=qt(u,d′)andyt,i(u,d)=yt,i(u,d′)  for all i∈[n].q_t(u,d)=q_t(u,d')\qquad\text{and}\qquad y_{t,i}(u,d)=y_{t,i}(u,d')\ \text{ for all } i\in[n].qt​(u,d)=qt​(u,d′)andyt,i​(u,d)=yt,i​(u,d′)  for all i∈[n].

So for each fixed uuu, the period-ttt values depend on ddd only through (d0,…,dt−1)(d_0,\dots,d_{t-1})(d0​,…,dt−1​). The same-period vector dtd_tdt​ is excluded, and the dependence on uuu is unrestricted. At t=0t=0t=0 the premise holds for every pair d,d′d,d'd,d′, so q0(u,d)q_0(u,d)q0​(u,d) and y0,i(u,d)y_{0,i}(u,d)y0,i​(u,d) cannot depend on ddd at all. The condition must hold for every uuu and every pair of sequences, not almost surely. It involves no network, measure or σ\sigmaσ-algebra.

Policy.IsMeasurable

Fix a σ\sigmaσ-algebra on UUU. IsMeasurable π\piπ means two things:

  • for every t∈Nt\in\mathbb{N}t∈N, the map (u,d)↦qt(u,d)(u,d)\mapsto q_t(u,d)(u,d)↦qt​(u,d) is measurable from U×(R≥0n)NU\times(\mathbb{R}^n_{\ge0})^{\mathbb{N}}U×(R≥0n​)N (the product of the given σ\sigmaσ-algebra on UUU with the product σ\sigmaσ-algebra on sequences) to R\mathbb{R}R with its Borel σ\sigmaσ-algebra;
  • for every ttt and every i∈[n]i\in[n]i∈[n], the map (u,d)↦yt,i(u,d)(u,d)\mapsto y_{t,i}(u,d)(u,d)↦yt,i​(u,d) is measurable in the same sense.

This is joint measurability in (u,d)(u,d)(u,d) for each fixed ttt (and iii), and nothing more.

Policy.supArrival and Policy.retArrival

Fix NNN, xxx, π\piπ, a point u∈Uu\in Uu∈U and a demand sequence ddd. Every quantity in this paragraph and the next two depends on all of them, but they are left out of the notation. For t∈Nt\in\mathbb{N}t∈N and i∈[n]i\in[n]i∈[n]:

SAt=φt  (t<L0),SAt=qt−L0(u,d)  (t≥L0),\mathrm{SA}_t=\varphi_t\ \ (t<L_0),\qquad\mathrm{SA}_t=q_{t-L_0}(u,d)\ \ (t\ge L_0),SAt​=φt​  (t<L0​),SAt​=qt−L0​​(u,d)  (t≥L0​), RAi,t=ψi,t  (t<Li),RAi,t=yt−Li, i(u,d)  (t≥Li).\mathrm{RA}_{i,t}=\psi_{i,t}\ \ (t<L_i),\qquad\mathrm{RA}_{i,t}=y_{t-L_i,\,i}(u,d)\ \ (t\ge L_i).RAi,t​=ψi,t​  (t<Li​),RAi,t​=yt−Li​,i​(u,d)  (t≥Li​).

The subtractions are ordinary ones, since they occur only when t≥L0t\ge L_0t≥L0​ or t≥Lit\ge L_it≥Li​. So the value qsq_sqs​ chosen in period sss appears as SAs+L0\mathrm{SA}_{s+L_0}SAs+L0​​, and the value ys,iy_{s,i}ys,i​ chosen in period sss appears as RAi,s+Li\mathrm{RA}_{i,s+L_i}RAi,s+Li​​. The first L0L_0L0​ (resp. LiL_iLi​) periods are filled from the initial sequences.

With zero delays: if L0=0L_0=0L0​=0, then SAt=qt(u,d)\mathrm{SA}_t=q_t(u,d)SAt​=qt​(u,d) for every ttt and φ\varphiφ is never read. If Li=0L_i=0Li​=0, then RAi,t=yt,i(u,d)\mathrm{RA}_{i,t}=y_{t,i}(u,d)RAi,t​=yt,i​(u,d) for every ttt and (ψi,t)t(\psi_{i,t})_t(ψi,t​)t​ is never read.

Policy.whStock, Policy.whAvailable, Policy.netInv

WSt=W+∑s=0t(SAs−∑i∈[n]ys,i(u,d)),WAt=W+∑s=0t−1(SAs−∑i∈[n]ys,i(u,d))+SAt,\mathrm{WS}_t=W+\sum_{s=0}^{t}\Big(\mathrm{SA}_s-\sum_{i\in[n]}y_{s,i}(u,d)\Big),\qquad\mathrm{WA}_t=W+\sum_{s=0}^{t-1}\Big(\mathrm{SA}_s-\sum_{i\in[n]}y_{s,i}(u,d)\Big)+\mathrm{SA}_t,WSt​=W+s=0∑t​(SAs​−i∈[n]∑​ys,i​(u,d)),WAt​=W+s=0∑t−1​(SAs​−i∈[n]∑​ys,i​(u,d))+SAt​, NIi,t=Ii+∑s=0t(RAi,s−ds,i).\mathrm{NI}_{i,t}=I_i+\sum_{s=0}^{t}\big(\mathrm{RA}_{i,s}-d_{s,i}\big).NIi,t​=Ii​+s=0∑t​(RAi,s​−ds,i​).

WWW and IiI_iIi​ are the values before period 000. From the formulas, WA0=W+SA0\mathrm{WA}_0=W+\mathrm{SA}_0WA0​=W+SA0​, and WAt=WSt+∑iyt,i(u,d)\mathrm{WA}_t=\mathrm{WS}_t+\sum_iy_{t,i}(u,d)WAt​=WSt​+∑i​yt,i​(u,d) for every ttt. So WAt\mathrm{WA}_tWAt​ contains the period-ttt term SAt\mathrm{SA}_tSAt​ but not the period-ttt values yt,iy_{t,i}yt,i​, while WSt\mathrm{WS}_tWSt​ contains both. NIi,t\mathrm{NI}_{i,t}NIi,t​ includes the demand dt,id_{t,i}dt,i​ of period ttt itself. All three are plain real numbers and are never truncated at 000.

The value ys,iy_{s,i}ys,i​ is subtracted in WS\mathrm{WS}WS from period sss on, but added in NIi\mathrm{NI}_iNIi​ only from period s+Lis+L_is+Li​ on. So for s≤t<s+Lis\le t<s+L_is≤t<s+Li​ it is counted in neither WSt\mathrm{WS}_tWSt​ nor NIi,t\mathrm{NI}_{i,t}NIi,t​. Likewise, qsq_sqs​ enters WSt\mathrm{WS}_tWSt​ only for t≥s+L0t\ge s+L_0t≥s+L0​. With L0=0L_0=0L0​=0, WAt\mathrm{WA}_tWAt​ already includes qt(u,d)q_t(u,d)qt​(u,d); with Li=0L_i=0Li​=0, NIi,t\mathrm{NI}_{i,t}NIi,t​ already includes yt,i(u,d)y_{t,i}(u,d)yt,i​(u,d).

Policy.periodCost

The period-ttt cost is the real number

ct(u,d)=K0 1[qt(u,d)>0]+∑i∈[n]Ki 1[yt,i(u,d)>0]+h WSt+∑i∈[n](Himax⁡(NIi,t,0)+pmax⁡(−NIi,t,0)).c_t(u,d)=K_0\,\mathbf{1}[q_t(u,d)>0]+\sum_{i\in[n]}K_i\,\mathbf{1}[y_{t,i}(u,d)>0]+h\,\mathrm{WS}_t+\sum_{i\in[n]}\Big(H_i\max(\mathrm{NI}_{i,t},0)+p\max(-\mathrm{NI}_{i,t},0)\Big).ct​(u,d)=K0​1[qt​(u,d)>0]+i∈[n]∑​Ki​1[yt,i​(u,d)>0]+hWSt​+i∈[n]∑​(Hi​max(NIi,t​,0)+pmax(−NIi,t​,0)).
  • The indicators use strict inequality, so a value ≤0\le0≤0 triggers no KKK term.
  • The KKK terms are charged in the period in which the values are chosen, not in the period in which they appear in SA\mathrm{SA}SA or RA\mathrm{RA}RA.
  • The coefficient hhh multiplies the signed WSt\mathrm{WS}_tWSt​; no positive part is taken.
  • NIi,t\mathrm{NI}_{i,t}NIi,t​ enters only through its positive part, weighted by HiH_iHi​, and its negative part, weighted by the common ppp.
  • Amounts not yet counted in WSt\mathrm{WS}_tWSt​ or NIi,t\mathrm{NI}_{i,t}NIi,t​ (see above) contribute nothing to ctc_tct​, apart from the KKK term of the period in which they were chosen.

In general ctc_tct​ can have either sign. Under Standing, and when WSt≥0\mathrm{WS}_t\ge0WSt​≥0, every term is ≥0\ge0≥0.

Policy.Feasible

Feasible N x π holds if and only if, for every u∈Uu\in Uu∈U, every demand sequence d∈(R≥0n)Nd\in(\mathbb{R}^n_{\ge0})^{\mathbb{N}}d∈(R≥0n​)N (all sequences, not almost all) and every t∈Nt\in\mathbb{N}t∈N:

qt(u,d)≥0,yt,i(u,d)≥0  ∀i∈[n],∑i∈[n]yt,i(u,d)≤WAt=W+∑s=0t−1(SAs−∑iys,i(u,d))+SAt.q_t(u,d)\ge0,\qquad y_{t,i}(u,d)\ge0\ \ \forall i\in[n],\qquad\sum_{i\in[n]}y_{t,i}(u,d)\le\mathrm{WA}_t=W+\sum_{s=0}^{t-1}\Big(\mathrm{SA}_s-\sum_{i}y_{s,i}(u,d)\Big)+\mathrm{SA}_t.qt​(u,d)≥0,yt,i​(u,d)≥0  ∀i∈[n],i∈[n]∑​yt,i​(u,d)≤WAt​=W+s=0∑t−1​(SAs​−i∑​ys,i​(u,d))+SAt​.

Because WAt=WSt+∑iyt,i\mathrm{WA}_t=\mathrm{WS}_t+\sum_iy_{t,i}WAt​=WSt​+∑i​yt,i​, the last inequality is equivalent to WSt≥0\mathrm{WS}_t\ge0WSt​≥0. Together with the second condition, it forces WAt≥0\mathrm{WA}_t\ge0WAt​≥0.

The predicate uses the network only through L0L_0L0​, and the initial state only through WWW and (φt)t<L0(\varphi_t)_{t<L_0}(φt​)t<L0​​. It puts no constraint on NI\mathrm{NI}NI, the IiI_iIi​, ψ\psiψ, the LiL_iLi​, μ\muμ or the cost coefficients, and no upper bound on qtq_tqt​. If UUU is empty it holds vacuously. If UUU is nonempty it can be unsatisfiable, because it forces W+∑s=0tφs≥0W+\sum_{s=0}^{t}\varphi_s\ge0W+∑s=0t​φs​≥0 for every t<L0t<L_0t<L0​ (see OPT).

padHist

Take any type α\alphaα (in Type) with a zero element, any T∈NT\in\mathbb{N}T∈N and any z=(z0,…,zT−1)∈αTz=(z_0,\dots,z_{T-1})\in\alpha^Tz=(z0​,…,zT−1​)∈αT. Then padT(z)\mathrm{pad}_T(z)padT​(z) is the infinite sequence equal to ztz_tzt​ for t<Tt<Tt<T and to 000 for t≥Tt\ge Tt≥T. The file uses it with α=R≥0n\alpha=\mathbb{R}^n_{\ge0}α=R≥0n​, where 000 is the zero vector. pad0(z)\mathrm{pad}_0(z)pad0​(z) is the all-zero sequence.

expCost

Take a type UUU with a σ\sigmaσ-algebra, a network NNN, an initial state xxx, a policy π\piπ in Policy n U, any measure ν\nuν on UUU, and T∈NT\in\mathbb{N}T∈N. Here ν\nuν need not be a probability measure; for example, ν=0\nu=0ν=0 gives the value 000. Then

expCost(N,x,π,ν,T)=∫U×(R≥0n)T ∑t=0T−1(ct(u,padT(z)))+ (ν⊗μ⊗T)(du,dz) ∈[0,∞].\mathrm{expCost}(N,x,\pi,\nu,T)=\int_{U\times(\mathbb{R}^n_{\ge0})^{T}}\ \sum_{t=0}^{T-1}\Big(c_t\big(u,\mathrm{pad}_T(z)\big)\Big)_{+}\ (\nu\otimes\mu^{\otimes T})(du,dz)\ \in[0,\infty].expCost(N,x,π,ν,T)=∫U×(R≥0n​)T​ t=0∑T−1​(ct​(u,padT​(z)))+​ (ν⊗μ⊗T)(du,dz) ∈[0,∞].
  • ctc_tct​ is periodCost.
  • (r)+=max⁡(r,0)(r)_+=\max(r,0)(r)+​=max(r,0) is Mathlib's conversion of a real into [0,∞)[0,\infty)[0,∞): every negative real becomes 000. It is applied to each period's cost separately, before summing.
  • μ⊗T\mu^{\otimes T}μ⊗T is the TTT-fold product of μ\muμ on (R≥0n)T(\mathbb{R}^n_{\ge0})^T(R≥0n​)T. The integrating measure is the product of ν\nuν with TTT copies of μ\muμ, so when ν\nuν is a probability measure, u∼νu\sim\nuu∼ν and z0,…,zT−1z_0,\dots,z_{T-1}z0​,…,zT−1​ i.i.d. with law μ\muμ are mutually independent.

Role of the padding. The policy, the stock quantities and the costs are all evaluated at the demand sequence d=padT(z)d=\mathrm{pad}_T(z)d=padT​(z): the TTT sampled vectors in periods 0,…,T−10,\dots,T-10,…,T−1, then zero vectors in every period ≥T\ge T≥T. For t<Tt<Tt<T, ctc_tct​ involves only values chosen in periods ≤t\le t≤t and demands dsd_sds​ with s≤ts\le ts≤t. So if π\piπ is nonanticipative, ct(u,padT(z))c_t(u,\mathrm{pad}_T(z))ct​(u,padT​(z)) depends only on u,z0,…,ztu,z_0,\dots,z_tu,z0​,…,zt​, and the zero padding plays no role. A policy that is not nonanticipative may react to later draws zsz_szs​ with s>ts>ts>t, and to the padded zeros.

The integral. It is Mathlib's lower Lebesgue integral: for an arbitrary [0,∞][0,\infty][0,∞]-valued integrand, it is the supremum of the integrals of measurable simple functions lying below it. When the integrand is measurable it equals the ordinary integral. This is the case when π\piπ satisfies IsMeasurable, since every operation involved, including padT\mathrm{pad}_TpadT​, is measurable. Otherwise it is still defined, as this approximation from below. It may equal ∞\infty∞.

For T=0T=0T=0 the sum is empty and the value is 000. Each TTT uses its own finite product space; no measure on infinite demand sequences is constructed.

avgCost

avgCost(N,x,π,ν)=lim sup⁡T→∞ T−1⋅expCost(N,x,π,ν,T)=inf⁡M∈N sup⁡T≥M T−1⋅expCost(N,x,π,ν,T) ∈[0,∞],\mathrm{avgCost}(N,x,\pi,\nu)=\limsup_{T\to\infty}\ T^{-1}\cdot\mathrm{expCost}(N,x,\pi,\nu,T)=\inf_{M\in\mathbb{N}}\ \sup_{T\ge M}\ T^{-1}\cdot\mathrm{expCost}(N,x,\pi,\nu,T)\ \in[0,\infty],avgCost(N,x,π,ν)=T→∞limsup​ T−1⋅expCost(N,x,π,ν,T)=M∈Ninf​ T≥Msup​ T−1⋅expCost(N,x,π,ν,T) ∈[0,∞],

computed in [0,∞][0,\infty][0,∞], where ν\nuν is again an arbitrary measure on UUU. It is the limit superior, not a limit and not a limit inferior. It is always defined and may be ∞\infty∞. For T≥1T\ge1T≥1, T−1=1/TT^{-1}=1/TT−1=1/T and T−1⋅∞=∞T^{-1}\cdot\infty=\inftyT−1⋅∞=∞. The T=0T=0T=0 term is 0−1⋅expCost(…,0)=∞⋅0=00^{-1}\cdot\mathrm{expCost}(\dots,0)=\infty\cdot0=00−1⋅expCost(…,0)=∞⋅0=0 under Mathlib's conventions. It cannot affect the limsup in any case, since finitely many terms never do.

OPT

For a network NNN and an initial state xxx, with nothing assumed about either (neither Standing nor Valid is required),

OPT(N,x)=inf⁡(U, F, ν, π) lim sup⁡T→∞ T−1∫∑t=0T−1(ct(u,padT(z)))+ (ν⊗μ⊗T)(du,dz) ∈[0,∞].\mathrm{OPT}(N,x)=\inf_{(U,\ \mathcal{F},\ \nu,\ \pi)}\ \limsup_{T\to\infty}\ T^{-1}\int\sum_{t=0}^{T-1}\Big(c_t\big(u,\mathrm{pad}_T(z)\big)\Big)_{+}\ (\nu\otimes\mu^{\otimes T})(du,dz)\ \in[0,\infty].OPT(N,x)=(U, F, ν, π)inf​ T→∞limsup​ T−1∫t=0∑T−1​(ct​(u,padT​(z)))+​ (ν⊗μ⊗T)(du,dz) ∈[0,∞].

The infimum runs over every choice of:

  • a type UUU in the universe Type, Lean's lowest universe of types. It contains, for example, finite types, R\mathbb{R}R, [0,1][0,1][0,1] and sequence spaces; types in higher universes are not included;
  • a σ\sigmaσ-algebra F\mathcal{F}F on UUU;
  • a probability measure ν\nuν on (U,F)(U,\mathcal{F})(U,F);
  • a policy π\piπ in Policy n U that is Nonanticipative, IsMeasurable (for F\mathcal{F}F) and Feasible N x, all at once.

The infimum of the empty family is ∞\infty∞. In words: a single point uuu is drawn from ν\nuν, independently of the demands, and the policy is then a fixed function of uuu and past demands. Feasibility and nonanticipativity must hold for every uuu and every demand sequence. An empty UUU admits no probability measure, so it contributes nothing.

When the family is nonempty. The admissible family is nonempty if and only if

W+∑s=0tφs≥0for every t<L0.W+\sum_{s=0}^{t}\varphi_s\ge0\qquad\text{for every } t<L_0.W+s=0∑t​φs​≥0for every t<L0​.

This is vacuous when L0=0L_0=0L0​=0 and is implied by Valid.

  • It is necessary: for t<L0t<L_0t<L0​, with nonnegative yyy, we get 0≤WAt≤W+∑s≤tφs0\le\mathrm{WA}_t\le W+\sum_{s\le t}\varphi_s0≤WAt​≤W+∑s≤t​φs​.
  • It is sufficient: take UUU a single point with its unit mass, q0≡max⁡(0,−W−∑s<L0φs)q_0\equiv\max\big(0,-W-\sum_{s<L_0}\varphi_s\big)q0​≡max(0,−W−∑s<L0​​φs​), qt≡0q_t\equiv0qt​≡0 for t≥1t\ge1t≥1, and y≡0y\equiv0y≡0. This policy is constant in ddd, hence nonanticipative and measurable, and it is feasible.

When the condition fails, OPT(N,x)=∞\mathrm{OPT}(N,x)=\inftyOPT(N,x)=∞ for that reason alone.

Clipping. If NNN satisfies Standing, every admissible π\piπ has ct≥0c_t\ge0ct​≥0 for all u,d,tu,d,tu,d,t, so the clipping (⋅)+(\cdot)_+(⋅)+​ has no effect. Without Standing (for instance h<0h<0h<0, or some of K0,Ki,Hi,pK_0,K_i,H_i,pK0​,Ki​,Hi​,p negative), negative period costs can occur, and each is replaced by 000 in its own period.

DetPolicy, DetPolicy.toPolicy, DetPolicy.avgCost

A DetPolicy n is a pair of arbitrary functions qt(d)∈Rq_t(d)\in\mathbb{R}qt​(d)∈R and yt,i(d)∈Ry_{t,i}(d)\in\mathbb{R}yt,i​(d)∈R of a period ttt, a demand sequence ddd and (for yyy) an index i∈[n]i\in[n]i∈[n]. No conditions are attached. toPolicy turns it into a Policy n Unit over the one-point type, ignoring the point. DetPolicy.avgCost N x π is avgCost of that policy with ν\nuν the unit mass on the point, which works out to

lim sup⁡T→∞ T−1∫(R≥0n)T∑t=0T−1(ct(padT(z)))+ μ⊗T(dz) ∈[0,∞].\limsup_{T\to\infty}\ T^{-1}\int_{(\mathbb{R}^n_{\ge0})^{T}}\sum_{t=0}^{T-1}\Big(c_t\big(\mathrm{pad}_T(z)\big)\Big)_{+}\ \mu^{\otimes T}(dz)\ \in[0,\infty].T→∞limsup​ T−1∫(R≥0n​)T​t=0∑T−1​(ct​(padT​(z)))+​ μ⊗T(dz) ∈[0,∞].

Here ct(d)c_t(d)ct​(d) is periodCost computed with qt(d)q_t(d)qt​(d) and yt,i(d)y_{t,i}(d)yt,i​(d) in place of qt(u,d)q_t(u,d)qt​(u,d) and yt,i(u,d)y_{t,i}(u,d)yt,i​(u,d). It is defined for every such pair. Nonanticipativity, measurability and feasibility are not required, so all of the following can occur:

  • the lower-integral convention;
  • dependence on later draws and on the zero padding;
  • negative values of qqq, yyy and WS\mathrm{WS}WS;
  • negative period costs clipped to 000.

The file states no relation between this quantity and OPT. However, a one-point UUU with its unit mass is one of the choices in the infimum. So OPT(N,x)≤\mathrm{OPT}(N,x)\leOPT(N,x)≤ DetPolicy.avgCost N x π whenever toPolicy π is nonanticipative, measurable and Feasible N x.

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