Equivalence of (1) and (2), pp. 326–328 — the MTZ integer program describes exactly the itineraries with at most p cities per tour
ProvedMillerTuckerZemlin.Formulation.mtz_formulation_equivalentFix cities besides the base city and a bound on the number of cities per tour. Let problem (1) be the set of legitimate itineraries: lists of tours from city , each tour a nonempty succession of at most cities other than , visiting each of the cities exactly once in all. For an itinerary write for the number of times it travels from city to city and for its number of tours (returns to ). Let problem (2) be the integer program with non-negative integers () and real subject to
with objective . Then:
- if is feasible for (2), there is a legitimate itinerary with , and ;
- conversely, for every legitimate itinerary there are non-negative integers with feasible for (2), and ;
- for all real distances and every legitimate itinerary , is the total distance travelled along .
This is the paper's claim that (2) "will be shown to be equivalent to (1)", in the form of its "burden of proof": the feasible sets correspond under "the salesman proceeds from city to city if and only if ", and the objectives agree. Parts 1 and 2 also cover fixed : adding to (2) corresponds to itineraries with exactly tours.
Formalization Note The hypothesis is not on the page; without it the claim is false (, : is feasible for (2) but no itinerary exists). The paper's "a feasible solution to (2) has which do define a legitimate itinerary" is read as being equal to the arc counts of that itinerary; "together with appropriate " is made explicit as the existence of natural-number (the paper's remark that the may be taken non-negative integers). Cities are Fin (n + 1), an itinerary is a list of tours (lists of cities), and the absent variables are encoded as .
import Mathlib import Definitions.Def_MillerTuckerZemlin_Formulation_Model
namespace MillerTuckerZemlin.Formulation
theorem mtz_formulation_equivalent (n p : ℕ) (hp : 1 ≤ p) :
(∀ (x : Fin (n + 1) → Fin (n + 1) → ℕ) (u : Fin (n + 1) → ℝ), Feasible n p x u →
∃ I : Itinerary n, IsItinerary n p I ∧ x = arcCount I ∧
∑ i ∈ Finset.univ.filter (· ≠ (0 : Fin (n + 1))), x i 0 = I.length) ∧
(∀ I : Itinerary n, IsItinerary n p I →
(∃ u : Fin (n + 1) → ℕ, Feasible n p (arcCount I) (fun i => (u i : ℝ))) ∧
∑ i ∈ Finset.univ.filter (· ≠ (0 : Fin (n + 1))), arcCount I i 0 = I.length) ∧
(∀ (d : Fin (n + 1) → Fin (n + 1) → ℝ) (I : Itinerary n), IsItinerary n p I →
objective d (arcCount I) = itineraryLength d I) := by sorry
end MillerTuckerZemlin.Formulation
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.