Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 7.1 — on the lot-sizing family (7.2), z_AR(U) = 0 and z_Aff(U) = m/2 − 1

Proved
BudgetedAffine.NetworkGap.lemma_7_1

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

adjustable-robustaffine-policieslot-sizingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization

Consider the two-stage robust lot-sizing problem (7.1) on the family of instances (7.2): m=2km=2km=2k nodes with k≥1k\ge1k≥1 split into J1J_1J1​ and J2J_2J2​, ∣J1∣=∣J2∣=m/2|J_1|=|J_2|=m/2∣J1​∣=∣J2​∣=m/2; inventory costs ci=0c_i=0ci​=0 on J1J_1J1​ and ci=1c_i=1ci​=1 on J2J_2J2​; capacities Ki=1K_i=1Ki​=1; distances dij=0d_{ij}=0dij​=0 from J1J_1J1​ to J2J_2J2​ and ∞\infty∞ otherwise; and demand uncertainty

U={h∈[0,1]m ∣ ∑i=1mhi≤m/2}.\mathcal U=\Big\{h\in[0,1]^m\ \Big|\ \sum_{i=1}^m h_i\le m/2\Big\}.U={h∈[0,1]m ​ i=1∑m​hi​≤m/2}.

Then the optimal adjustable value and the optimal affine value are

zAR(U)=0andzAff(U)=m2−1,z_{AR}(\mathcal U)=0\qquad\text{and}\qquad z_{Aff}(\mathcal U)=\frac m2-1,zAR​(U)=0andzAff​(U)=2m​−1,

both attained. In particular the gap between affine and adjustable policies is unbounded as m→∞m\to\inftym→∞.

The recourse matrix of (7.1) is a network matrix with entries in {−1,0,1}\{-1,0,1\}{−1,0,1}. The lemma shows that the non-negativity of the recourse matrix, under which the paper proves its O(log⁡n/log⁡log⁡n)O(\log n/\log\log n)O(logn/loglogn) approximation bounds for affine policies, cannot be dropped.

Formalization Note Each optimal value is stated as IsLeast of the set of objective values ttt for which some feasible solution (adjustable, resp. affine y(h)=Ph+qy(h)=Ph+qy(h)=Ph+q) has cost at most ttt in every scenario; this asserts that the value is attained and is the minimum, and cannot hold vacuously. The distances dij=∞d_{ij}=\inftydij​=∞ are encoded by keeping only the arcs J1×J2J_1\times J_2J1​×J2​ (a solution of finite cost never uses another arc); PPP has one row per kept arc, as in App. D. The paper's "mmm even" is m=2km=2km=2k, and k≥1k\ge1k≥1 makes J1,J2J_1,J_2J1​,J2​ nonempty. The unboundedness of the gap is the immediate consequence zAff−zAR=k−1→∞z_{Aff}-z_{AR}=k-1\to\inftyzAff​−zAR​=k−1→∞ and is not stated separately.

Preamble
import Mathlib
import Definitions.Def_BudgetedAffine_NetworkGap_LotSizing
import Definitions.Def_BudgetedAffine_NetworkGap_Instance
Formal statement
namespace BudgetedAffine.NetworkGap

/-- Lemma 7.1, p. 28: for the family of instances (7.2) with `m = 2k` nodes (`k ≥ 1`), the
optimal adjustable value is `z_AR(U) = 0` and the optimal affine value is
`z_Aff(U) = m/2 − 1 = k − 1`, both attained. -/
theorem lemma_7_1 (k : ℕ) (hk : 1 ≤ k) :
    IsLeast (lotSizingFamily k).adjustableValues 0 ∧
      IsLeast (lotSizingFamily k).affineValues ((k : ℝ) - 1) := by sorry

end BudgetedAffine.NetworkGap
Source
El Housni, Goyal, On the Optimality of Affine Policies for Budgeted Uncertainty Sets, arXiv:1807.00163v2, Lemma 7.1, p. 28 (family (7.2), p. 28; proof App. D, pp. 35–37)
Human review
  • Endorsed by Shuze Chen · Oct 14, 2026

    Confirmed by the moderator at approval.

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