Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2 — a policy of S\mathcal SS is optimal if the stocks between the two reorder points are accessible from its order-up-to level

Proved
VeinottWagnerSS.Selection.theorem2_optimal_of_accessible

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

dynamic-programminginventorymarkov-chainp2o-batch-p200bp2o-gran-per-chapterp2o-plan-paperp2o-v1ss-policy

Let 0<α<10 < \alpha < 10<α<1 and consider the inventory model with set-up cost K≥0K \ge 0K≥0, convex one-period cost GαG_\alphaGα​ with Gα(y)→∞G_\alpha(y) \to \inftyGα​(y)→∞ as ∣y∣→∞|y| \to \infty∣y∣→∞, and i.i.d. integer demands with finite mean. Let S\mathcal SS be the candidate set of Step ii: the (s,S)(s, S)(s,S) policies with s‾≤s≤sˉ\underline{s} \le s \le \bar{s}s​≤s≤sˉ, S‾≤S≤Sˉ\underline{S} \le S \le \bar{S}S​≤S≤Sˉ that minimize Lα(S,S−s)\mathcal L_\alpha(S, S - s)Lα​(S,S−s) among such policies, where s‾,sˉ,S‾,Sˉ\underline{s}, \bar{s}, \underline{S}, \bar{S}s​,sˉ,S​,Sˉ are the integers of (21)–(23).

Let (si,Si)(s^i, S^i)(si,Si) and (sj,Sj)(s^j, S^j)(sj,Sj) belong to S\mathcal SS. Suppose that (si,Si)(s^i, S^i)(si,Si) is optimal, i.e. it minimizes aα(x∣s,S)a_\alpha(x \mid s, S)aα​(x∣s,S) over all (s,S)(s, S)(s,S) policies for every starting stock xxx, and that every integer x′x'x′ with

min⁡(si,sj)≤x′<max⁡(si,sj)\min(s^i, s^j) \le x' < \max(s^i, s^j)min(si,sj)≤x′<max(si,sj)

is accessible from SjS^jSj under (sj,Sj)(s^j, S^j)(sj,Sj). Then (sj,Sj)(s^j, S^j)(sj,Sj) is optimal.

The theorem lets the algorithm of the paper certify a policy of S\mathcal SS as optimal by a reachability check on the demand distribution instead of a comparison of average costs; its Corollaries 2.1 and 2.2 give conditions (e.g. φ(k)>0\varphi(k) > 0φ(k)>0 for k=1,…,sn−s1k = 1, \dots, s^n - s^1k=1,…,sn−s1) under which this check is automatic.

Formalization Note Policies are pairs (s,S)∈Z×Z(s, S) \in \mathbb Z \times \mathbb Z(s,S)∈Z×Z; "optimal" is among all (s,S)(s, S)(s,S) policies for every integer starting stock (p. 536). Lα(S,D)\mathcal L_\alpha(S, D)Lα​(S,D) is aα(S−D−1∣S−D,S)a_\alpha(S - D - 1 \mid S - D, S)aα​(S−D−1∣S−D,S). The bounds are least integers, computed from GαG_\alphaGα​, KKK and α\alphaα. As for Lemma 1, the paper's standing assumptions are kept.

Preamble
import Mathlib
import Definitions.Def_VeinottWagnerSS_Selection_Model
import Definitions.Def_VeinottWagnerSS_Selection_CandidateSet
Formal statement
namespace VeinottWagnerSS.Selection

/-- Veinott & Wagner (1965), Theorem 2, p. 543: let `0 < α < 1` and let `(sⁱ, Sⁱ)`, `(sʲ, Sʲ)`
be policies of the candidate set `𝒮` of Step ii. If `(sⁱ, Sⁱ)` is optimal, and if each `x'`
with `min(sⁱ, sʲ) ≤ x' < max(sⁱ, sʲ)` is accessible from `Sʲ` under `(sʲ, Sʲ)`, then
`(sʲ, Sʲ)` is optimal. -/
theorem theorem2_optimal_of_accessible (M : Model) (α : ℝ) (hα0 : 0 < α) (hα1 : α < 1)
    (pi pj : ℤ × ℤ) (hpi : pi ∈ candSet M α) (hpj : pj ∈ candSet M α)
    (hopt : Optimal M α pi.1 pi.2)
    (hacc : ∀ x' : ℤ, min pi.1 pj.1 ≤ x' → x' < max pi.1 pj.1 →
      Accessible M pj.1 pj.2 pj.2 x') :
    Optimal M α pj.1 pj.2 := by sorry

end VeinottWagnerSS.Selection
Source
Veinott & Wagner, Computing Optimal (s, S) Inventory Policies, Management Sci. 11 (1965), p. 543, Theorem 2 (𝒮 defined p. 536 Step ii and p. 542; bounds p. 537 (21)-(23))
Human review
  • Endorsed by Shuze Chen · Oct 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 1, 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