Weak integer programming duality:
ProvedLinearOptimization.integer_program_weak_lagrangean_duality(Theorem 11.2, Weak integer programming duality — Bertsimas & Tsitsiklis, p. 495.) In the setting of Section 11.4 (integer program (11.5): minimize subject to , , integer, with , , , , of integer entries; ; ; ): we have
import Definitions.Def_LinearOptimization_IntegerProgram import Definitions.Def_LinearOptimization_LagrangeanDual open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 11.2 (p. 495).** Weak Lagrangean duality for the integer program (11.5): `Z_D ≤ Z_IP` (in `EReal`, hypothesis-free). -/
theorem LinearOptimization.integer_program_weak_lagrangean_duality {m₁ m₂ n : ℕ}
(A : Matrix (Fin m₁) (Fin n) ℤ) (b : Fin m₁ → ℤ) (c : Fin n → ℤ)
(D : Matrix (Fin m₂) (Fin n) ℤ) (d : Fin m₂ → ℤ) :
lagrangeanDualValue (A.map ((↑) : ℤ → ℝ)) (fun i => (b i : ℝ))
(fun j => (c j : ℝ))
(lagrangeanIntegerSet (D.map ((↑) : ℤ → ℝ)) (fun i => (d i : ℝ))) ≤
integerProgramValue (fun j => (c j : ℝ)) (A.map ((↑) : ℤ → ℝ))
(fun i => (b i : ℝ)) (D.map ((↑) : ℤ → ℝ)) (fun i => (d i : ℝ)) := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Fix integer data: matrices () and () over and integer vectors , all cast entrywise into . Let . The statement is the single extended-real inequality
i.e. the Lagrangean dual value obtained by dualizing the constraints with nonnegative multipliers while keeping the integer lattice points of is at most the integer program's optimal value. Degenerate behavior follows the extended-real conventions: if the inner infimum is for every , so both sides are and the inequality holds as ; either side may also be . No further hypotheses (feasibility, boundedness, rank) are imposed.
Confirmed by the mission captain (proposal self-audit).