Proof of the equivalence, p. 328 — along a path of m arcs avoiding city 0 the potentials u rise by at least m
ProvedMillerTuckerZemlin.Formulation.potential_path_boundLet be feasible for problem (2) of Miller, Tucker and Zemlin, with parameter . Let () be cities, none equal to the base city , such that for . Then
For a single arc () this is the paper's inequality , obtained from ; for general it is the summed form the paper uses twice ("Summing from to " and "Then, as before, "). The thus act as node potentials that strictly increase along every arc between non-base cities.
Formalization Note The path is a map from to the cities. Consecutive cities of the path are automatically distinct, since in the encoding of (2). The page states the summed bound as ; the exact sum is , which is what is stated here ( for a path of arcs). No hypothesis is needed.
import Mathlib import Definitions.Def_MillerTuckerZemlin_Formulation_Model
namespace MillerTuckerZemlin.Formulation
theorem potential_path_bound (n p : ℕ) (x : Fin (n + 1) → Fin (n + 1) → ℕ) (u : Fin (n + 1) → ℝ)
(hx : Feasible n p x u) (m : ℕ) (r : Fin (m + 1) → Fin (n + 1))
(hr : ∀ k, r k ≠ 0) (hpath : ∀ k : Fin m, x (r k.castSucc) (r k.succ) = 1) :
u (r 0) - u (r (Fin.last m)) ≤ -(m : ℝ) := by sorry
end MillerTuckerZemlin.Formulation
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.