Lemma 1 — feasible better completions avoid inherited cancellations
ProvedBalasAdditive.Convergence.lemma_1implicit-enumerationinteger-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a solution just generated by the additive algorithm, and let be the union of cancellation records inherited from earlier generated solutions whose index sets are strict subsets of . If a feasible binary assignment strictly contains and has cost below the current ceiling, then
This is Lemma 1's exclusion of cancelled indices from any better feasible completion of the current solution.
Formalization Note The state is reachable and is at the start of an iteration, immediately after was generated. The feasible ranges over all binary assignments, whether or not the algorithm generated it.
Preamble
import Mathlib import Definitions.Def_BalasAdditive_Convergence_Algorithm set_option autoImplicit false
Formal statement
namespace BalasAdditive.Convergence
/-- Lemma 1, p. 530, equation (34). -/
theorem lemma_1 {n m : ℕ} (P : Problem n m) (σ : State n)
(hr : Reachable P σ) (hphase : σ.phase = .start)
(J : Finset (Fin n)) (hfeas : P.lp.Feasible J)
(hstrict : σ.latest ⊂ J)
(hcost : (↑(P.lp.cost J) : WithTop ℝ) < ceiling P σ) :
Disjoint (J \ σ.latest) σ.C := by sorry
end BalasAdditive.Convergence
Source
Balas, An additive algorithm for solving linear programs with zero-one variables, Oper. Res. 13 (1965), p. 530, Lemma 1, Eq. (34), DOI 10.1287/opre.13.4.517
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.