Theorem 8.7 (Hakimi): the -median problem on a network has an optimal solution consisting of nodes
ProvedSupplyChainTheory.hakimiTheorem 8.7 (Hakimi 1965). Consider a network with node set (the customers, with weights ), node-to-node shortest-path distances , and edges of positive length, so that the distance from node to a point at position along an edge of length is . For there exists a set of nodes such that, for any set of points on the network (nodes or edges),
where is the distance to the nearest point of the set. The -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 is a family of points, repetitions allowed, which only strengthens the claim, and the node set produced has exactly elements. Two properties of the book's network are hypotheses. First, 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 () coincide with its nodes (), and the concavity argument moves points to endpoints. Without them the statement is false: with two nodes at distance , unit weights, and a point at the middle of an "edge" of length between them, the point costs and either node costs .
import Definitions.Def_SupplyChainTheory_location
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.