Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 10.4: the comb inequality ∑i,j∈Hxij+∑k∑i,j∈Tkxij≤∣H∣+∑k(∣Tk∣−1)+12(s−1)\sum_{i,j \in H} x_{ij} + \sum_k \sum_{i,j \in T_k} x_{ij} \le |H| + \sum_k (|T_k| - 1) + \tfrac{1}{2}(s-1)∑i,j∈H​xij​+∑k​∑i,j∈Tk​​xij​≤∣H∣+∑k​(∣Tk​∣−1)+21​(s−1) holds for every tour

Proved
SupplyChainTheory.comb_inequality

by naimengye · Sep 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

operations-researchpolyhedral-combinatoricstraveling-salesmanvalid-inequalities

Theorem 10.4. For any handle H⊆NH \subseteq NH⊆N and teeth T1,…,Ts⊆NT_1, \dots, T_s \subseteq NT1​,…,Ts​⊆N such that each TkT_kTk​ contains at least one node in HHH and one node not in HHH, the teeth are pairwise disjoint, and s≥3s \ge 3s≥3 is odd, the comb inequality

∑i,j∈Hxij+∑k=1s∑i,j∈Tkxij  ≤  ∣H∣+∑k=1s(∣Tk∣−1)−12(s+1)\sum_{i,j \in H} x_{ij} + \sum_{k=1}^s \sum_{i,j \in T_k} x_{ij} \;\le\; |H| + \sum_{k=1}^s (|T_k| - 1) - \tfrac{1}{2}(s+1)i,j∈H∑​xij​+k=1∑s​i,j∈Tk​∑​xij​≤∣H∣+k=1∑s​(∣Tk​∣−1)−21​(s+1)

is valid for every tour through NNN. 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 +12(s−1)+\tfrac{1}{2}(s-1)+21​(s−1) in place of −12(s+1)-\tfrac{1}{2}(s+1)−21​(s+1). That is a typo. With teeth of two nodes, ∑k(∣Tk∣−1)=s\sum_k(|T_k| - 1) = s∑k​(∣Tk​∣−1)=s, and the printed right side becomes ∣H∣+s+12(s−1)|H| + s + \tfrac{1}{2}(s-1)∣H∣+s+21​(s−1). The book's own 2-matching inequality (10.15), which it presents as the special case, is ∣H∣+12(s−1)|H| + \tfrac{1}{2}(s-1)∣H∣+21​(s−1). 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 sss and never tight. This statement is the corrected one, which implies the printed one. It is written with the 12(s+1)\tfrac{1}{2}(s+1)21​(s+1) on the left, so no natural-number subtraction truncates, and (s+1)/2(s+1)/2(s+1)/2 is exact for odd sss. It was checked by enumerating every tour for n=6n = 6n=6 to 999 against random combs: no violation, and tight in thousands of cases.

Preamble
import Definitions.Def_SupplyChainTheory_tsp
Formal statement
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
Source
Lawrence V. Snyder and Zuo-Jun Max Shen, Fundamentals of Supply Chain Theory, 2nd ed., Wiley 2019, DOI 10.1002/9781119584445, p. 415, Sect. 10.3.3, Theorem 10.4, Eq. (10.20): 'Proof. Omitted; see Problem 10.10'; after Grötschel and Padberg (1979)
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 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