Chapter 29 — Linear Programming

This is the canonical CLRS fourth-edition chapter guide during the migration period.

Current source

Sections 29.1--29.3 are native fourth-edition sections (standard and slack forms, formulating problems as linear programs, and duality), imported directly from Section 29.1, Section 29.2, and Section 29.3. The duality development builds on the online simplex machinery (legacy Section 29.3), and the difference-constraints bridge imports the fourth-edition single-source-shortest-paths sources (Chapter 22). Declarations keep their current namespaces; the third-edition-numbered imports CLRSLean.Chapter_29 and CLRSLean.Chapter_29.Section_29_* forward to these sources.

Implementation details

The supporting implementation pages remain available outside the main sidebar:

• Standard-Form Definitions

• Canonical Slack Variables

• Standard/Slack Equivalence

• General-Form Normalization

• Canonical Solver Wrapper

• Finite Network Model

• Shortest Paths as an LP

• Maximum Flow as an LP

• Minimum-Cost Flow as an LP

• Multicommodity Flow as an LP

• Dual Feasibility

• Weak Duality

• Primal and Dual Optimality

• Complementary-Slackness Gap Identity

• Terminal Dual Certificates

• Dictionary/Primal Bridge

• Strong Duality

• Complementary-Slackness Theorem

• General Strong Duality

Coverage boundary

The native sections supply the represented fourth-edition linear-programming sections (§29.1 formulations and algorithms, §29.2 formulating problems, §29.3 duality with Theorems 29.8--29.10). The detailed simplex algorithm (legacy Section 29.3) and the initial basic feasible solution (legacy Section 29.5) are retained as supplementary online material (reachable through CLRSLean.OnlineMaterial).

See docs/clrs-fourth-edition-map.csv for the section-level mapping and docs/migrations/clrs4.md for compatibility and deprecation policy.