Convergence Theorem 2(b) — no solution is generated twice
ProvedBalasAdditive.Convergence.no_solution_twiceinteger-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1termination
At every reachable state of the additive algorithm, the generated assignments are pairwise distinct:
This is part (b) of the proof of the convergence theorem and supplies finiteness of the sequence of generated solutions because there are only finitely many binary assignments.
Formalization Note Equality of assignments is equality of their index sets , since the slacks and objective value are determined by those sets.
Preamble
import Mathlib import Definitions.Def_BalasAdditive_Convergence_Algorithm set_option autoImplicit false
Formal statement
namespace BalasAdditive.Convergence
/-- Proof of Convergence Theorem 2, part (b), p. 533. -/
theorem no_solution_twice {n m : ℕ} (P : Problem n m) (σ : State n)
(hr : Reachable P σ) :
(σ.history.map Record.J).Nodup := by sorry
end BalasAdditive.Convergence
Source
Balas, An additive algorithm for solving linear programs with zero-one variables, Oper. Res. 13 (1965), p. 533, proof of Convergence Theorem 2, part (b), DOI 10.1287/opre.13.4.517
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.