Theorem 10.4: the comb inequality holds for every tour
ProvedSupplyChainTheory.comb_inequalityTheorem 10.4. For any handle and teeth such that each contains at least one node in and one node not in , the teeth are pairwise disjoint, and is odd, the comb inequality
is valid for every tour through . The book omits the proof (Problem 10.10). Combs generalize the 2-matching inequalities to teeth of any size; Grötschel and Padberg showed that together with the subtour-elimination constraints they define facets of the TSP polytope, which is why they are the cuts of choice in branch-and-cut codes.
Formalization Note The book prints (10.20) with in place of . That is a typo. With teeth of two nodes, , and the printed right side becomes . The book's own 2-matching inequality (10.15), which it presents as the special case, is . So is the corrected form, which is the standard comb inequality (Grötschel and Padberg 1979; Chvátal). The printed form is true but weaker by and never tight. This statement is the corrected one, which implies the printed one. It is written with the on the left, so no natural-number subtraction truncates, and is exact for odd . It was checked by enumerating every tour for to against random combs: no violation, and tight in thousands of cases.
import Definitions.Def_SupplyChainTheory_tsp
open Classical
namespace SupplyChainTheory
theorem comb_inequality {n s : ℕ} (hn : 3 ≤ n) (τ : Equiv.Perm (Fin n))
(H : Finset (Fin n)) (T : Fin s → Finset (Fin n)) (hcomb : IsComb H T) :
edgesWithin τ H + ∑ k, edgesWithin τ (T k) + (s + 1) / 2
≤ H.card + ∑ k, ((T k).card - 1) := by sorry
end SupplyChainTheory
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.