Lax Lean Archive

While this submission is a draft, it cannot be used by other submissions.

Linear Programming: Duality, Certificates, and Polynomial-Time Optimization

lax-109476·formalized by Édouard Bonnet and Codex 6.1 @EdouardBonnet·created ·GitHub @0a04260·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    This submission treats finite real linear programs in the form max⁡{cTx:Ax≤b, x≥0}\max\{c^T x:Ax\le b,\ x\ge0\} and their nonnegative-multiplier duals. The mathematical concepts include weak and strong duality, complementary slackness, primal attainment, Farkas' alternative, and certificates of unboundedness. Exact rational certificates cover optimality, infeasibility, and unboundedness of rational programs optimized over real variables. The elimination and Farkas proofs adapt Jyotirmoy Bhattacharya's MIT-licensed farkas_lean formalization.

    The algorithmic scope is one uniform exact polynomial-time solver, measured in the binary size of the rational input and using the registered word-RAM model of lax-808846 through the polynomial-time predicate of lax-759944. The solver returns the encoding of the certificate that validates its answer. Polynomial-size certificate existence is proved independently. The solver uses the rational ellipsoid method and exact certificate recovery.

    Concepts

    Concept map
    25 concepts
    100%
    Proven claimDefinitionThis submissionOther submissionA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.

    Proofs

    Proof networkview on GitHub

    100%
    assumptions conclusionProven claimClaim from this submissionProof — open large view for details
    Proof list

    Lean sources for these proofs: proofs/ on GitHub

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    100%
    This submissionOther submissionA → B: B's concepts build on AA → B: only B's proofs build on A

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-109476,
  author = {Édouard Bonnet and Codex 6.1},
  title = {Linear Programming: Duality, Certificates, and Polynomial-Time Optimization},
  year = {2026},
  howpublished = {Lax Archive, lax-109476},
  url = {https://laxarchive.org/lax-109476/},
  note = {draft},
}

    References

    1. Jyotirmoy Bhattacharya. Farkas Lean: Theorems of the Alternative via Fourier–Motzkin Elimination. 2026. MIT-licensed Lean proof; revision 30c319dd52ca89cfa82a68352b1f39f4f3026fc2. github.com/jmoy/farkas_lean
    2. Alexander Schrijver. Theory of Linear and Integer Programming. Wiley, 1986.
    3. Leonid G. Khachiyan. A Polynomial Algorithm in Linear Programming. Doklady Akademii Nauk SSSR 244(5):1093–1096, 1979. English translation: Soviet Mathematics Doklady 20, 191–194. mathnet.ru/eng/dan42319

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…