Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 3: Φi\Phi_iΦi​ is supermodular on sets of size at most RRR, in the form (18)

Proved
ReliableFacilityLoc.Supermod.proposition3_supermodular

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

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

Consider the reliable facility location model with customers i=0,…,I−1i = 0, \dots, I-1i=0,…,I−1, regular facilities j=0,…,J−1j = 0, \dots, J-1j=0,…,J−1, demand rates λi≥0\lambda_i \ge 0λi​≥0, unit costs dijd_{ij}dij​, penalties φi\varphi_iφi​, failure probabilities 0≤qj<10 \le q_j < 10≤qj​<1, Lagrange multipliers μij\mu_{ij}μij​, and R≥1R \ge 1R≥1 backup levels, and let Φi(S)\Phi_i(S)Φi​(S) be the minimum cost of serving customer iii using only facilities of SSS.

For every customer iii, every set SSS of regular facilities, and all regular facilities u≠vu \ne vu=v not in SSS with ∣S∣+2≤R|S| + 2 \le R∣S∣+2≤R,

Φi(S∪{u,v})−Φi(S∪{u}) ≥ Φi(S∪{v})−Φi(S).\Phi_i(S\cup\{u,v\}) - \Phi_i(S\cup\{u\}) \ \ge\ \Phi_i(S\cup\{v\}) - \Phi_i(S).Φi​(S∪{u,v})−Φi​(S∪{u}) ≥ Φi​(S∪{v})−Φi​(S).

That is, the marginal cost of adding a facility increases as the set grows, so Φi\Phi_iΦi​ is supermodular on the sets that the customer's assignment problem (MSFi_ii​) ranges over. This is the property that lets (MSFi_ii​) be solved by the branch-and-bound algorithm of Goldengorin et al. for supermodular minimization.

Formalization Note The paper states "Φi\Phi_iΦi​ is supermodular" without restriction; the hypothesis ∣S∪{u,v}∣≤R|S \cup \{u,v\}| \le R∣S∪{u,v}∣≤R is added because the unrestricted statement is false. For J=5J = 5J=5, R=3R = 3R=3, λi=1\lambda_i = 1λi​=1, μ≡0\mu \equiv 0μ≡0, d=(3.747,4.39,5.084,7.784,5.209)d = (3.747, 4.39, 5.084, 7.784, 5.209)d=(3.747,4.39,5.084,7.784,5.209), q=(0.393,0.733,0.043,0,0)q = (0.393, 0.733, 0.043, 0, 0)q=(0.393,0.733,0.043,0,0), φi=11.558\varphi_i = 11.558φi​=11.558, S={0,2,3}S = \{0,2,3\}S={0,2,3}, u=1u = 1u=1, v=4v = 4v=4, the left side is about −0.04418-0.04418−0.04418 and the right side about −0.04351-0.04351−0.04351. The paper's proof uses the closed form of Φi\Phi_iΦi​, valid only for ∣S∣≤R|S| \le R∣S∣≤R, and (MSFi_ii​) evaluates Φi\Phi_iΦi​ only on such sets. Costs, penalties and multipliers are arbitrary reals.

Preamble
import Mathlib
import Definitions.Def_ReliableFacilityLoc_Supermod_RSP
import Definitions.Def_ReliableFacilityLoc_Supermod_ClosedForm

open Finset
Formal statement
namespace ReliableFacilityLoc.Supermod

/-- **Proposition 3** (Cui, Ouyang & Shen, UCTC-FR-2010-02 (Feb. 2010), p. 13, PDF 15; proof in
Appendix A.3, pp. 35–37, PDF 37–39), in the form (18) its proof establishes. For every customer
`i`, every set `S` of regular facilities and all regular facilities `u ≠ v` outside `S` with
`|S| + 2 ≤ R`,
`Φ_i(S ∪ {u, v}) − Φ_i(S ∪ {u}) ≥ Φ_i(S ∪ {v}) − Φ_i(S)`.

Printed (p. 13): "Proposition 3. The set function Φi is supermodular, for all i = 0, ··· , I − 1."
Printed (p. 35): "Let S ⊆ {0, ··· , J − 1} be a subset of candidate locations, and
u, v ∈ {0, ··· , J − 1} \ S, we show that Φi(S ∪ {u, v}) − Φi(S ∪ {u}) ≥ Φi(S ∪ {v}) − Φi(S). (18)"

Formalization Note: the hypothesis `|S| + 2 ≤ R`, i.e. `|S ∪ {u, v}| ≤ R`, is added. Without it the
statement is false: for `J = 5`, `R = 3`, `λ_i = 1`, `µ ≡ 0`, `d = (3.747, 4.39, 5.084, 7.784, 5.209)`,
`q = (0.393, 0.733, 0.043, 0, 0)`, `φ_i = 11.558`, `S = {0, 2, 3}`, `u = 1`, `v = 4`, the left side
is ≈ −0.04418 and the right side ≈ −0.04351. The proof uses the closed form of `Φ_i`, which holds
only for `|S| ≤ R`, and (MSF_i) only evaluates `Φ_i` on sets with `|S| ≤ R` (constraint (6c),
p. 13). `0 ≤ λ_i` (demand rates; the proof multiplies a nonpositive bracket by `λ_i q_u`),
`0 ≤ q_j < 1` and `R ≥ 1` are the standing assumptions of §3.1 (pp. 7–8). The costs `d`, penalties
`φ` and multipliers `µ` are arbitrary reals. -/
theorem proposition3_supermodular {I J R : ℕ} (lam : Fin I → ℝ) (d : Fin I → Fin J → ℝ)
    (phi : Fin I → ℝ) (q : Fin J → ℝ) (mu : Fin I → Fin J → ℝ) (hlam : ∀ i, 0 ≤ lam i)
    (hq0 : ∀ j, 0 ≤ q j) (hq1 : ∀ j, q j < 1) (hR : 1 ≤ R) (i : Fin I) (S : Finset (Fin J))
    (u v : Fin J) (huv : u ≠ v) (hu : u ∉ S) (hv : v ∉ S) (hS : S.card + 2 ≤ R) :
    Phi (lam i) (d i) (phi i) q (mu i) R (insert u (insert v S)) -
        Phi (lam i) (d i) (phi i) q (mu i) R (insert u S) ≥
      Phi (lam i) (d i) (phi i) q (mu i) R (insert v S) -
        Phi (lam i) (d i) (phi i) q (mu i) R S := 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. 13 (PDF 15), Proposition 3; proof in Appendix A.3, pp. 35–37 (PDF 37–39), inequality (18)
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