Proof of the equivalence, p. 327 — the constraints of (2) force x_ij ∈ {0, 1}
ProvedMillerTuckerZemlin.Formulation.feasible_x_le_oneassignmentinteger-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1traveling-salesman
Let and let be feasible for problem (2) of Miller, Tucker and Zemlin: the () are non-negative integers with every column and every row summing to , and for . Then
This is the paper's remark "the constraints require that or ", which makes the reading "the salesman proceeds from city to city if and only if " possible.
Formalization Note The statement is for all in ; together with this is . On the diagonal, is part of the encoding of (2) (there is no variable ).
Preamble
import Mathlib import Definitions.Def_MillerTuckerZemlin_Formulation_Model
Formal statement
namespace MillerTuckerZemlin.Formulation
theorem feasible_x_le_one (n p : ℕ) (x : Fin (n + 1) → Fin (n + 1) → ℕ) (u : Fin (n + 1) → ℝ)
(hx : Feasible n p x u) : ∀ i j : Fin (n + 1), x i j ≤ 1 := 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, "Note that the constraints require that x_ij = 0 or 1"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.