App. D, p. 37 — the affine solution y_{im}(h) = 1 − h_i is feasible and costs m/2 − 1
ProvedBudgetedAffine.NetworkGap.affine_solutionaffine-policieslot-sizingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
Consider the family of lot-sizing instances (7.2) with nodes, , and let also denote the last node of . The affine solution
is feasible for (7.1) on , and its cost in every scenario is
It shows , the upper half of the affine value in Lemma 7.1.
Formalization Note The solution is written with the explicit (row of arc equal to , all else ) and (, all else ) of the instance definition, for ; the paper's node is the last node Sum.inr (Fin.last n). 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, p. 37: for `k = n + 1`, the affine solution `x_i = 1` (`i ≠ m`), `x_m = 0`,
`y_{im}(h) = 1 − h_i`, `y_{ij}(h) = 0` (`j ≠ m`) is feasible for the family (7.2) and costs
`m/2 − 1 = n` in every scenario. -/
theorem affine_solution (n : ℕ) :
(lotSizingFamily (n + 1)).Feasible (ubX n) (LotSizing.affinePolicy (ubP n) (ubQ n)) ∧
∀ h ∈ (lotSizingFamily (n + 1)).U,
(lotSizingFamily (n + 1)).cost (ubX n) (LotSizing.affinePolicy (ubP n) (ubQ n) h)
= (n : ℝ) := 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 we consider the following affine solution" to "zAff(U) = m/2 − 1.", p. 37
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.