Theorem 10.17 (Held-Karp bound): for every
ProvedSupplyChainTheory.held_karp_boundheld-karplagrangian-relaxationlower-boundsoperations-researchtraveling-salesman
Theorem 10.17. For any ,
where is an optimal 1-tree under the revised distances of (10.31) and its node degrees. The right-hand side is the Held-Karp lower bound ; it follows from Lemma 10.15 applied to and both parts of Lemma 10.16. Maximizing it over by subgradient steps (10.34) gives the strongest bounds in practice for the TSP, and the bound is the Lagrangian relaxation of the degree constraints.
Preamble
import Definitions.Def_SupplyChainTheory_tsp
Formal statement
open Classical
namespace SupplyChainTheory
theorem held_karp_bound {n : ℕ} (c : Fin n → Fin n → ℝ) (hc : IsMetric c) (hn : 3 ≤ n)
(lam : Fin n → ℝ) (r : Fin n) (G : SimpleGraph (Fin n)) (hG : Is1Tree r G)
(hopt : ∀ G' : SimpleGraph (Fin n), Is1Tree r G' →
graphWeight (revisedCost c lam) G ≤ graphWeight (revisedCost c lam) G') :
graphWeight c G + ∑ i, lam i * ((G.degree i : ℝ) - 2) ≤ optTourLength c := 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. 446, Sect. 10.6.1, Theorem 10.17, Eq. (10.33), and its proof; after Held and Karp (1970, 1971)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.