Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4(i), p. 574 — if an item and its predecessors have negative discounted echelon holding cost, the minimal cost of P is unbounded below

Proved
RoslingAssembly.Unbounded.theorem4i_cost_unbounded_below

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

assembly-systemdynamic-programminginventorymultiechelonp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider Problem P for an assembly system with items 1,…,N1, \dots, N1,…,N (N≥1N \ge 1N≥1, item 1 the end item, a tree with s(1)=0s(1) = 0s(1)=0 and 1≤s(i)<i1 \le s(i) < i1≤s(i)<i for i≥2i \ge 2i≥2, indexed so that Mi−1≤MiM_{i-1} \le M_iMi−1​≤Mi​), demands ξ1,ξ2,…\xi_1, \xi_2, \dotsξ1​,ξ2​,… independent with a common law that has a density, ξt≥0\xi_t \ge 0ξt​≥0 and 0<Eξt<∞0 < E\xi_t < \infty0<Eξt​<∞, discount factor 0<α<10 < \alpha < 10<α<1, and well-formed initial positions x0x^0x0. No sign condition is imposed on the echelon holding costs hih_ihi​, on ppp or on H1H_1H1​.

If for some item iii

hi α−Ms(i)+∑k∈B(i)hk α−Ms(k)<0,h_i\,\alpha^{-M_{s(i)}} + \sum_{k \in B(i)} h_k\,\alpha^{-M_{s(k)}} < 0,hi​α−Ms(i)​+k∈B(i)∑​hk​α−Ms(k)​<0,

then the minimal cost of Problem P is unbounded below: for every real number CCC there is a measurable policy π\piπ, feasible from x0x^0x0, whose cost (2) is a real number rrr with

r<C.r < C.r<C.

This is the "practical necessity" half of the Generalized Assumption (i): an item which, together with all its predecessors, has negative discounted echelon holding cost makes the model degenerate, since stockpiling it forever earns money.

Formalization Note. "Unbounded below" is stated with witnesses of real cost: in the extended reals the cost of a policy whose positive and negative parts are both infinite is ⊤−⊤=⊥\top - \top = \bot⊤−⊤=⊥, and such a policy would trivially lie below every CCC. The page allows α=1\alpha = 1α=1 (average cost); this statement is for 0<α<10 < \alpha < 10<α<1. The constant of (2) is dropped, which shifts every cost by the same amount. The well-formedness of x0x^0x0 (the history before period 1 obeys (3) and nonnegative ordering) is taken for granted on the page and makes Problem P feasible.

Preamble
import Mathlib
import Definitions.Def_RoslingAssembly_Unbounded_Model
Formal statement
namespace RoslingAssembly.Unbounded

open MeasureTheory

/-- Theorem 4(i), p. 574: if `h_i α^{−M_{s(i)}} + ∑_{k ∈ B(i)} h_k α^{−M_{s(k)}} < 0` for some
item `i`, then the minimal cost of Problem P is unbounded below: for every real `C` there is a
measurable policy, feasible from `x0`, whose cost is a real number below `C`. -/
theorem theorem4i_cost_unbounded_below (S : Model) (x0 : ℕ → ℕ → ℝ)
    (hT : S.IsTree) (hI : S.IsIndexed) [IsProbabilityMeasure S.ν] (hD : S.DemandStanding)
    (hα0 : 0 < S.α) (hα1 : S.α < 1) (hx0 : S.WellFormed x0)
    (i : ℕ) (hi : i ∈ S.items) (hneg : S.echelonSum i < 0) :
    ∀ C : ℝ, ∃ π : RoslingAssembly.SeriesEquiv.Policy, IsMeasurablePolicy π ∧ S.Feasible x0 π ∧
      ∃ r : ℝ, S.cost π = (r : EReal) ∧ r < C := by sorry

end RoslingAssembly.Unbounded
Source
Rosling, Optimal Inventory Policies for Assembly Systems under Random Demands, Oper. Res. 37(4), 1989, p. 574, Theorem 4 (i)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

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