App. D, p. 37 — every feasible affine solution stocks ≥ m/2 − 1 on J₂, so z_Aff ≥ m/2 − 1
ProvedBudgetedAffine.NetworkGap.affine_lower_boundaffine-policieslot-sizingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
Consider the family of lot-sizing instances (7.2) with nodes. Every feasible affine solution satisfies
and consequently every affine objective value (a number with for all , for some feasible affine solution) satisfies :
This is the lower half of the affine value in Lemma 7.1.
Formalization Note The statement holds for every (for it reduces to , resp. to the non-negativity of the cost), so no hypothesis on is added. Lean indices are 0-based; is the real number , never a natural-number subtraction.
Preamble
import Mathlib import Definitions.Def_BudgetedAffine_NetworkGap_LotSizing import Definitions.Def_BudgetedAffine_NetworkGap_Instance
Formal statement
namespace BudgetedAffine.NetworkGap
/-- App. D, p. 37: every feasible affine solution `(x, y(h) = P h + q)` of the family (7.2)
stocks at least `m/2 − 1 = k − 1` units on `J₂`, and hence `k − 1` is a lower bound for
the objective value of every affine solution: `z_Aff(U) ≥ m/2 − 1`. -/
theorem affine_lower_bound (k : ℕ) :
(∀ (x : Node k → ℝ) (P : Matrix (Arc k) (Node k) ℝ) (q : Arc k → ℝ),
(lotSizingFamily k).Feasible x (LotSizing.affinePolicy P q) →
(k : ℝ) - 1 ≤ ∑ j, x (Sum.inr j)) ∧
(k : ℝ) - 1 ∈ lowerBounds (lotSizingFamily k).affineValues := by sorry
end BudgetedAffine.NetworkGap
Source
El Housni, Goyal, On the Optimality of Affine Policies for Budgeted Uncertainty Sets, arXiv:1807.00163v2, App. D, from "Therefore, Σ_{j∈J2} xj + Σ_{j∈J2} qℓj ≥ m/2" to "zAff ≥ Σ cjxj = Σ_{j∈J2} xj ≥ m/2 − 1", p. 37
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.