Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2 — if ot,t+L+1≥S‾−smo_{t,t+L+1} \ge \overline{S} - s^mot,t+L+1​≥S−sm then St(ot)=SmS_t(o_t) = S^mSt​(ot​)=Sm

Proved
GallegoOzerADI.PositiveSetup.myopic_order_up_to_optimal

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

advance-demand-informationdynamic-programminginventorymyopic-policyp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider a stationary instance of the finite-horizon inventory model with advance demand information and set-up costs (Definition Model): the single-period cost Gt=GG_t = GGt​=G, the set-up cost Kt=KK_t = KKt​=K, the discount factor αt=α\alpha_t = \alphaαt​=α and the demand law μt=ν\mu_t = \nuμt​=ν do not depend on ttt, and N>L+1N > L + 1N>L+1. Let SmS^mSm be the least minimizer of GGG, sm=max⁡{y≤Sm:G(y)≥K+G(Sm)}s^m = \max\{y \le S^m : G(y) \ge K + G(S^m)\}sm=max{y≤Sm:G(y)≥K+G(Sm)} and S‾=inf⁡{y>Sm:G(y)>G(Sm)+αK}\overline{S} = \inf\{y > S^m : G(y) > G(S^m) + \alpha K\}S=inf{y>Sm:G(y)>G(Sm)+αK} (Definition MyopicLevels). Fix a period 1≤t≤T1 \le t \le T1≤t≤T and a vector ot=(ot,t+L+1,…,ot,t+N−1)o_t = (o_{t,t+L+1}, \dots, o_{t,t+N-1})ot​=(ot,t+L+1​,…,ot,t+N−1​) of observed demands with nonnegative components. If

ot,t+L+1≥S‾−sm,o_{t,t+L+1} \ge \overline{S} - s^m,ot,t+L+1​≥S−sm,

then the optimal order-up-to level equals the myopic one:

St(ot)=min⁡{y:Vt(y,ot)≤Vt(x,ot) for all x}=Sm.S_t(o_t) = \min\{y : V_t(y, o_t) \le V_t(x, o_t) \text{ for all } x\} = S^m.St​(ot​)=min{y:Vt​(y,ot​)≤Vt​(x,ot​) for all x}=Sm.

Once the demand already observed for period t+L+1t + L + 1t+L+1, the first period beyond the protection period, is large enough, the advance demand information for later periods can be ignored when choosing the order-up-to level. The threshold S‾−sm\overline{S} - s^mS−sm depends only on the single-period cost, the set-up cost and the discount factor.

Formalization Note The conclusion is IsLeast {y | ∀ x, V_t(y, o_t) ≤ V_t(x, o_t)} S^m: SmS^mSm is a global minimizer of Vt(⋅,ot)V_t(\cdot, o_t)Vt​(⋅,ot​) and no smaller level is. Only the first component ot,t+L+1o_{t,t+L+1}ot,t+L+1​ is compared with the threshold. The other components are required to be nonnegative, as all reachable observed-demand vectors are (Eq. (1) with nonnegative demands). The paper's proof uses the lower bound sm≤st+1(ot+1)s^m \le s_{t+1}(o_{t+1})sm≤st+1​(ot+1​) of Lemma 3, which needs this, and a negative component of oto_tot​ would become a negative first component at a later period. The terminal case t=Tt = Tt=T is included: there VT=GV_T = GVT​=G and the statement says that SmS^mSm is the least minimizer of GGG.

Preamble
import Mathlib
import Definitions.Def_GallegoOzerADI_PositiveSetup_Model
import Definitions.Def_GallegoOzerADI_PositiveSetup_MyopicLevels

open MeasureTheory
Formal statement
namespace GallegoOzerADI.PositiveSetup

theorem myopic_order_up_to_optimal {L M : ℕ} [NeZero M] (P : Model L M) (G : ℝ → ℝ)
    (K α : ℝ) (ν : Measure (Fin (L + M + 2) → ℝ)) (hG : ∀ t, P.G t = G)
    (hK : ∀ t, P.K t = K) (hα : ∀ t, P.α t = α) (hμ : ∀ t, P.μ t = ν) (t : ℕ) (ht₁ : 1 ≤ t)
    (htT : t ≤ P.T) (o : Fin M → ℝ) (ho : ∀ j, 0 ≤ o j)
    (hobs : myopicUpperLevel G K α - myopicReorderPoint G K ≤ o 0) :
    IsLeast {y | ∀ x, P.V t y o ≤ P.V t x o} (myopicOrderUpTo G) := by sorry

end GallegoOzerADI.PositiveSetup
Source
Gallego, Özer, Integrating Replenishment Decisions with Advance Demand Information, Management Science 47(10):1344–1360 (2001), p. 1350, Theorem 2 (proof p. 1357)
Read-back

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

Here LLL and MMM are natural numbers with M≠0M \neq 0M=0, and PPP is a structure of type Model with parameters L,ML, ML,M. The code shown does not include the definition of Model or of its fields, so the fields named below are described only by how they are used.

The other inputs are:

  • a function G:R→RG : \mathbb{R} \to \mathbb{R}G:R→R;
  • real numbers KKK and α\alphaα;
  • a measure ν\nuν on the space RL+M+2\mathbb{R}^{L+M+2}RL+M+2 of real vectors indexed by {0,…,L+M+1}\{0, \dots, L+M+1\}{0,…,L+M+1}. The statement assumes nothing about ν\nuν: it need not be a probability measure, finite or σ-finite, unless Model itself requires this.

The following hypotheses are imposed:

  • Stationarity. For every natural number ttt, including t=0t = 0t=0 and t>Tt > Tt>T, the model's period-ttt fields satisfy
P.Gt=G,P.Kt=K,P.αt=α,P.μt=ν.P.G_t = G,\qquad P.K_t = K,\qquad P.\alpha_t = \alpha,\qquad P.\mu_t = \nu.P.Gt​=G,P.Kt​=K,P.αt​=α,P.μt​=ν.

So each of these four fields is constant in ttt, with values GGG, KKK, α\alphaα and ν\nuν.

  • Period range. ttt is a natural number with 1≤t≤T1 \le t \le T1≤t≤T, where T=P.TT = P.TT=P.T is the model's horizon field.
  • State vector. o=(o0,…,oM−1)∈RMo = (o_0, \dots, o_{M-1}) \in \mathbb{R}^Mo=(o0​,…,oM−1​)∈RM with oj≥0o_j \ge 0oj​≥0 for every jjj. The component o0o_0o0​ exists because M≥1M \ge 1M≥1.
  • Condition on the first component. Let Sˉ(G,K,α)\bar S(G,K,\alpha)Sˉ(G,K,α) be myopicUpperLevel G K α and s(G,K)s(G,K)s(G,K) be myopicReorderPoint G K. Their definitions are imported and not shown here. The condition is
Sˉ(G,K,α)−s(G,K)≤o0.\bar S(G,K,\alpha) - s(G,K) \le o_0.Sˉ(G,K,α)−s(G,K)≤o0​.

This is ordinary real subtraction. It constrains only o0o_0o0​; the other components need only be nonnegative.

Vt(y,o)V_t(y, o)Vt​(y,o) denotes the model's value function P.V, evaluated at period ttt, a point yyy and the vector ooo. Its definition is not shown. Consider the set

Y={ y:Vt(y,o)≤Vt(x,o) for every x },\mathcal{Y} = \{\, y : V_t(y, o) \le V_t(x, o) \text{ for every } x \,\},Y={y:Vt​(y,o)≤Vt​(x,o) for every x},

which is the set of global minimizers of y↦Vt(y,o)y \mapsto V_t(y,o)y↦Vt​(y,o) over the whole domain of VVV's second argument. The statement says nothing more about that type than that it carries an order. Let S∗(G)S^*(G)S∗(G) be myopicOrderUpTo G, whose definition is not shown.

The conclusion is that S∗(G)S^*(G)S∗(G) is the least element of Y\mathcal{Y}Y. This has two parts:

  1. S∗(G)S^*(G)S∗(G) is itself a global minimizer:
Vt(S∗(G),o)≤Vt(x,o)for all x.V_t(S^*(G), o) \le V_t(x, o) \quad \text{for all } x.Vt​(S∗(G),o)≤Vt​(x,o)for all x.
  1. Every global minimizer yyy satisfies S∗(G)≤yS^*(G) \le yS∗(G)≤y.

In particular, the theorem asserts that the minimum of Vt(⋅,o)V_t(\cdot, o)Vt​(⋅,o) is attained. Note which quantities appear where:

  • The point S∗(G)S^*(G)S∗(G) depends only on GGG, not on KKK, α\alphaα, ν\nuν, ttt or ooo.
  • KKK and α\alphaα enter only through the stationarity hypotheses and the condition on o0o_0o0​.
  • ν\nuν enters only through P.μt=νP.\mu_t = \nuP.μt​=ν.

Degenerate cases.

  • If T=0T = 0T=0, no ttt satisfies 1≤t≤T1 \le t \le T1≤t≤T, so the statement is vacuous.
  • L=0L = 0L=0 is allowed, and ν\nuν then lives on RM+2\mathbb{R}^{M+2}RM+2.
  • M=1M = 1M=1 is allowed. Then o=(o0)o = (o_0)o=(o0​) is a single nonnegative number and the condition applies to it directly.
  • If Sˉ(G,K,α)−s(G,K)≤0\bar S(G,K,\alpha) - s(G,K) \le 0Sˉ(G,K,α)−s(G,K)≤0, the condition on o0o_0o0​ follows from o0≥0o_0 \ge 0o0​≥0.
  • If Sˉ(G,K,α)−s(G,K)>0\bar S(G,K,\alpha) - s(G,K) > 0Sˉ(G,K,α)−s(G,K)>0, only states with o0o_0o0​ at least that large are covered.
  • Whether Sˉ\bar SSˉ, sss or S∗S^*S∗ can take default values (for example, an infimum or supremum of an empty or unbounded set, or a division by zero) depends on their definitions, which are not shown. If they can, the conclusion is still asserted about whatever value S∗(G)S^*(G)S∗(G) takes.
  • The requirement that the model's fields be constant for every natural ttt could be impossible to satisfy if Model imposes conditions that conflict with it. In that case the statement would be vacuous. That cannot be decided from the code shown.
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 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