§1, pp. 33–35 — Munkres' algorithm terminates on every real matrix, never gets stuck, and ends with an optimal assignment
ProvedMunkresAlg.Assignment.munkres_algorithm_correctLet be any real matrix, being the cost of assigning row (man) to column (job) . Consider Munkres' algorithm on , with all of its free choices (the order in which the Preliminaries consider the zeros, and the non-covered zero primed in Step 1). Then:
- the algorithm can start: there is a start state for ;
- every run is finite: from every start state there is no infinite sequence of moves;
- no run gets stuck: every reachable state that is not done has a next move;
- the output is optimal: at every reachable done state the starred zeros are exactly the positions of a permutation , and
Together, 2 and 3 say every run reaches the done state, and 4 says that it then holds a set of independent elements of with minimum sum, which is the assignment problem of p. 32. Optimality is with respect to the original matrix , not the transformed one.
Formalization Note The entries of are arbitrary reals: the integrality assumption of p. 32 is withdrawn on p. 35. Finiteness of every run is stated as accessibility (Acc) of the start state for the reversed move relation. The test "if all columns are covered, stop" is also applied right after the Preliminaries (the page goes to Step 1 unconditionally there, after which Step 3 would have no non-covered element if the Preliminaries already starred zeros). For the start state is done and the empty permutation is optimal.
import Mathlib import Definitions.Def_HeldWolfeCrowder_Assignment_Setting import Definitions.Def_MunkresAlg_Assignment_Basic import Definitions.Def_MunkresAlg_Assignment_Algorithm
namespace MunkresAlg.Assignment
/-- Munkres (1957), §1, pp. 33–35: correctness of the assignment algorithm on every real
`n × n` matrix `A`. The Preliminaries can be carried out; every run is finite; no run gets stuck
before it stops; and when it stops, the starred zeros are the positions `(σ r, r)` of a
permutation `σ` that is an optimal assignment for the original matrix `A`. -/
theorem munkres_algorithm_correct {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) :
(∃ s₀, IsStart A s₀) ∧
(∀ s₀, IsStart A s₀ → Acc (fun t s => Step s t) s₀) ∧
(∀ s, Reachable A s → s.phase ≠ Phase.done → ∃ t, Step s t) ∧
(∀ s, Reachable A s → s.phase = Phase.done →
∃ σ : Equiv.Perm (Fin n), s.starred = Finset.univ.image (fun r => (σ r, r)) ∧
HeldWolfeCrowder.Assignment.IsOptimalAssignment A σ) := by sorry
end MunkresAlg.Assignment
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.