Single-location problems, policies, canonical optima, mirror cost, ,
Definitionowmr_single_locationSingle-location problem. Let be a probability law on , a cost function, and a setup cost. In each period the position may be raised by , which costs if ; the post-action position incurs , and an i.i.d. demand with law then reduces it. The single-location value is the infimum, over all nonanticipative (possibly randomized) policies, of
policies. Started at pre-action position , the policy raises the position to whenever it is at most ; base stock is the case . A pair is a canonical optimum (Lemma 1) if , the policy attains , and the canonical conditions (4) hold:
A best half window of is a pair with and whose long-run average holding and backlog cost is smallest among all such pairs.
Mirror cost. With the warehouse-rate loss , the mirror cost of an policy with post-action positions is , and a minimizing is a mirror center.
Network cost functions. For retailer with marginal demand , , where is a sum of i.i.d. copies of , and (equation (8)). For aggregate demand , , where is a sum of i.i.d. copies of (), and (equation (22)). The augmented cost of an policy for retailer is its long-run average cost at the actual setup cost plus its mirror cost. The renewal function is (equation (9)). The demand vector is associated if for all bounded, coordinatewise nondecreasing (Section 6).
These objects are the building blocks of both policies and both guarantees.
Formalization Note Every long-run average is the limsup of Cesàro averages of expected costs, valued in ; where the source writes a limit, the limit exists and equals this limsup. Averages of policies start at pre-action position , and starts at position (the source shows that it does not depend on the initial position). A real cost enters through ; every used in the mission is nonnegative. and are Bochner integrals; the canonical conditions compare with in . In the association condition, and are also required to be measurable, the standard convention.
import Definitions.Def_owmr_network_model
/-!
# Single-location problems, (s,S) policies, and the cost functions of the OWMR paper
Source: M. Hu, "A 5/2 Guarantee for Echelon Stock (s,S) Policies in One-Warehouse
Multi-Retailer Systems": Section 3 (the single-location problems and `(s,S)` policies used by
Definition 1, mirror cost, augmented cost), Section 4.1 (the single-location value `𝒥_D(f;K)`,
Lemma 1 and the canonical conditions (4)), equations (8) (`F_i`, `J_i`), (9) (renewal measure,
`M(w)`), (14) (warehouse-rate loss `φ`, mirror cost), (22) (`f_{L₀}`, `J₀`), and Section 6
(association).
-/
open MeasureTheory
open scoped ENNReal NNReal
noncomputable section
namespace OWMR
variable {n : ℕ}
/-! ## The single-location problem (Section 4.1) -/
/-- A single-location policy with auxiliary randomness `u : U`: the order quantity in period
`t`, as a function of `u` and the demand sequence. -/
abbrev SLPolicy (U : Type) := ℕ → U → (ℕ → ℝ≥0) → ℝ
/-- Post-action position in period `t`, starting from pre-action position `y0` in period `0`:
`x_t = y0 + ∑_{s ≤ t} q_s - ∑_{s < t} D_s`. -/
def slPos {U : Type} (y0 : ℝ) (q : SLPolicy U) (u : U) (d : ℕ → ℝ≥0) (t : ℕ) : ℝ :=
y0 + ∑ s ∈ Finset.range (t + 1), q s u d - ∑ s ∈ Finset.range t, (d s : ℝ)
/-- Period cost `K 1{q_t > 0} + f(x_t)` of the single-location problem. -/
def slPeriodCost {U : Type} (f : ℝ → ℝ) (K y0 : ℝ) (q : SLPolicy U) (u : U) (d : ℕ → ℝ≥0)
(t : ℕ) : ℝ :=
K * (if 0 < q t u d then 1 else 0) + f (slPos y0 q u d t)
/-- Long-run average cost `limsup_T T⁻¹ 𝔼 ∑_{t<T} (K 1{q_t>0} + f(x_t))`, demands i.i.d. with
law `ρ`, auxiliary randomness with law `ν`. -/
def slAvgCost {U : Type} [MeasurableSpace U] (ρ : Measure ℝ≥0) [IsProbabilityMeasure ρ]
(f : ℝ → ℝ) (K y0 : ℝ) (q : SLPolicy U) (ν : Measure U) : ℝ≥0∞ :=
Filter.limsup (fun T : ℕ => (T : ℝ≥0∞)⁻¹ *
∫⁻ ω, ∑ t ∈ Finset.range T, ENNReal.ofReal (slPeriodCost f K y0 q ω.1 (padHist T ω.2) t)
∂(ν.prod (Measure.pi fun _ : Fin T => ρ))) Filter.atTop
/-- Admissible single-location policies: nonanticipative, measurable, nonnegative orders. -/
def SLAdmissible {U : Type} [MeasurableSpace U] (q : SLPolicy U) : Prop :=
(∀ (t : ℕ) (u : U) (d d' : ℕ → ℝ≥0), (∀ s < t, d s = d' s) → q t u d = q t u d') ∧
(∀ t : ℕ, Measurable (fun ω : U × (ℕ → ℝ≥0) => q t ω.1 ω.2)) ∧
(∀ t u d, 0 ≤ q t u d)
/-- The single-location value `𝒥_D(f;K)`: the infimum of the long-run average cost over all
nonanticipative policies (from initial position `0`; by Lemma 1 the value does not depend on the
initial position). -/
def slValue (ρ : Measure ℝ≥0) [IsProbabilityMeasure ρ] (f : ℝ → ℝ) (K : ℝ) : ℝ≥0∞ :=
⨅ (U : Type) (_ : MeasurableSpace U) (ν : Measure U) (_ : IsProbabilityMeasure ν)
(q : SLPolicy U) (_ : SLAdmissible q), slAvgCost ρ f K 0 q ν
/-! ## `(s,S)` policies -/
/-- Pre-action positions of the `(s,S)` policy started at pre-action position `S`: whenever the
position is at most `s` it is raised to `S`, then demand reduces it. -/
def ssPre (s S : ℝ) (d : ℕ → ℝ≥0) : ℕ → ℝ
| 0 => S
| t + 1 => (if ssPre s S d t ≤ s then S else ssPre s S d t) - (d t : ℝ)
/-- Post-action position of the `(s,S)` policy in period `t`. -/
def ssPost (s S : ℝ) (d : ℕ → ℝ≥0) (t : ℕ) : ℝ :=
if ssPre s S d t ≤ s then S else ssPre s S d t
/-- Period cost of the `(s,S)` policy: `K` for a positive order, plus `f` of the post-action
position. -/
def ssPeriodCost (f : ℝ → ℝ) (K s S : ℝ) (d : ℕ → ℝ≥0) (t : ℕ) : ℝ :=
K * (if ssPre s S d t ≤ s ∧ ssPre s S d t < S then 1 else 0) + f (ssPost s S d t)
/-- Long-run average cost of the `(s,S)` policy started at `S` (setup cost `K` per order).
With `K = 0` this is its long-run average holding and backlog cost. -/
def ssAvgCost (ρ : Measure ℝ≥0) [IsProbabilityMeasure ρ] (f : ℝ → ℝ) (K s S : ℝ) : ℝ≥0∞ :=
Filter.limsup (fun T : ℕ => (T : ℝ≥0∞)⁻¹ *
∫⁻ z, ∑ t ∈ Finset.range T, ENNReal.ofReal (ssPeriodCost f K s S (padHist T z) t)
∂(Measure.pi fun _ : Fin T => ρ)) Filter.atTop
/-- `(s,S)` is a canonical optimum (Lemma 1): `s < S`, the `(s,S)` policy is optimal (its average
cost started at `S` equals `J = 𝒥_D(f;K)`), and the canonical conditions (4) hold:
`f(s) = J`, `f(S) ≤ J`, and `f(x) ≤ J` for `s ≤ x ≤ S`. -/
def IsCanonicalOptimum (ρ : Measure ℝ≥0) [IsProbabilityMeasure ρ] (f : ℝ → ℝ) (K s S : ℝ) :
Prop :=
s < S ∧ ssAvgCost ρ f K s S = slValue ρ f K ∧
ENNReal.ofReal (f s) = slValue ρ f K ∧ ENNReal.ofReal (f S) ≤ slValue ρ f K ∧
∀ y ∈ Set.Icc s S, ENNReal.ofReal (f y) ≤ slValue ρ f K
/-- `(s,S)` has the smallest long-run average holding and backlog cost among the `(s',S')`
policies with `sh ≤ s' < S' ≤ Sh` and `S' - s' = (Sh - sh)/2` (the half windows of
`[sh, Sh]`), and is itself such a policy. -/
def IsBestHalfWindow (ρ : Measure ℝ≥0) [IsProbabilityMeasure ρ] (f : ℝ → ℝ) (sh Sh s S : ℝ) :
Prop :=
sh ≤ s ∧ s < S ∧ S ≤ Sh ∧ S - s = (Sh - sh) / 2 ∧
∀ s' S' : ℝ, sh ≤ s' → s' < S' → S' ≤ Sh → S' - s' = (Sh - sh) / 2 →
ssAvgCost ρ f 0 s S ≤ ssAvgCost ρ f 0 s' S'
/-! ## Warehouse-rate loss and mirror cost -/
/-- The warehouse-rate loss `φ(y) = h y⁺ + p y⁻`. -/
def whLoss (h p y : ℝ) : ℝ := h * max y 0 + p * max (-y) 0
/-- Long-run average mirror loss `φ(a - P̂_t)` of the `(s,S)` policy started at `S`, where `P̂_t`
is its post-action position. -/
def mirrorAvg (ρ : Measure ℝ≥0) [IsProbabilityMeasure ρ] (h p s S a : ℝ) : ℝ≥0∞ :=
Filter.limsup (fun T : ℕ => (T : ℝ≥0∞)⁻¹ *
∫⁻ z, ∑ t ∈ Finset.range T, ENNReal.ofReal (whLoss h p (a - ssPost s S (padHist T z) t))
∂(Measure.pi fun _ : Fin T => ρ)) Filter.atTop
/-- The mirror cost of the `(s,S)` policy: the minimum over centers `a` of `mirrorAvg`. -/
def mirrorCost (ρ : Measure ℝ≥0) [IsProbabilityMeasure ρ] (h p s S : ℝ) : ℝ≥0∞ :=
⨅ a : ℝ, mirrorAvg ρ h p s S a
/-! ## Renewal function (9) -/
/-- `M(w) = U[0,w) = ∑_{k ≥ 0} ℙ(D^{(k)} < w)`, with `D^{(k)}` the sum of `k` i.i.d. demands of
law `ρ` (and `D^{(0)} = 0`). -/
def renewalM (ρ : Measure ℝ≥0) [IsProbabilityMeasure ρ] (w : ℝ) : ℝ≥0∞ :=
∑' k : ℕ, (Measure.pi fun _ : Fin k => ρ) {z | ∑ j, (z j : ℝ) < w}
/-! ## Network-level cost functions -/
/-- Marginal law of retailer `i`'s demand `D_i`. -/
def Network.marginal (N : Network n) (i : Fin n) : Measure ℝ≥0 := N.μ.map (fun x => x i)
instance (N : Network n) (i : Fin n) : IsProbabilityMeasure (N.marginal i) :=
Measure.isProbabilityMeasure_map (measurable_pi_apply i).aemeasurable
/-- Law of aggregate demand `D = ∑_i D_i`. -/
def Network.aggregate (N : Network n) : Measure ℝ≥0 := N.μ.map (fun x => ∑ i, x i)
instance (N : Network n) : IsProbabilityMeasure N.aggregate :=
Measure.isProbabilityMeasure_map (Finset.measurable_sum _ fun i _ => measurable_pi_apply i).aemeasurable
/-- `F_i(y) = 𝔼[H_i (y - Z_i)⁺ + p (Z_i - y)⁺]` from (8), where `Z_i` is a sum of `L_i + 1`
i.i.d. demands of retailer `i`. -/
def Network.F (N : Network n) (i : Fin n) (y : ℝ) : ℝ :=
∫ z, (N.H i * max (y - ∑ j, (z j : ℝ)) 0 + N.p * max (∑ j, (z j : ℝ) - y) 0)
∂(Measure.pi fun _ : Fin (N.L i + 1) => N.marginal i)
/-- `J_i(k) = 𝒥_{D_i}(F_i; k)` from (8). -/
def Network.J (N : Network n) (i : Fin n) (k : ℝ) : ℝ≥0∞ :=
slValue (N.marginal i) (N.F i) k
/-- `f_{L₀}(y) = 𝔼 φ(y - D^{(L₀)})` from (22), where `D^{(L₀)}` is a sum of `L₀` i.i.d. aggregate
demands (`D^{(0)} = 0`). -/
def Network.fL0 (N : Network n) (y : ℝ) : ℝ :=
∫ z, whLoss N.h N.p (y - ∑ j, (z j : ℝ)) ∂(Measure.pi fun _ : Fin N.L0 => N.aggregate)
/-- `J₀(k) = 𝒥_D(f_{L₀}; k)` from (22). -/
def Network.J0 (N : Network n) (k : ℝ) : ℝ≥0∞ :=
slValue N.aggregate N.fL0 k
/-- The augmented cost of the `(s,S)` policy for retailer `i` (Section 3): its long-run average
cost in the single-location problem with actual setup cost `K_i` and lead time `L_i`, plus the
mirror cost of its position. -/
def Network.augCost (N : Network n) (i : Fin n) (s S : ℝ) : ℝ≥0∞ :=
ssAvgCost (N.marginal i) (N.F i) (N.K i) s S + mirrorCost (N.marginal i) N.h N.p s S
/-- Association of the demand vector within a period (Section 6): `Cov(u(D_t), v(D_t)) ≥ 0`
for all bounded, measurable, coordinatewise nondecreasing `u, v`. -/
def Network.Associated (N : Network n) : Prop :=
∀ u v : DemandVec n → ℝ, Measurable u → Measurable v → Monotone u → Monotone v →
(∃ C, ∀ x, |u x| ≤ C) → (∃ C, ∀ x, |v x| ≤ C) →
(∫ x, u x ∂N.μ) * (∫ x, v x ∂N.μ) ≤ ∫ x, u x * v x ∂N.μ
end OWMR
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Conventions used throughout. is the set of nonnegative reals with its Borel -algebra. A nonnegative number that enters real arithmetic is treated as a real number. Sequences carry the product -algebra generated by the coordinates, and carries the product -algebra. For and a probability measure on , is the -fold product measure on , under which are independent with law . For the space has exactly one point (the empty tuple) and is the unit point mass on it. For , is its zero padding (the context function padHist): for and for . For real , . This is how every real-valued period cost below is turned into an extended nonnegative number, so negative values become . In , and . The integral of a -valued function is always defined and may be . If the function is not measurable, it is the lower integral, meaning the supremum of the integrals of measurable simple functions lying below it. For a -valued sequence, , which always exists and may be .
SLPolicy. For a type (an arbitrary set), an element of SLPolicy U is any function that assigns a real number to each time , each and each sequence . No sign, measurability or information restriction is built in. Such restrictions appear only in SLAdmissible.
slPos, slPeriodCost. Take a type , a real , SLPolicy U, , and . Then
The -sum includes time , while the -sum stops at . In particular . Given in addition an arbitrary function and a real , with no sign assumption on either,
The indicator uses a strict inequality, so is charged only when is strictly positive. Both quantities are real and may be negative.
slAvgCost. The inputs are:
- a type with a -algebra;
- a measure on , assumed to be a probability measure;
- an arbitrary ;
- reals and ;
- an arbitrary
SLPolicy U(no admissibility is required here); - an arbitrary measure on (not required to be a probability measure here).
For and , let
Then
For each horizon , the following hold:
- One is used in all periods, and the integral is against the product measure . So when is a probability measure, is independent of the i.i.d. -distributed .
- is evaluated on the whole zero-padded sequence . Nothing in this definition stops from depending on or on the padded zeros.
- Each period cost is clipped at on its own before summing; the total is not clipped as a whole.
- The integral of the -period total is divided by , and the limsup is taken over these averaged integrals. It is not the integral of a pathwise limsup.
The term equals and does not affect the limsup.
SLAdmissible. For a type with -algebra , SLPolicy U is admissible if and only if all three of the following hold:
- For every and , and all with for every , we have . So depends on only through . For the hypothesis is empty, so does not depend on at all.
- For every , the map is measurable from (with the product of and the sequence -algebra) to (Borel).
- for all .
No bound, integrability or other condition is imposed.
slValue. The inputs are a probability measure on , an arbitrary (no measurability, continuity, sign or growth condition) and a real of any sign. Then
The infimum is taken in , not as a real-valued infimum. It ranges over every type in the lowest universe (informally, every set ), every -algebra on , every probability measure on , and every SLPolicy U that is admissible (conditions 1 to 3 of SLAdmissible). The starting value is fixed at , so the argument of at time is . By condition 1, for this argument and the indicator depend on only through , so the zero padding has no effect. The index family is nonempty: for example, a one-point with is admissible. So the value is not the empty-infimum default . It can still be , and it need not be attained.
ssPre, ssPost. Take reals (no relation between them is assumed) and . Two real sequences are defined by the recursion
ssPre returns and ssPost returns . The sequence starts at , so for every . The reset test is non-strict: resets to . Both and depend on only through . If , every lies in . If , then for all .
ssPeriodCost. For an arbitrary , reals , a sequence and ,
For the indicator equals . For it equals . Since , the term is never charged at . The value is real and may be negative.
ssAvgCost. For a probability measure on , an arbitrary and reals ,
The sequence starts at , and there is no randomization variable. Each period cost is clipped at on its own. The limsup is taken over averaged integrals, and the term is . Since depends only on , the zero padding has no effect.
IsCanonicalOptimum. Take a probability measure on , an arbitrary and reals . The proposition holds if and only if all five of the following hold:
- (strict);
- ;
- ;
- ;
- for every real with .
All comparisons are in , and values of are clipped at first. Condition 3 forces to be finite and equal to , so by condition 2 is finite too. If , condition 3 forces . Any point with satisfies condition 5 automatically. Condition 4 is the case of condition 5. In condition 2, the left side uses the sequence started at , while uses starting value . The same appears on both sides.
IsBestHalfWindow. Take a probability measure on , an arbitrary , and reals (the arguments sh, Sh, s, S). The proposition holds if and only if both of the following hold:
- , , and .
- For all reals with , , and , we have .
The fixed-cost argument is on both sides, so only is averaged. Comparisons are in , where holds. The pair itself belongs to the compared family, so it minimizes over that family. The proposition cannot hold when , because then , which contradicts .
whLoss. For reals of any sign, .
mirrorAvg, mirrorCost. Take a probability measure on and reals , with as in ssPost (started at ). Let , which is . Then
The same conventions apply. Per-period clipping matters only if or is negative, the limsup is of averaged integrals, and the term is . Then
Here is one constant chosen outside the limsup; it does not depend on , or . The infimum is taken in over all real , need not be attained, and may be .
renewalM. For a probability measure on and a real ,
The -th term is the probability that a sum of independent -distributed variables is strictly less than . The series of nonnegative terms equals the supremum of its partial sums and may be . The term (an empty sum, which is , under a point mass) is if and if . For every term is , so . For the value is at least . It is , for instance, when is the point mass at .
Network data (unfolded from the context file). In the remaining declarations, is an implicit parameter and may be . Indices range over . A network bundles the following data:
- , and for each ;
- a probability measure on (the context calls this space
DemandVec n); - reals , , , and .
No declaration in this file imposes any sign, moment or other condition on these data. The context file has a separate predicate Network.Standing, which requires positive finite coordinate means, and , but it is not referenced here. The field is not used anywhere in this file.
Network.marginal, Network.aggregate, and the two instances. For a network and an index , is the image of under the coordinate map , that is, the law of the -th coordinate. is the image of under , the law of the coordinate sum; when it is the point mass at . Both are measures on . The two instances record, with proof, that and are probability measures. They add no assumption.
Network.F. For a network , an index and a real ,
The integral is over independent copies of the marginal , not of the joint law , with weights and . It is a real-valued (Bochner) integral, which by convention equals when the integrand is not integrable. If and has infinite mean, then for every . If or has finite mean, the integral is the genuine expectation.
Network.J. For a network , an index and a real , . Unfolded,
The infimum is in . It ranges over all types with a -algebra, all probability measures on , and all admissible . Admissible means three things: depends only on , the map is measurable, and . The starting value is , and is as above, including its zero convention. The fixed cost is the argument ; the field is not used.
Network.fL0. For a network and a real ,
This is evaluated at minus a sum of independent copies of . The count is , not , and the weight is , not . If , then . Under the Bochner convention, if , and has infinite mean, then . Having infinite mean is equivalent to some having infinite mean. In every other case is the genuine expectation.
Network.J0. For a network and a real , . This is the same infimum in as for , with in place of , (including its zero convention) in place of , starting value and fixed cost . The field is not used.
Network.augCost. For a network , an index and reals ,
This is the sum of two quantities computed separately:
- the limsup average of ;
- the infimum over constants of the limsup average of .
Both use the sequence started at and driven by i.i.d. -distributed inputs. Here the field is used, and the weight is , not . The sum is if either term is .
Network.Associated. For a network , this holds if and only if the following is true for all functions that are:
- measurable;
- nondecreasing for the coordinatewise order, where means for every ;
- bounded, each with its own real such that (respectively ) for all .
For every such pair,
All three integrals are genuine, since the integrands are bounded and measurable and is a probability measure. The inequality is non-strict. Only pairs that are both nondecreasing are tested. The condition depends on only through . For it holds automatically, since is then a point mass.