Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 8.7 (Hakimi): the ppp-median problem on a network has an optimal solution consisting of nodes

Proved
SupplyChainTheory.hakimi

by naimengye · Sep 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

facility-locationnetworksoperations-researchp-median

Theorem 8.7 (Hakimi 1965). Consider a network with node set III (the customers, with weights hi≥0h_i \ge 0hi​≥0), node-to-node shortest-path distances ddd, and edges of positive length, so that the distance from node iii to a point at position ttt along an edge (u,w)(u, w)(u,w) of length ℓ\ellℓ is min⁡{d(i,u)+tℓ, d(i,w)+(1−t)ℓ}\min\{d(i, u) + t\ell,\ d(i, w) + (1-t)\ell\}min{d(i,u)+tℓ, d(i,w)+(1−t)ℓ}. For 1≤p≤∣I∣1 \le p \le |I|1≤p≤∣I∣ there exists a set Ip∗⊆II^*_p \subseteq IIp∗​⊆I of ppp nodes such that, for any set XXX of ppp points on the network (nodes or edges),

∑i∈Ihi c(i,Ip∗)  ≤  ∑i∈Ihi c(i,X),\sum_{i \in I} h_i\, c(i, I^*_p) \;\le\; \sum_{i \in I} h_i\, c(i, X),i∈I∑​hi​c(i,Ip∗​)≤i∈I∑​hi​c(i,X),

where c(i,⋅)c(i, \cdot)c(i,⋅) is the distance to the nearest point of the set. The ppp-median problem may therefore be treated as a discrete problem over node subsets. The reason is that, as a point slides along an edge, its distance to every node is concave in the position, so the weighted sum of distances of the customers it serves is concave and is minimized at an endpoint.

Formalization Note The set XXX is a family of ppp points, repetitions allowed, which only strengthens the claim, and the node set produced has exactly ppp elements. Two properties of the book's network are hypotheses. First, ddd is a shortest-path distance, so it satisfies the triangle inequality. Second, each point lies on an edge whose length is at least the distance between its endpoints, since the edge is itself a path. Together they make the endpoints of an edge (t=0,1t = 0, 1t=0,1) coincide with its nodes (min⁡{d(i,u),d(i,w)+ℓ}=d(i,u)\min\{d(i,u), d(i,w) + \ell\} = d(i,u)min{d(i,u),d(i,w)+ℓ}=d(i,u)), and the concavity argument moves points to endpoints. Without them the statement is false: with two nodes at distance 101010, unit weights, p=1p = 1p=1 and a point at the middle of an "edge" of length 111 between them, the point costs 111 and either node costs 101010.

Preamble
import Definitions.Def_SupplyChainTheory_location
Formal statement
namespace SupplyChainTheory

theorem hakimi {n p : ℕ} (d : Fin n → Fin n → ℝ) (hw : Fin n → ℝ) (hwn : ∀ i, 0 ≤ hw i)
    (hp : 1 ≤ p) (hpn : p ≤ n)
    (htri : ∀ i j k : Fin n, d i k ≤ d i j + d j k)
    (X : Fin p → NetPoint n)
    (hedge : ∀ k, d (X k).u (X k).w ≤ (X k).len ∧ d (X k).w (X k).u ≤ (X k).len) :
    ∃ S : Finset (Fin n), S.card = p ∧
      ∑ i, hw i * nearestNodeDist d i S ≤ ∑ i, hw i * nearestDist d i X := by sorry

end SupplyChainTheory
Source
Lawrence V. Snyder and Zuo-Jun Max Shen, Fundamentals of Supply Chain Theory, 2nd ed., Wiley 2019, DOI 10.1002/9781119584445, p. 298, Sect. 8.3.2, Theorem 8.7 (Hakimi (1965))
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 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