A.2, p. 35 — swapping two regular facilities at consecutive levels changes the cost by
ProvedReliableFacilityLoc.LevelOrder.swap_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 regular facility at level , i.e. . Let be obtained by exchanging and between the two levels, and let be the probabilities recomputed from (1e)–(1f). Then is feasible, and
This is the computation at the heart of the proof of Proposition 2: when , and the swap strictly lowers the cost, so an optimal solution cannot have its regular facilities out of order.
Formalization Note The paper writes "" at the end of the display under its assumption ; the identity is stated here without that sign. The hypothesis is not needed: it follows from (1c).
Preamble
import Mathlib import Definitions.Def_ReliableFacilityLoc_LevelOrder_RUFL import Definitions.Def_ReliableFacilityLoc_LevelOrder_Moves open Finset
Formal statement
namespace ReliableFacilityLoc.LevelOrder
/-- **Swap cost identity, `k` regular** (unnumbered; Appendix A.2, proof of Proposition 2, pp. 34–35,
PDF 36–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 regular facility `k` at level `r + 1 ≤ R`. Exchange `j` and `k` between the
two levels (`swapY`), and recompute the probabilities from (1e)–(1f) (`transProb`). The result is
feasible, and its objective differs from that of `(X, Y, P)` by `λ_i (1 - q_k) (d_ik - d_ij) P_ijr`.
Formalization Note: the page's `P′` keeps `P′_hℓs = P_hℓs` at every other index; that array does
not satisfy (1e)–(1f) at the unassigned entries, so here `P′` is the solution of (1e)–(1f) for
`Y′`, which agrees with the page's `P′` wherever `Y′ = 1`. The page concludes "`< 0`" under
`d_ij > d_ik`; the identity is stated here without that sign. `j ≠ k` is not assumed: it follows
from (1c). -/
theorem swap_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 k : Fin J) (r : Fin R)
(hj : Y i j.castSucc r.castSucc = 1) (hk : Y i k.castSucc r.succ = 1) :
D.IsFeasible X (swapY i j.castSucc k.castSucc r Y)
(D.transProb (swapY i j.castSucc k.castSucc r Y)) ∧
D.objective X (swapY i j.castSucc k.castSucc r Y)
(D.transProb (swapY i j.castSucc k.castSucc r Y)) - D.objective X Y P =
D.lam i * (1 - D.q k) * (D.d i k - D.d i j) * P i j.castSucc r.castSucc := 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), pp. 34–35 (PDF 36–37), unnumbered display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.