A.2, p. 35 — moving the emergency facility up one level and dropping changes the cost by
ProvedReliableFacilityLoc.LevelOrder.emergency_cost_identityfacility-locationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reliability
Let be a feasible solution of (RUFL). Suppose customer is assigned to the regular facility at level and to the emergency facility at level , i.e. . Let be obtained by assigning at level in place of and dropping (so ), and let be the probabilities recomputed from (1e)–(1f). Then is feasible, and
This is the case of the proof of Proposition 2: if , and , the move strictly lowers the cost.
Formalization Note The page does not print this value; it says only that the case "is similar, except that , which reduces the cost even more". The explicit difference follows from (1e)–(1f): the emergency facility at level has and the removed level- term had .
Preamble
import Mathlib import Definitions.Def_ReliableFacilityLoc_LevelOrder_RUFL import Definitions.Def_ReliableFacilityLoc_LevelOrder_Moves open Finset
Formal statement
namespace ReliableFacilityLoc.LevelOrder
/-- **Emergency case `k = J`** (unnumbered; Appendix A.2, proof of Proposition 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).
Let `(X, Y, P)` be feasible for (RUFL), and let customer `i` be assigned to the regular facility `j`
at level `r` and to the emergency facility `J` at level `r + 1 ≤ R`. Move `J` up to level `r` and
drop `j` (`emergencyUpY`), recomputing the probabilities from (1e)–(1f) (`transProb`). The result is
feasible, and its objective differs from that of `(X, Y, P)` by `λ_i P_ijr (φ_i - d_ij)`.
Formalization Note: the page states only that this case "is similar, except that
`Y′_{ij,r+1} = P′_{ij,r+1} = 0`, which reduces the cost even more". The explicit change
`λ_i P_ijr (φ_i - d_ij)` is computed from (1e)–(1f): the emergency facility at level `r` has
`P′_iJr = P_ijr / (1 - q_j)`, and the removed level-`r+1` term had `P_{iJ,r+1} = q_j P_ijr / (1 - q_j)`. -/
theorem emergency_cost_identity {I J R : ℕ} (D : Instance I J R) (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) (r : Fin R)
(hj : Y i j.castSucc r.castSucc = 1) (hJ : Y i (Fin.last J) r.succ = 1) :
D.IsFeasible X (emergencyUpY i j.castSucc r Y)
(D.transProb (emergencyUpY i j.castSucc r Y)) ∧
D.objective X (emergencyUpY i j.castSucc r Y)
(D.transProb (emergencyUpY i j.castSucc r Y)) - D.objective X Y P =
D.lam i * P i j.castSucc r.castSucc * (D.phi i - D.d i j) := 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), case k = J
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.