tsp_opt
def
OPT is the infimum length of a tour on V under edge weights ℓ.
Statement
noncomputable def tsp_opt {V : Type*} [Fintype V] [DecidableEq V] (ℓ : V → V → ℝ) : ℝ
- Defined in
- arXiv:2611.09421 Section 1
- Verified
- 10 Nov 2026
- Axioms
- none listed
- Built on 2
- is_tsp_tourA tour on a finite set V is a permutation σ of V that forms an n-cycle (it is a cycle and has full support).
- tsp_tour_lengthThe length of a tour σ on a finite set V under edge weight function ℓ is ∑_{v ∈ V} ℓ(v, σ(v)).
Read back from the Lean
Given a finite type V with decidable equality and an edge-weight function ℓ : V → V → ℝ, tsp_opt ℓ is defined as the real infimum (sInf) of the set of tour lengths tsp_tour_length ℓ σ over all permutations σ : Equiv.Perm V satisfying is_tsp_tour σ.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- OPT is the infimum length of a tour on V under edge weights ℓ. -/ noncomputable def tsp_opt {V : Type*} [Fintype V] [DecidableEq V] (ℓ : V → V → ℝ) : ℝ := sInf {tsp_tour_length ℓ σ | (σ : Equiv.Perm V) (_ : is_tsp_tour σ)}