Proof of Theorem 5, p. 215 — under Assumption 2 there is x̂ ≥ 0 with Rx̂ > 0 vanishing on input activities and input processors
ProvedMaxPressure.FluidStab.input_part_zeroedinput-output-matrixp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-processing-network
Let a stochastic processing network satisfy the standing assumptions of §2 and Assumption 2 (there is with ). Then there is a vector such that
- and componentwise;
- for every input activity ;
- for every input processor .
In the proof of Theorem 5 this vector is the direction along which an LP solution with is pushed to obtain an allocation with strictly positive net outflow from every buffer, without changing the load on the input processors.
Formalization Note "" is componentwise strict positivity on every internal buffer.
Preamble
import Mathlib import Definitions.Def_MaxPressure_FluidStab_Network
Formal statement
namespace MaxPressure.FluidStab
open Matrix
/-- Proof of Theorem 5, App. B, p. 215: from Assumption 2 there is an `x̂ ≥ 0` with `Rx̂ > 0`;
`x̂_j` can be set to `0` for each input activity `j` so that `Rx̂ > 0` still holds, and then
`∑_j A_kj x̂_j = 0` for each input processor `k`. -/
theorem input_part_zeroed {I J K : ℕ} (N : Network I J K) (hN : N.Standing)
(h2 : Assumption2 N) :
∃ xh : Fin J → ℝ, (∀ j, 0 ≤ xh j) ∧ (∀ i, 0 < (R N *ᵥ xh) i) ∧
(∀ j, IsInputActivity N j → xh j = 0) ∧
(∀ k, N.inputProc k → ∑ j, N.A k j * xh j = 0) := by sorry
end MaxPressure.FluidStab
Source
Dai & Lin, Maximum pressure policies in stochastic processing networks, Oper. Res. 53(2) (2005), p. 215, proof of Theorem 5 (App. B), sentences 2–4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.