Theorem 4.1 — for disjoint constrained budgeted sets, z_Aff(U) = O(log² n / log log n)·z_AR(U)
ProvedBudgetedAffine.Disjoint.theorem_4_1Consider the two-stage adjustable robust problem (1.1) with , , , polyhedral with for all , and the disjoint constrained budgeted set (4.1) for a partition of and weights . Then
i.e. there are a constant and a threshold such that for every , every , every number of blocks and every such instance,
Here is the number of decision variables. The bound does not depend on or on the number of budget constraints.
Formalization Note and are chosen before , and the instance. Values are extended reals, so an infeasible problem gives and the bound holds trivially. is the natural logarithm and . The hypothesis on is added: without it the statement is false (with , , , , , , one has , and padding with zero columns makes ). It holds whenever . The online covering algorithm used by the proof does not appear in the statement.
import Mathlib import Definitions.Def_BudgetedAffine_Disjoint_Model
namespace BudgetedAffine.Disjoint
open Matrix
/-- Theorem 4.1: for disjoint constrained budgeted sets,
`z_Aff(U) = O(log² n / log log n) · z_AR(U)`, with the constant `C` and the threshold `N` uniform
over `m`, the number of blocks `L`, and every instance. -/
theorem theorem_4_1 :
∃ C : ℝ, 0 < C ∧ ∃ N : ℕ, ∀ n ≥ N, ∀ (m L : ℕ) (A B : Matrix (Fin m) (Fin n) ℝ)
(c d : Fin n → ℝ) (X : Set (Fin n → ℝ)) (S : Fin L → Finset (Fin m))
(w : Fin L → Fin m → ℝ),
(∀ i j, 0 ≤ B i j) → 0 ≤ c → 0 ≤ d → BudgetedAffine.Budget.IsPolyhedral X →
(∀ x ∈ X, 0 ≤ c ⬝ᵥ x) → IsPartition S → (∀ ℓ i, 0 ≤ w ℓ i ∧ w ℓ i ≤ 1) →
BudgetedAffine.Budget.zAff A B c d X (disjointBudgetSet S w) ≤
((C * (Real.log n ^ 2 / Real.log (Real.log n)) : ℝ) : EReal) *
BudgetedAffine.Budget.zAR A B c d X (disjointBudgetSet S w) := by sorry
end BudgetedAffine.Disjoint
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.