Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A.3: the bracket Ptdiv−∑k=t+1nˉ+1CkP_t d_{iv} - \sum_{k=t+1}^{\bar n+1} C_kPt​div​−∑k=t+1nˉ+1​Ck​ is nonpositive

Proved
ReliableFacilityLoc.Supermod.bracket_nonpos

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

facility-locationoperations-researchp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reliability

Assume 0≤qj<10 \le q_j < 10≤qj​<1 for every regular facility. Let j1,…,jnj_1, \dots, j_nj1​,…,jn​ be regular facilities listed in nondecreasing order of distance dijd_{ij}dij​, and let vvv be a regular facility with div≤φid_{iv} \le \varphi_idiv​≤φi​. Let nˉ\bar nnˉ and ttt be the numbers of listed facilities with dij≤φid_{ij} \le \varphi_idij​≤φi​, resp. dij≤divd_{ij} \le d_{iv}dij​≤div​, and PkP_kPk​, CkC_kCk​ as in the proof of Proposition 3. Then

Pt div−∑k=t+1nˉ+1Ck≤0.P_t\, d_{iv} - \sum_{k=t+1}^{\bar n+1} C_k \le 0.Pt​div​−k=t+1∑nˉ+1​Ck​≤0.

Consequently, by the marginal-cost formula, adding a facility within the penalty distance changes the transportation part of Φi\Phi_iΦi​ by a nonpositive amount, and this sign is what both cases of the proof of Proposition 3 rely on.

Formalization Note The paper claims the bracket is strictly negative; this fails when some qjk=0q_{j_k} = 0qjk​​=0 or when div=φid_{iv} = \varphi_idiv​=φi​ (for instance with an empty list and div=φid_{iv} = \varphi_idiv​=φi​ the bracket is 000). Only the weak inequality is used in the proof, and it is what is stated. No sign is assumed on the distances.

Preamble
import Mathlib
import Definitions.Def_ReliableFacilityLoc_Supermod_RSP
import Definitions.Def_ReliableFacilityLoc_Supermod_ClosedForm

open Finset
Formal statement
namespace ReliableFacilityLoc.Supermod

/-- **Sign of the bracket in the marginal cost** (Cui, Ouyang & Shen, UCTC-FR-2010-02 (Feb. 2010),
Appendix A.3, p. 36, PDF 38). Let `L = [j_1, …, j_n]` be a list of regular facilities in
nondecreasing order of distance, and `v` a regular facility with `d_iv ≤ φ_i`; let `n̄`, `t` be the
numbers of entries with `d_ij ≤ φ_i`, resp. `d_ij ≤ d_iv`. Then
`P_t d_iv − Σ_{k=t+1}^{n̄+1} C_k ≤ 0`.

Printed (p. 36): "Note that the first item in the last equation is negative, because
Ptdiv − Σ_{k=t+1}^{n̄+1} Ck = Pt[div − Σ_{k=t+1}^{n̄} (Π_{ℓ=t+1}^{k−1} qjℓ)(1 − qjk)dijk −
(Π_{ℓ=t+1}^{n̄} qjℓ)φi] < Ptdiv[1 − (Π_{ℓ=t+1}^{k−1} qjℓ)(1 − qjk) − Π_{ℓ=t+1}^{n̄} qjℓ] = 0."

Formalization Note: the paper claims a strict inequality ("negative", "<"). It fails when some
`q_{j_k} = 0` cuts the chain or when `d_iv = φ_i` (e.g. `L = []`, `d_iv = φ_i` gives `0`); only
"`≤ 0`" is used in the proof, so "`≤ 0`" is stated. The printed second line also omits the sum
over `k`. The list need not be the list of a set avoiding `v`, and no cardinality bound is needed:
the claim is an inequality about the numbers `P_k`, `C_k` alone. `0 ≤ q_j < 1` is the standing
assumption of §3.1 (`q_j ≤ 1` suffices). -/
theorem bracket_nonpos {J : ℕ} (d : Fin J → ℝ) (phi : ℝ) (q : Fin J → ℝ)
    (hq0 : ∀ j, 0 ≤ q j) (hq1 : ∀ j, q j < 1) (L : List (Fin J))
    (hLsort : L.Pairwise (fun a b => d a ≤ d b)) (v : Fin J) (hv : d v ≤ phi) :
    prodQ q L (countLE d (d v) L) * d v -
      ∑ k ∈ Icc (countLE d (d v) L + 1) (countLE d phi L + 1), Ck d phi q L k ≤ 0 := by sorry

end ReliableFacilityLoc.Supermod
Source
Cui, Ouyang, Shen, Reliable Facility Location Design under the Risk of Disruptions, UCTC-FR-2010-02 (Feb. 2010), p. 36 (PDF 38), Appendix A.3, "Note that the first item in the last equation is negative"
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