(D.3), p. 36 — a feasible affine policy on arc (i, j) is the constant P_{(i,j),i} + q_{ij} = 0 off its own node
ProvedBudgetedAffine.NetworkGap.eq_D_3Consider the family of lot-sizing instances (7.2) with nodes and . Let be any feasible affine solution, where has one row per arc and one column per node, so that
Then for every , and for every and
In words: no inventory can be shipped out of a node whose own demand is , and an affine policy can only respect this on all such scenarios if the flow on arc depends on alone and vanishes at . This rigidity is what forces affine policies to pay on .
Formalization Note The hypothesis () is added and necessary. For the only scenario with is , and (D.3) fails: , is a feasible affine solution with . The paper's " for all " is derived from (D.2) at and the capacity . Lean indices are 0-based; has rows indexed by the arcs , the only arcs of finite distance.
import Mathlib import Definitions.Def_BudgetedAffine_NetworkGap_LotSizing import Definitions.Def_BudgetedAffine_NetworkGap_Instance
namespace BudgetedAffine.NetworkGap
/-- App. D, p. 36, (D.3): for `k ≥ 2` (`m ≥ 4`), every feasible affine solution
`(x, y(h) = P h + q)` of the family (7.2) has `x_i = 1` on `J₁`, and for every arc `(i, j)`
`P_{(i,j),i} + q_{ij} = 0` and `P_{(i,j),ℓ} = 0` for every node `ℓ ≠ i`. -/
theorem eq_D_3 (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)) :
(∀ i, x (Sum.inl i) = 1) ∧
∀ i j, P (i, j) (Sum.inl i) + q (i, j) = 0 ∧
∀ v, v ≠ Sum.inl i → P (i, j) v = 0 := by sorry
end BudgetedAffine.NetworkGap
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.