Remark, p. 326 — an itinerary with t tours of at most p cities each requires tp ≥ n
ProvedMillerTuckerZemlin.Formulation.itinerary_tours_mul_p_gecombinatoricsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1traveling-salesman
Let be a legitimate itinerary of problem (1) of Miller, Tucker and Zemlin: tours from the base city , together visiting each of the cities exactly once, each tour visiting at most cities. Then
This is the paper's remark that, for fixed , problem (1) has a solution only if ; for , it is the standard traveling salesman problem.
Formalization Note is the number of tours of the itinerary, i.e. the length of the list.
Preamble
import Mathlib import Definitions.Def_MillerTuckerZemlin_Formulation_Model
Formal statement
namespace MillerTuckerZemlin.Formulation
theorem itinerary_tours_mul_p_ge (n p : ℕ) (I : Itinerary n) (hI : IsItinerary n p I) :
n ≤ I.length * p := by sorry
end MillerTuckerZemlin.Formulation
Source
Miller, Tucker, Zemlin, Integer Programming Formulation of Traveling Salesman Problems, J. ACM 7(4) (1960), p. 326, remark after (1), "Note that if t is fixed, then for the problem to have a solution we must have tp ≧ n"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.