Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 1 — with R=JR = JR=J, (RUFL) and the scenario-based program (SSP) have the same optimal value

Proved
ReliableFacilityLoc.Scenario.proposition1_equivalence

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

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

Proposition 1 (Cui, Ouyang and Shen). If R=JR = JR=J, then the compact formulation (RUFL) (1a)–(1g) is equivalent to the stochastic programming formulation (SSP) (17a)–(17d) that covers all 2J2^J2J failure scenarios.

Precisely: let the data be customers iii with demand rates λi≥0\lambda_i \ge 0λi​≥0, regular sites j=0,…,J−1j = 0,\dots,J-1j=0,…,J−1 with fixed costs fjf_jfj​ and independent failure probabilities 0≤qj<10 \le q_j < 10≤qj​<1, unit costs dijd_{ij}dij​, penalties ϕi\phi_iϕi​ (the costs diJd_{iJ}diJ​ of the never-failing emergency facility JJJ), and R=J≥1R = J \ge 1R=J≥1 assignment levels beyond level 000. Then

  1. (RUFL) has an optimal solution;
  2. (SSP) has an optimal solution;
  3. for every optimal solution (X,Y,P)(X,Y,P)(X,Y,P) of (RUFL) and every optimal solution (X′,Y′)(X',Y')(X′,Y′) of (SSP),
Φ(X,Y,P)=Ψ(X′,Y′).\Phi(X,Y,P) = \Psi(X',Y').Φ(X,Y,P)=Ψ(X′,Y′).

The proposition justifies replacing an exponentially large scenario-based stochastic program by a compact, polynomial-size mixed-integer program when each customer may be assigned to as many backup facilities as there are sites.

Formalization Note "Equivalent" is read, as in the paper's proof, as equality of optimal values; existence of optima is stated so that the equality is not vacuous. R=JR = JR=J is built into the type of the instance, and R≥1R \ge 1R≥1 (p. 8) then means J≥1J \ge 1J≥1. Both formulations use the corrected constraints: the first sum of (1b) runs over all J+1J+1J+1 facilities, and (17c) is imposed per customer.

Preamble
import Definitions.Def_ReliableFacilityLoc_Scenario_RUFL
import Definitions.Def_ReliableFacilityLoc_Scenario_SSP

open Finset
Formal statement
namespace ReliableFacilityLoc.Scenario

/-- **Proposition 1** (Cui–Ouyang–Shen, UCTC-FR-2010-02 (Feb. 2010), p. 10 (PDF 12); proof in
A.1, pp. 32–34 (PDF 34–36)): "If `R = J`, then formulation (1a)-(1g) is equivalent to the
stochastic programming formulation that covers all failure scenarios." Both (RUFL) (1a)–(1g) and
the scenario-based program (SSP) (17a)–(17d) have optimal solutions, and every optimal solution
of (RUFL) has the same objective value as every optimal solution of (SSP).

Formalization Note: "equivalent" is read, as in the proof, as equality of optimal values; the
existence of optima is stated so that the equality is not vacuous. `R = J` is the instance type
`Instance I J J`; with the standing assumption `R ≥ 1` (p. 8) this means `J ≥ 1`. Both
formulations use the corrected constraints (1b) and (17c) (see `IsRUFLFeasible`, `IsSSPFeasible`):
the first sum of (1b) runs over all `J + 1` facilities, and (17c) is imposed per customer. -/
theorem proposition1_equivalence {I J : ℕ} (D : Instance I J J) :
    (∃ (X : Fin J → ℝ) (Y P : Fin I → Fin (J + 1) → Fin (J + 1) → ℝ), D.IsRUFLOptimal X Y P) ∧
    (∃ (X : Fin J → ℝ) (Y : Fin I → Fin (J + 1) → FailureScenario J → ℝ), D.IsSSPOptimal X Y) ∧
    ∀ (X : Fin J → ℝ) (Y P : Fin I → Fin (J + 1) → Fin (J + 1) → ℝ) (X' : Fin J → ℝ)
      (Y' : Fin I → Fin (J + 1) → FailureScenario J → ℝ),
      D.IsRUFLOptimal X Y P → D.IsSSPOptimal X' Y' →
        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), p. 10 (PDF 12), Proposition 1; proof in Appendix A.1, pp. 32–34 (PDF 34–36); (1b) and (17c) corrected
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