Proof of the equivalence, p. 328 — the converse: u_i = position of city i in its tour makes an itinerary feasible for (2)
ProvedMillerTuckerZemlin.Formulation.itinerary_tourPosition_feasibleformulationinteger-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1traveling-salesman
Let be a legitimate itinerary of problem (1) of Miller, Tucker and Zemlin with at most cities per tour, and let be the number of times travels from city to city . For each city let when is the -th city visited in the tour which includes . Then
This is the converse half of the equivalence: every legitimate itinerary yields a feasible solution of (2), with the non-negative integers ("it is permissible to restrict the to be non-negative integers as well", p. 327).
Formalization Note The are natural numbers cast to ; and plays no role in (2). The bound is what yields the paper's "and always ". No hypothesis is needed: when a legitimate itinerary already forces .
Preamble
import Mathlib import Definitions.Def_MillerTuckerZemlin_Formulation_Model
Formal statement
namespace MillerTuckerZemlin.Formulation
theorem itinerary_tourPosition_feasible (n p : ℕ) (I : Itinerary n) (hI : IsItinerary n p I) :
Feasible n p (arcCount I) (fun i => (tourPosition I i : ℝ)) ∧
∀ i : Fin (n + 1), i ≠ 0 → 1 ≤ tourPosition I i ∧ tourPosition I i ≤ p := 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, "Conversely, if the x_ij correspond to a legitimate itinerary"; p. 327, "(We shall see that it is permissible to restrict the u_i to be non-negative integers as well.)"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.