Proof of the equivalence, pp. 327–328 — a feasible x has no cycle avoiding city 0 (all tours include city 0)
ProvedMillerTuckerZemlin.Formulation.no_subtour_avoiding_baseLet be feasible for problem (2) of Miller, Tucker and Zemlin, with parameter . Then there is no cycle of arcs among the non-base cities: there are no and cities , all different from , such that
This is the paper's conclusion "Thus all tours include city 0": following the successors from an arc out of city must return to , since the alternative is reaching a repeated city , i.e. a cycle avoiding . The statement here excludes every such cycle of the feasible , which is what makes every arc of lie on a tour through .
Formalization Note The cycle is a map from to the cities, so . The page argues for the cycle met while following successors from city ; its argument uses only that the 's are nonzero and that the arcs carry , so the statement is made for every such cycle. The case (a loop) is excluded by .
import Mathlib import Definitions.Def_MillerTuckerZemlin_Formulation_Model
namespace MillerTuckerZemlin.Formulation
theorem no_subtour_avoiding_base (n p : ℕ) (x : Fin (n + 1) → Fin (n + 1) → ℕ)
(u : Fin (n + 1) → ℝ) (hx : Feasible n p x u) (k : ℕ) (r : Fin (k + 1) → Fin (n + 1))
(hr : ∀ i, r i ≠ 0) : ¬ ∀ i : Fin (k + 1), x (r i) (r (i + 1)) = 1 := by sorry
end MillerTuckerZemlin.Formulation
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.