Theorem 10.1 (Little et al.): after reducing rows by and columns by with all reduced entries nonnegative,
ProvedSupplyChainTheory.reduced_matrix_boundTheorem 10.1. Let for all , where are constants such that for all . Then is a lower bound on the optimal tour length .
Every tour, traversed in one direction, leaves each node once and enters each node once, so its length under is its length under minus exactly ; being nonnegative under , it is at least under . This is the bounding device of Little et al.'s branch-and-bound.
Formalization Note The book applies the reduction to the upper-triangular matrix only () and asserts the same conclusion. That version is false: node is never a row and node never a column of a triangular entry, so (or ) may be arbitrarily large, and even with the row and column reductions restricted to the entries that exist, a random metric instance violates the bound (see the mission's checks). The statement here is the full-matrix reduction, which is what Little et al. prove and what makes the bookkeeping exact. It needs at least two nodes. With the only "tour" is the self-loop , no entry constrains or , and the bound fails for large .
import Definitions.Def_SupplyChainTheory_tsp
open Classical
namespace SupplyChainTheory
theorem reduced_matrix_bound {n : ℕ} (c : Fin n → Fin n → ℝ) (hn : 2 ≤ n) (ρ κ : Fin n → ℝ)
(hρ : ∀ i, 0 ≤ ρ i) (hκ : ∀ j, 0 ≤ κ j) (hc : ∀ i j, i ≠ j → 0 ≤ reducedCost c ρ κ i j) :
∑ i, ρ i + ∑ j, κ j ≤ optTourLength c := by sorry
end SupplyChainTheory
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.