Lemma 7.1 — on the lot-sizing family (7.2), z_AR(U) = 0 and z_Aff(U) = m/2 − 1
ProvedBudgetedAffine.NetworkGap.lemma_7_1Consider the two-stage robust lot-sizing problem (7.1) on the family of instances (7.2): nodes with split into and , ; inventory costs on and on ; capacities ; distances from to and otherwise; and demand uncertainty
Then the optimal adjustable value and the optimal affine value are
both attained. In particular the gap between affine and adjustable policies is unbounded as .
The recourse matrix of (7.1) is a network matrix with entries in . The lemma shows that the non-negativity of the recourse matrix, under which the paper proves its approximation bounds for affine policies, cannot be dropped.
Formalization Note Each optimal value is stated as IsLeast of the set of objective values for which some feasible solution (adjustable, resp. affine ) has cost at most in every scenario; this asserts that the value is attained and is the minimum, and cannot hold vacuously. The distances are encoded by keeping only the arcs (a solution of finite cost never uses another arc); has one row per kept arc, as in App. D. The paper's " even" is , and makes nonempty. The unboundedness of the gap is the immediate consequence and is not stated separately.
import Mathlib import Definitions.Def_BudgetedAffine_NetworkGap_LotSizing import Definitions.Def_BudgetedAffine_NetworkGap_Instance
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.