Weak integer programming duality:
ProvedLinearOptimization.integer_program_weak_lagrangean_dualitydualityinteger-programminglagrangean-dualityweak-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
Preamble
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). -/
Formal statement
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
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 11.2, p. 495