Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1 — feasible better completions avoid inherited cancellations

Proved
BalasAdditive.Convergence.lemma_1

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

implicit-enumerationinteger-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let usu^sus be a solution just generated by the additive algorithm, and let CsC^sCs be the union of cancellation records inherited from earlier generated solutions whose index sets are strict subsets of JsJ_sJs​. If a feasible binary assignment JtJ_tJt​ strictly contains JsJ_sJs​ and has cost below the current ceiling, then

(Jt∖Js)∩Cs=∅.(34)(J_t\setminus J_s)\cap C^s=\varnothing.\tag{34}(Jt​∖Js​)∩Cs=∅.(34)

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 usu^sus was generated. The feasible JtJ_tJt​ 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
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me