Theorem 10.2: the 2-matching inequality holds for every tour
ProvedSupplyChainTheory.two_matching_inequalityoperations-researchpolyhedral-combinatoricstraveling-salesmanvalid-inequalities
Theorem 10.2. For any handle and teeth such that each contains exactly one node in and one node not in , the teeth are pairwise disjoint, and is odd, the 2-matching (blossom) inequality
is valid for every tour through , where when the tour uses edge . The book's proof counts degrees: if the left side reached , the nodes of would have total degree at least , so some node would have degree greater than . Here the count is over the edge set of a tour on nodes, and is the exact natural number since is odd.
Preamble
import Definitions.Def_SupplyChainTheory_tsp
Formal statement
open Classical
namespace SupplyChainTheory
theorem two_matching_inequality {n s : ℕ} (hn : 3 ≤ n) (τ : Equiv.Perm (Fin n))
(H : Finset (Fin n)) (T : Fin s → Finset (Fin n)) (hcomb : IsComb H T)
(hteeth : ∀ k, (T k).card = 2) :
edgesWithin τ H + ∑ k, edgesWithin τ (T k) ≤ H.card + (s - 1) / 2 := by sorry
end SupplyChainTheory
Source
Lawrence V. Snyder and Zuo-Jun Max Shen, Fundamentals of Supply Chain Theory, 2nd ed., Wiley 2019, DOI 10.1002/9781119584445, pp. 413-414, Sect. 10.3.3, Theorem 10.2, Eq. (10.15), and its proof; after Hong (1972)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.