Proof of the equivalence, p. 327 — under the correspondence the objective of (2) is the distance travelled in (1)
ProvedMillerTuckerZemlin.Formulation.objective_eq_itineraryLengthformulationinteger-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, let be the number of times travels from city to city , and let () be arbitrary distances. Then
the right-hand side summing over all arcs of all tours of with multiplicity. That is, under the correspondence the form minimized in (2) is the total distance travelled by the salesman in (1).
Formalization Note No sign, symmetry or triangle condition is placed on , as on the page. The diagonal appears on neither side: a legitimate itinerary never travels an arc .
Preamble
import Mathlib import Definitions.Def_MillerTuckerZemlin_Formulation_Model
Formal statement
namespace MillerTuckerZemlin.Formulation
theorem objective_eq_itineraryLength (n p : ℕ) (d : Fin (n + 1) → Fin (n + 1) → ℝ)
(I : Itinerary n) (hI : IsItinerary n p I) :
objective d (arcCount I) = itineraryLength d I := by sorry
end MillerTuckerZemlin.Formulation
Source
Miller, Tucker, Zemlin, Integer Programming Formulation of Traveling Salesman Problems, J. ACM 7(4) (1960), p. 327, proof of the equivalence, "Under this correspondence the form to be minimized in (2) is the total distance to be traveled by the salesman in (1)"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.