A.2, p. 35 — if every regular , an assigned facility has positive serving probability
ProvedReliableFacilityLoc.LevelOrder.prob_pos_of_assignedfacility-locationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reliability
Suppose every regular facility has a positive failure probability, for . Let be a feasible solution of (RUFL). Then for every customer , every facility (the emergency facility included) and every level ,
This is the fact that turns the identity of the swap into the strict inequality "" of the paper's proof: the cost change of an improving swap is weighted by , and it is strictly negative only if .
Formalization Note The hypothesis is not in the paper, which uses silently. Without it the statement fails: if the level-0 facility has , every later level has by (1f).
Preamble
import Mathlib import Definitions.Def_ReliableFacilityLoc_LevelOrder_RUFL open Finset
Formal statement
namespace ReliableFacilityLoc.LevelOrder
/-- **Positivity of the serving probability of an assigned facility** (unnumbered; used for the
strict inequality "`λ_i(1 - q_k)(d_ik - d_ij)P_jr < 0`" in Appendix A.2, p. 35, PDF 37, of Cui,
Ouyang and Shen, *Reliable Facility Location Design under the Risk of Disruptions*,
UCTC-FR-2010-02, Feb. 2010).
If every regular facility has a positive failure probability `q_k > 0`, then in every feasible
solution `(X, Y, P)` of (RUFL), `Y_ijr = 1` implies `P_ijr > 0`, for every facility `j ≤ J`
(including the emergency facility) and every level `r ≤ R`.
Formalization Note: the hypothesis `0 < q k` is not in the paper; without it the statement is false
(if the level-0 facility has `q = 0`, every later level has `P = 0` by (1f)). It is the hypothesis
under which the strict inequality of A.2 holds. -/
theorem prob_pos_of_assigned {I J R : ℕ} (D : Instance I J R) (hq : ∀ k, 0 < D.q k)
(X : Fin J → ℝ) (Y P : Fin I → Fin (J + 1) → Fin (R + 1) → ℝ) (hfeas : D.IsFeasible X Y P)
(i : Fin I) (j : Fin (J + 1)) (r : Fin (R + 1)) (hj : Y i j r = 1) :
0 < P i j r := by sorry
end ReliableFacilityLoc.LevelOrder
Source
Cui, Ouyang, Shen, Reliable Facility Location Design under the Risk of Disruptions, UCTC-FR-2010-02 (Feb. 2010), Appendix A.2 (proof of Proposition 2), p. 35 (PDF 37), the strict inequality "< 0"; (1e)–(1f), p. 9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.