Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

With R=JR = JR=J, a nearest-server (SSP) solution has a (RUFL)-feasible counterpart of equal cost

Proved
ReliableFacilityLoc.Scenario.ssp_to_rufl

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

facility-locationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reliabilitystochastic-programming

Suppose R=JR = JR=J. Let (X,Y)(X,Y)(X,Y) be a feasible solution of (SSP) in which every customer in every scenario is served by her nearest operating open facility (ties to the lowest index, with δJω=1\delta_{J\omega} = 1δJω​=1 and XJ=1X_J = 1XJ​=1). Then there are Y′Y'Y′, P′P'P′ such that (X,Y′,P′)(X,Y',P')(X,Y′,P′) is feasible for (RUFL) and

Φ(X,Y′,P′)=Ψ(X,Y).\Phi(X,Y',P') = \Psi(X,Y).Φ(X,Y′,P′)=Ψ(X,Y).

The paper's Y′Y'Y′ assigns customer iii, in nondecreasing order of distance (ties to the lower index), to the open sites jjj with dij≤diJd_{ij} \le d_{iJ}dij​≤diJ​, followed by the emergency facility JJJ; and P′P'P′ is the corresponding level probability (1−qj(i,r))∏ℓ<rqj(i,ℓ)(1-q_{j(i,r)})\prod_{\ell<r} q_{j(i,\ell)}(1−qj(i,r)​)∏ℓ<r​qj(i,ℓ)​.

Consequently the optimal value of (RUFL) is at most that of (SSP): "the optimal solution to (SSP) is also a lower bound to (RUFL)".

Formalization Note The paper applies the construction to an optimal, normalized solution of (SSP); it uses only feasibility and the normalization, so the statement is made for every such solution. R=JR = JR=J is built into the type of the instance; it is what allows all open sites to be placed on the levels 0,…,R−10,\dots,R-10,…,R−1.

Preamble
import Definitions.Def_ReliableFacilityLoc_Scenario_RUFL
import Definitions.Def_ReliableFacilityLoc_Scenario_SSP

open Finset
Formal statement
namespace ReliableFacilityLoc.Scenario

/-- **(SSP) → (RUFL) with equal cost when `R = J`** (Cui–Ouyang–Shen, UCTC-FR-2010-02 (Feb. 2010),
A.1, proof of Proposition 1, pp. 33–34 (PDF 35–36)). Let `R = J`. For every (SSP)-feasible
`(X, Y)` in the normalized form of p. 33 (each customer in each scenario served by her closest
operating open facility, ties to the lowest index) there is a (RUFL)-feasible `(X', Y', P')` with
`X' = X` and `Φ(X', Y', P') = Ψ(X, Y)`; hence the optimal value of (RUFL) is at most that of (SSP)
("the optimal solution to (SSP) is also a lower bound to (RUFL)").

Formalization Note: the paper starts from an optimal `(X, Y)` normalized as on p. 33; its
construction (levels = the open facilities `j` with `d_ij ≤ d_iJ` in nondecreasing distance, ties
to the lower index, followed by `J`) uses only feasibility and the normalization, so the statement
is made for every such feasible solution. `R = J` is the instance type `Instance I J J`; it is what
lets all open facilities fit on the levels `0, …, R-1`. -/
theorem ssp_to_rufl {I J : ℕ} (D : Instance I J J) (X : Fin J → ℝ)
    (Y : Fin I → Fin (J + 1) → FailureScenario J → ℝ) (h : D.IsSSPFeasible X Y)
    (hY : ∀ i ω k, Y i k ω = 1 ↔ D.IsNearestServer X i ω k) :
    ∃ Y' P' : Fin I → Fin (J + 1) → Fin (J + 1) → ℝ,
      D.IsRUFLFeasible X Y' P' ∧ D.ruflObjective X Y' P' = D.sspObjective X Y := by sorry

end ReliableFacilityLoc.Scenario
Source
Cui, Ouyang, Shen, Reliable Facility Location Design under the Risk of Disruptions, UCTC-FR-2010-02 (Feb. 2010), Appendix A.1 (proof of Proposition 1), pp. 33–34 (PDF 35–36), construction of (X′, Y′, P′) and the display ending "= Ψ(X, Y)"
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