Theorem 1 — an abandoned solution has no better feasible completion
ProvedBalasAdditive.Convergence.abandoned_no_better_completionbranch-and-boundimplicit-enumerationinteger-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Suppose the additive algorithm has abandoned a generated solution while processing iteration (with generated): it has been instructed to check for some in step 5, or to stop. There is no feasible binary assignment strictly containing whose cost is below the current ceiling:
This is the exclusion theorem used to justify the algorithm's abandonment and final verdict.
Formalization Note The printed theorem writes ; the algorithm and proof require . The statement uses the current ceiling and applies only to reachable states. The printed version fails already for , , , : the run (step 4a) stops at step 5a, abandoning , while is feasible, contains strictly, and has .
Preamble
import Mathlib import Definitions.Def_BalasAdditive_Convergence_Algorithm set_option autoImplicit false
Formal statement
namespace BalasAdditive.Convergence
/-- Theorem 1, p. 529, with the current ceiling `z^{*(s)}` in place of
the printed `z^{*(k)}`; the latter is false for the paper's algorithm. -/
theorem abandoned_no_better_completion {n m : ℕ} (P : Problem n m) (σ : State n)
(hr : Reachable P σ) (k : ℕ) (habandoned : Abandoned P σ k) :
¬ ∃ J : Finset (Fin n), P.lp.Feasible J ∧ σ.J k ⊂ J ∧
(↑(P.lp.cost J) : WithTop ℝ) < ceiling P σ := by sorry
end BalasAdditive.Convergence
Source
Balas, An additive algorithm for solving linear programs with zero-one variables, Oper. Res. 13 (1965), p. 529, Theorem 1 (ceiling corrected from z^{*(k)} to z^{*(s)}), DOI 10.1287/opre.13.4.517
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.