Proposition 2 — in any optimal solution of (RUFL), each customer's consecutive levels are ordered by distance,
ProvedReliableFacilityLoc.LevelOrder.proposition2_level_orderConsider the reliability uncapacitated facility location problem (RUFL) with positive demand rates and positive failure probabilities at every regular site. Let be an optimal solution. If customer is assigned to facility at level and to facility at level , that is
then
where and range over all facilities and for the emergency facility.
In words: although (RUFL) does not force a customer to be served by her closer facilities first, every optimal solution assigns her facilities level by level in nondecreasing order of distance, with the emergency facility (cost ) after every regular facility that is no more expensive. This extends the equal-failure-probability result of Snyder and Daskin to site-dependent failure probabilities, and it means that the optimal assignment levels depend only on the distances, given the set of facilities assigned to a customer.
Formalization Note The paper states Proposition 2 without the hypotheses and ; as printed it is false. With one customer, , three sites with , , , and , the site never fails at level 0, every later level has , and the assignment order is optimal although . Demand likewise makes customer 's order irrelevant. The paper's proof needs both hypotheses for its strict inequality. The printed range "" is read as , the range in which exists.
import Mathlib import Definitions.Def_ReliableFacilityLoc_LevelOrder_RUFL open Finset
namespace ReliableFacilityLoc.LevelOrder
/-- **Proposition 2** (p. 10, PDF 12) of Cui, Ouyang and Shen, *Reliable Facility Location Design
under the Risk of Disruptions*, UCTC-FR-2010-02, Feb. 2010. Printed:
"In any optimal solution (X,Y,P) of (RUFL), if Y_ijr = 1 and Y_ik,r+1 = 1, then d_ij ≤ d_ik, for all
0 ≤ i ≤ I − 1, 0 ≤ j ≤ J, and 0 ≤ r ≤ R."
Assume every demand rate is positive (`λ_i > 0`) and every regular facility has a positive failure
probability (`q_k > 0`). Then in every optimal solution `(X, Y, P)` of (RUFL), if customer `i` is
assigned to facility `j` at level `r` and to facility `k` at level `r + 1 ≤ R`, then
`d_ij ≤ d_ik`, where `d_iJ = φ_i` for the emergency facility (`j`, `k` range over all `J + 1`
facilities).
Formalization Note: the hypotheses `0 < lam i` and `0 < q k` are added. As printed the proposition
is false: with one customer, `λ = 1`, three sites with `f = 0`, `d = (1, 5, 3)`, `q = (0, 1/2, 1/2)`, `φ = 100` and `R = 3`, the level-0 facility
never fails, every later level has `P = 0`, and the orders `(0, 1, 2)` and `(0, 2, 1)` have the same
cost, so an optimal solution may list its backups out of order; `λ_i = 0` likewise makes customer
`i`'s order irrelevant. The paper's proof needs `P_ijr > 0` and `λ_i > 0` for its "`< 0`".
The level `r` is `r : Fin R`, encoding `0 ≤ r` and `r + 1 ≤ R`, the range in which `Y_{ik,r+1}`
exists. -/
theorem proposition2_level_order {I J R : ℕ} (D : Instance I J R)
(hlam : ∀ i, 0 < D.lam i) (hq : ∀ k, 0 < D.q k)
(X : Fin J → ℝ) (Y P : Fin I → Fin (J + 1) → Fin (R + 1) → ℝ) (hopt : D.IsOptimal X Y P)
(i : Fin I) (j k : Fin (J + 1)) (r : Fin R)
(hj : Y i j r.castSucc = 1) (hk : Y i k r.succ = 1) :
D.dExt i j ≤ D.dExt i k := by sorry
end ReliableFacilityLoc.LevelOrder
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.