Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Equivalence of (1) and (2), pp. 326–328 — the MTZ integer program describes exactly the itineraries with at most p cities per tour

Proved
MillerTuckerZemlin.Formulation.mtz_formulation_equivalent

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

formulationinteger-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1subtour-eliminationtraveling-salesman

Fix n≥0n\ge 0n≥0 cities besides the base city 000 and a bound p≥1p\ge 1p≥1 on the number of cities per tour. Let problem (1) be the set of legitimate itineraries: lists of tours from city 000, each tour a nonempty succession of at most ppp cities other than 000, visiting each of the cities 1,…,n1,\dots,n1,…,n exactly once in all. For an itinerary III write aij(I)a_{ij}(I)aij​(I) for the number of times it travels from city iii to city jjj and t(I)t(I)t(I) for its number of tours (returns to 000). Let problem (2) be the integer program with non-negative integers xijx_{ij}xij​ (0≤i≠j≤n0\le i\ne j\le n0≤i=j≤n) and real u1,…,unu_1,\dots,u_nu1​,…,un​ subject to

∑i=0i≠jnxij=1 (j≥1),∑j=0j≠inxij=1 (i≥1),ui−uj+p xij≤p−1 (1≤i≠j≤n),\sum_{\substack{i=0\\ i\ne j}}^{n} x_{ij}=1\ (j\ge1),\qquad \sum_{\substack{j=0\\ j\ne i}}^{n} x_{ij}=1\ (i\ge1),\qquad u_i-u_j+p\,x_{ij}\le p-1\ (1\le i\ne j\le n),i=0i=j​∑n​xij​=1 (j≥1),j=0j=i​∑n​xij​=1 (i≥1),ui​−uj​+pxij​≤p−1 (1≤i=j≤n),

with objective ∑∑i≠jdijxij\sum\sum_{i\ne j} d_{ij}x_{ij}∑∑i=j​dij​xij​. Then:

  1. if (x,u)(x,u)(x,u) is feasible for (2), there is a legitimate itinerary III with x=a(I)x=a(I)x=a(I), and ∑i=1nxi0=t(I)\sum_{i=1}^n x_{i0}=t(I)∑i=1n​xi0​=t(I);
  2. conversely, for every legitimate itinerary III there are non-negative integers u1,…,unu_1,\dots,u_nu1​,…,un​ with (a(I),u)(a(I),u)(a(I),u) feasible for (2), and ∑i=1nai0(I)=t(I)\sum_{i=1}^n a_{i0}(I)=t(I)∑i=1n​ai0​(I)=t(I);
  3. for all real distances dijd_{ij}dij​ and every legitimate itinerary III, ∑∑i≠jdijaij(I)\sum\sum_{i\ne j}d_{ij}a_{ij}(I)∑∑i=j​dij​aij​(I) is the total distance travelled along III.

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 iii to city jjj if and only if xij=1x_{ij}=1xij​=1", and the objectives agree. Parts 1 and 2 also cover fixed ttt: adding ∑i=1nxi0=t\sum_{i=1}^n x_{i0}=t∑i=1n​xi0​=t to (2) corresponds to itineraries with exactly ttt tours.

Formalization Note The hypothesis p≥1p\ge 1p≥1 is not on the page; without it the claim is false (n=1n=1n=1, p=0p=0p=0: x01=x10=1x_{01}=x_{10}=1x01​=x10​=1 is feasible for (2) but no itinerary exists). The paper's "a feasible solution to (2) has xijx_{ij}xij​ which do define a legitimate itinerary" is read as xxx being equal to the arc counts of that itinerary; "together with appropriate uiu_iui​" is made explicit as the existence of natural-number uiu_iui​ (the paper's remark that the uiu_iui​ 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 xiix_{ii}xii​ are encoded as xii=0x_{ii}=0xii​=0.

Preamble
import Mathlib
import Definitions.Def_MillerTuckerZemlin_Formulation_Model
Formal statement
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
Source
Miller, Tucker, Zemlin, Integer Programming Formulation of Traveling Salesman Problems, J. ACM 7(4) (1960), pp. 326–328, equivalence of (1) and (2) (stated p. 326–327, burden of proof p. 327, proof pp. 327–328)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me