Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A.2, p. 35 — swapping two regular facilities at consecutive levels changes the cost by λi(1−qk)(dik−dij)Pijr\lambda_i(1-q_k)(d_{ik}-d_{ij})P_{ijr}λi​(1−qk​)(dik​−dij​)Pijr​

Proved
ReliableFacilityLoc.LevelOrder.swap_cost_identity

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

facility-locationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reliability

Let (X,Y,P)(X,Y,P)(X,Y,P) be a feasible solution of (RUFL). Suppose customer iii is assigned to the regular facility jjj at level rrr and to the regular facility kkk at level r+1≤Rr+1 \le Rr+1≤R, i.e. Yijr=Yik,r+1=1Y_{ijr} = Y_{ik,r+1} = 1Yijr​=Yik,r+1​=1. Let Y′Y'Y′ be obtained by exchanging jjj and kkk between the two levels, and let P′=P(Y′)P' = P(Y')P′=P(Y′) be the probabilities recomputed from (1e)–(1f). Then (X,Y′,P′)(X, Y', P')(X,Y′,P′) is feasible, and

Φ(X,Y′,P′)−Φ(X,Y,P)=λi (1−qk) (dik−dij) Pijr.\Phi(X,Y',P') - \Phi(X,Y,P) = \lambda_i\,(1-q_k)\,(d_{ik}-d_{ij})\,P_{ijr}.Φ(X,Y′,P′)−Φ(X,Y,P)=λi​(1−qk​)(dik​−dij​)Pijr​.

This is the computation at the heart of the proof of Proposition 2: when dij>dikd_{ij} > d_{ik}dij​>dik​, λi>0\lambda_i > 0λi​>0 and Pijr>0P_{ijr} > 0Pijr​>0 the swap strictly lowers the cost, so an optimal solution cannot have its regular facilities out of order.

Formalization Note The paper writes "<0< 0<0" at the end of the display under its assumption dij>dikd_{ij} > d_{ik}dij​>dik​; the identity is stated here without that sign. The hypothesis j≠kj \ne kj=k 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
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me