App. D, pp. 36–37 — every feasible affine solution has x_j + q_{ℓj} ≥ 1 for ℓ ∈ J₁, j ∈ J₂
ProvedBudgetedAffine.NetworkGap.affine_cover_boundaffine-policieslot-sizingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
Consider the family of lot-sizing instances (7.2) with nodes and , and let be any feasible affine solution. Then for every and every ,
The bound comes from the scenario in which every node of except and the single node of have unit demand; together with (D.3) it is the step that turns the rigidity of affine policies into a cost on .
Formalization Note The paper writes "for any and for any "; the roles are swapped there (the scenario it uses has , , and is only defined for , ). The statement uses , . The hypothesis is added and necessary: for the feasible affine solution , has . Lean indices are 0-based.
Preamble
import Mathlib import Definitions.Def_BudgetedAffine_NetworkGap_LotSizing import Definitions.Def_BudgetedAffine_NetworkGap_Instance
Formal statement
namespace BudgetedAffine.NetworkGap
/-- App. D, pp. 36–37: for `k ≥ 2`, every feasible affine solution `(x, y(h) = P h + q)` of the
family (7.2) satisfies `x_j + q_{ℓj} ≥ 1` for every `ℓ ∈ J₁` and `j ∈ J₂`. -/
theorem affine_cover_bound (k : ℕ) (hk : 2 ≤ k) (x : Node k → ℝ)
(P : Matrix (Arc k) (Node k) ℝ) (q : Arc k → ℝ)
(hfeas : (lotSizingFamily k).Feasible x (LotSizing.affinePolicy P q)) :
∀ ℓ j : Fin k, 1 ≤ x (Sum.inr j) + q (ℓ, j) := 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 "Now fix ℓ ∈ J1 and j ∈ J2" (p. 36) to "xj + qℓj ≥ 1" (p. 37)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.