OWMR model: dynamics, period cost, , and
Definitionowmr_network_modelAn OWMR network with retailers consists of a supplier lead time , retailer lead times , a probability measure on (the common law of the demand vectors , which are i.i.d. over periods , with possibly dependent components), setup costs (supplier) and (retailers), holding rates (warehouse) and (retailers), and a common backlog penalty . The standing assumptions are for every , , and . Write .
In period , scheduled shipments arrive; the warehouse places a supplier order , which arrives in period ; it dispatches to retailer , which arrives in period ; then demand occurs. A valid initial state prescribes warehouse stock , retailer net inventories , and nonnegative pipeline quantities arriving at the warehouse in periods and at retailer in periods . Inventories evolve by
and the period cost (1) is
A policy chooses and from the demand history and auxiliary randomness , drawn from a probability law independent of all demands. It is nonanticipative if the decisions of period depend on demands only through , and feasible if orders and dispatches are nonnegative and . The long-run average cost and the optimal cost (2) are
Every guarantee of the mission compares the cost of a constructed policy with .
Formalization Note Demand vectors have type Fin n → ℝ≥0. The expected cost of periods is the lower Lebesgue integral of , as an extended nonnegative real, under , with the history extended by zero vectors (the costs of these periods involve no later demand); for feasible policies . Hence . In the infimum ranges over every auxiliary probability space with U : Type and every measurable, nonanticipative policy that is feasible for every and every demand sequence. A deterministic policy is a policy on the one-point space.
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
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 . 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.
- is an implicit parameter of every declaration, and is allowed. The code numbers coordinates . Here they are relabelled , so a subscript always means one of the separate scalar fields
L0orK0, never a coordinate. The coordinate index is only ever used in sums, suprema and "for all" statements, so the relabelling changes nothing. - Periods are , starting at . They are not relabelled.
- is the set of nonnegative reals. is the set of extended nonnegative reals, in which Mathlib sets and .
- All -algebras are Mathlib's defaults: Borel on and , and product -algebras on finite products, on sequence spaces and on .
DemandVec
DemandVec n is : vectors with nonnegative real entries, with the product of the Borel -algebras. For it is a one-point space. Nonnegativity is part of the type, so every demand entry below is automatically . A demand sequence is any with , and is the -th entry of . The set of all demand sequences carries the product (cylinder) -algebra.
Network
A network (type Network n) is a record with exactly these fields:
- natural numbers and for (any of them may be );
- a measure on , with a proof that is a probability measure. The proof is registered as an instance, so later definitions that need it, such as the product measures , find it automatically;
- real numbers , , , and real numbers , for .
The record imposes nothing beyond having total mass . The reals may have any sign. need not have finite or positive means, and nothing is said about how the coordinates of depend on each other. is a single number shared by all , while , and may vary with . For the indexed families are empty, and 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 : and ;
- , and for every ;
- , for every , and .
Each integral is the Lebesgue integral, valued in , of the nonnegative measurable coordinate map . In other words it is the mean of coordinate under , and the first condition says this mean is finite and strictly positive (equivalently, coordinate is integrable and not -almost surely ). Nothing is required of , of the , or of the joint law beyond these means of single coordinates. For the indexed conditions are vacuous, and Standing reduces to , , . 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 , computed in . For it equals . For the family is empty, and Mathlib's supremum of an empty family of reals is the junk value (not ). Nothing else in the file uses it.
InitState and InitState.Valid
An initial state (type InitState n) is a record of:
- a real number ;
- real numbers for ;
- a real sequence (field
supPipe); - for each , a real sequence (field
retPipe).
All values are arbitrary reals, and the record does not refer to any network. The sequences are infinite whatever and are, but later definitions read only for and for . All other entries affect nothing.
Valid x is the proposition
It puts no condition on the , 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 be any type in Lean's lowest universe Type, with no structure assumed. A policy (type Policy n U) is a pair of completely arbitrary functions
written (field order) and (field dispatch). For each period , these values may depend on the point and on the whole demand sequence , including the entries with . They may be negative, and nothing is assumed about measurability. Such restrictions come only from the separate predicates Nonanticipative, IsMeasurable and Feasible.
Policy.Nonanticipative
is nonanticipative if and only if, for every , every and every two demand sequences with for all ,
So for each fixed , the period- values depend on only through . The same-period vector is excluded, and the dependence on is unrestricted. At the premise holds for every pair , so and cannot depend on at all. The condition must hold for every and every pair of sequences, not almost surely. It involves no network, measure or -algebra.
Policy.IsMeasurable
Fix a -algebra on . IsMeasurable means two things:
- for every , the map is measurable from (the product of the given -algebra on with the product -algebra on sequences) to with its Borel -algebra;
- for every and every , the map is measurable in the same sense.
This is joint measurability in for each fixed (and ), and nothing more.
Policy.supArrival and Policy.retArrival
Fix , , , a point and a demand sequence . Every quantity in this paragraph and the next two depends on all of them, but they are left out of the notation. For and :
The subtractions are ordinary ones, since they occur only when or . So the value chosen in period appears as , and the value chosen in period appears as . The first (resp. ) periods are filled from the initial sequences.
With zero delays: if , then for every and is never read. If , then for every and is never read.
Policy.whStock, Policy.whAvailable, Policy.netInv
and are the values before period . From the formulas, , and for every . So contains the period- term but not the period- values , while contains both. includes the demand of period itself. All three are plain real numbers and are never truncated at .
The value is subtracted in from period on, but added in only from period on. So for it is counted in neither nor . Likewise, enters only for . With , already includes ; with , already includes .
Policy.periodCost
The period- cost is the real number
- The indicators use strict inequality, so a value triggers no term.
- The terms are charged in the period in which the values are chosen, not in the period in which they appear in or .
- The coefficient multiplies the signed ; no positive part is taken.
- enters only through its positive part, weighted by , and its negative part, weighted by the common .
- Amounts not yet counted in or (see above) contribute nothing to , apart from the term of the period in which they were chosen.
In general can have either sign. Under Standing, and when , every term is .
Policy.Feasible
Feasible N x π holds if and only if, for every , every demand sequence (all sequences, not almost all) and every :
Because , the last inequality is equivalent to . Together with the second condition, it forces .
The predicate uses the network only through , and the initial state only through and . It puts no constraint on , the , , the , or the cost coefficients, and no upper bound on . If is empty it holds vacuously. If is nonempty it can be unsatisfiable, because it forces for every (see OPT).
padHist
Take any type (in Type) with a zero element, any and any . Then is the infinite sequence equal to for and to for . The file uses it with , where is the zero vector. is the all-zero sequence.
expCost
Take a type with a -algebra, a network , an initial state , a policy in Policy n U, any measure on , and . Here need not be a probability measure; for example, gives the value . Then
- is
periodCost. - is Mathlib's conversion of a real into : every negative real becomes . It is applied to each period's cost separately, before summing.
- is the -fold product of on . The integrating measure is the product of with copies of , so when is a probability measure, and i.i.d. with law are mutually independent.
Role of the padding. The policy, the stock quantities and the costs are all evaluated at the demand sequence : the sampled vectors in periods , then zero vectors in every period . For , involves only values chosen in periods and demands with . So if is nonanticipative, depends only on , and the zero padding plays no role. A policy that is not nonanticipative may react to later draws with , and to the padded zeros.
The integral. It is Mathlib's lower Lebesgue integral: for an arbitrary -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 satisfies IsMeasurable, since every operation involved, including , is measurable. Otherwise it is still defined, as this approximation from below. It may equal .
For the sum is empty and the value is . Each uses its own finite product space; no measure on infinite demand sequences is constructed.
avgCost
computed in , where is again an arbitrary measure on . It is the limit superior, not a limit and not a limit inferior. It is always defined and may be . For , and . The term is under Mathlib's conventions. It cannot affect the limsup in any case, since finitely many terms never do.
OPT
For a network and an initial state , with nothing assumed about either (neither Standing nor Valid is required),
The infimum runs over every choice of:
- a type in the universe
Type, Lean's lowest universe of types. It contains, for example, finite types, , and sequence spaces; types in higher universes are not included; - a -algebra on ;
- a probability measure on ;
- a policy in
Policy n Uthat isNonanticipative,IsMeasurable(for ) andFeasible N x, all at once.
The infimum of the empty family is . In words: a single point is drawn from , independently of the demands, and the policy is then a fixed function of and past demands. Feasibility and nonanticipativity must hold for every and every demand sequence. An empty admits no probability measure, so it contributes nothing.
When the family is nonempty. The admissible family is nonempty if and only if
This is vacuous when and is implied by Valid.
- It is necessary: for , with nonnegative , we get .
- It is sufficient: take a single point with its unit mass, , for , and . This policy is constant in , hence nonanticipative and measurable, and it is feasible.
When the condition fails, for that reason alone.
Clipping. If satisfies Standing, every admissible has for all , so the clipping has no effect. Without Standing (for instance , or some of negative), negative period costs can occur, and each is replaced by in its own period.
DetPolicy, DetPolicy.toPolicy, DetPolicy.avgCost
A DetPolicy n is a pair of arbitrary functions and of a period , a demand sequence and (for ) an index . 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 the unit mass on the point, which works out to
Here is periodCost computed with and in place of and . 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 , and ;
- negative period costs clipped to .
The file states no relation between this quantity and OPT. However, a one-point with its unit mass is one of the choices in the infimum. So DetPolicy.avgCost N x π whenever toPolicy π is nonanticipative, measurable and Feasible N x.