Proof of the equivalence, p. 328 — no tour of a feasible x visits more than p cities
ProvedMillerTuckerZemlin.Formulation.no_tour_longer_than_pinteger-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1subtour-eliminationtraveling-salesman
Let and let be feasible for problem (2) of Miller, Tucker and Zemlin. Then no tour of visits more than cities: there are no cities , all different from the base city , with
Together with the absence of subtours avoiding , this is the half of the equivalence that shows a feasible solution of (2) describes an itinerary of (1) with at most cities per tour.
Formalization Note The cities are a map from to the cities (index shifted down by one). The hypothesis is not on the page: for the claim is false (with , is feasible, there being no -constraint, and is a tour of cities). The paper's step needs , which the paper leaves implicit.
Preamble
import Mathlib import Definitions.Def_MillerTuckerZemlin_Formulation_Model
Formal statement
namespace MillerTuckerZemlin.Formulation
theorem no_tour_longer_than_p (n p : ℕ) (hp : 1 ≤ p) (x : Fin (n + 1) → Fin (n + 1) → ℕ)
(u : Fin (n + 1) → ℝ) (hx : Feasible n p x u) (r : Fin (p + 1) → Fin (n + 1))
(hr : ∀ k, r k ≠ 0) (h0 : x 0 (r 0) = 1) :
¬ ∀ k : Fin p, x (r k.castSucc) (r k.succ) = 1 := by sorry
end MillerTuckerZemlin.Formulation
Source
Miller, Tucker, Zemlin, Integer Programming Formulation of Traveling Salesman Problems, J. ACM 7(4) (1960), p. 328, proof of the equivalence, "It remains to observe that no tour is of length greater than p"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.