Convergence Theorem 2 — the additive algorithm terminates with an optimal solution or infeasibility
ProvedBalasAdditive.Convergence.additive_algorithm_convergenceFor every instance of Balas's problem with nonnegative costs, the additive algorithm starting from has no infinite run. Every reachable state before a stopping situation has an allowed next step. At any reachable stopped state, let be the ceiling formed from the generated solutions. Then
Thus the finite algorithm ends with either an optimal feasible solution or a valid infeasibility verdict, exactly the two outcomes of Convergence Theorem 2.
Formalization Note “In a finite number of iterations” is stated as the absence of an infinite transition run together with a successor for every reachable non-stopped state; this excludes a missing algorithm case from counting as termination. The verdict quantifies over all binary assignments, not only generated ones. The ceiling uses an explicit value when no feasible solution has yet been generated, and tied choices remain nondeterministic.
import Mathlib import Definitions.Def_BalasAdditive_Convergence_Algorithm set_option autoImplicit false
namespace BalasAdditive.Convergence
/-- Convergence Theorem 2, p. 533: finite, non-stuck execution and the
optimality or infeasibility verdict at a stop. -/
theorem additive_algorithm_convergence {n m : ℕ} (P : Problem n m) :
(¬ ∃ run : ℕ → State n,
run 0 = init P ∧ ∀ t, Step P (run t) (run (t + 1))) ∧
(∀ σ : State n, Reachable P σ → σ.phase ≠ .stopped → ∃ τ, Step P σ τ) ∧
(∀ σ : State n, Reachable P σ → σ.phase = .stopped →
(ceiling P σ = ⊤ → ∀ J : Finset (Fin n), ¬ P.lp.Feasible J) ∧
(ceiling P σ ≠ ⊤ →
(∃ q, q < σ.history.length ∧ P.lp.Feasible (σ.J q) ∧
(↑(P.lp.cost (σ.J q)) : WithTop ℝ) = ceiling P σ) ∧
(∀ q, q < σ.history.length → P.lp.Feasible (σ.J q) →
(↑(P.lp.cost (σ.J q)) : WithTop ℝ) = ceiling P σ →
P.lp.Optimal (σ.J q)))) := by sorry
end BalasAdditive.Convergence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.