Lemma 8 — for fixed q, (22a) and (22b) hold for equally many indices
ProvedGilmoreGomoryTSP.Bottleneck.lemma_8_countp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1permutationstraveling-salesman
Let and be permutations of the jobs and fix an index with . Then the number of indices satisfying (22a) equals the number of indices satisfying (22b):
In words: the permutation sends as many indices from above as it sends from above into . This counting fact is used to show that an arc of outside always comes with an index satisfying (22a).
Formalization Note The statement involves only , and ; the ranking property of , which the paper has in force, is not used in it and is not assumed. ranges over the arc indices Fin n (0-based), the range in which (22a)/(22b) are used.
Preamble
import Mathlib import Definitions.Def_GilmoreGomoryTSP_Bottleneck_Model
Formal statement
namespace GilmoreGomoryTSP.Bottleneck
open Classical in
theorem lemma_8_count {n : ℕ} (φ ψ : Equiv.Perm (Fin (n + 1))) (q : Fin n) :
(Finset.univ.filter (fun i => Cond22a φ ψ q i)).card =
(Finset.univ.filter (fun j => Cond22b φ ψ q j)).card := by sorry
end GilmoreGomoryTSP.Bottleneck
Source
Gilmore and Gomory, Sequencing a one state-variable machine, Oper. Res. 12 (1964), p. 668, Lemma 8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.