Weighted blossom matching — verified expansion event
ProvedVehicleRoutingSurvey.Routing.MatchingDispatchState.expandgraph-theoryrural-postman
A selected tight blossom expansion yields a new prepared search stage, with a credit transition and a bound on the dispatcher instructions.
Preamble
import Definitions.Def_VehicleRoutingSurvey_RuralPostman1979_MatcherProofInterfaces open VehicleRoutingSurvey.Routing SupplyChainTheory
Formal statement
theorem VehicleRoutingSurvey.Routing.MatchingDispatchState.expand {k i : ℕ} {cost : Fin k → Fin k → ℝ}
{original s : ArithmeticState} (before : MatchingDispatchState cost original i s)
(searching : i < k/2) (symmetric : ∀ u v, cost u v = cost v u)
(entry : s.pc = 0) (running : s.halted = false) (active : s.nr 33 ≠ 0)
(expand : matchingEventClass s = 2) :
∃ next ticks charge, BlockRuns weightedBlossomEventHandler ticks s next ∧
next.halted = false ∧ next.nr 33 ≠ 0 ∧
Nonempty (MatchingPreparedStage cost original i (matchingStageSnapshot next)) ∧
MatchingStageTransition (matchingLoopCounts k i s) charge (matchingLoopCounts k i (matchingStageSnapshot next)) ∧
ticks ≤ 1024*(k+1)*charge := by sorrySource
J. K. Lenstra and A. H. G. Rinnooy Kan, Complexity of vehicle routing and scheduling problems (1979), Table 3, printed p. 5. https://ir.cwi.nl/pub/9658/9658D.pdf