Lagrangean dual equals the LP over the convex hull of
ProvedLinearOptimization.lagrangean_dual_eq_lp_over_hullconvex-hulldualityinteger-programminglagrangean-duality
(Theorem 11.4, GOAL — Bertsimas & Tsitsiklis, p. 496, the central result of Section 11.4.) In the setting of Section 11.4 (integer program (11.5): minimize subject to , , integer, with , , , , of integer entries; ; for ; ):
the optimal value of the Lagrangean dual is equal to the optimal cost of the following linear programming problem (11.9):
where is the convex hull of the set .
Preamble
import Mathlib.Analysis.Convex.Hull
import Definitions.Def_LinearOptimization_IntegerProgram
import Definitions.Def_LinearOptimization_LagrangeanDual
open Matrix
/-- **Bertsimas & Tsitsiklis, Theorem 11.4 (p. 496).** The Lagrangean dual equals the linear
program over the convex hull of `X`:
`Z_D = min {c'x | Ax ≥ b, x ∈ CH(X)}` (as `EReal` values), provided
`X = ∅` or the right-hand LP is feasible. -/
Formal statement
theorem LinearOptimization.lagrangean_dual_eq_lp_over_hull {m₁ m₂ n : ℕ}
(A : Matrix (Fin m₁) (Fin n) ℤ) (b : Fin m₁ → ℤ) (c : Fin n → ℤ)
(D : Matrix (Fin m₂) (Fin n) ℤ) (d : Fin m₂ → ℤ)
(hguard :
lagrangeanIntegerSet (D.map ((↑) : ℤ → ℝ)) (fun i => (d i : ℝ)) = ∅ ∨
{x : Fin n → ℝ | (fun i => (b i : ℝ)) ≤ (A.map ((↑) : ℤ → ℝ)).mulVec x ∧
x ∈ convexHull ℝ (lagrangeanIntegerSet (D.map ((↑) : ℤ → ℝ))
(fun i => (d i : ℝ)))}.Nonempty) :
lagrangeanDualValue (A.map ((↑) : ℤ → ℝ)) (fun i => (b i : ℝ))
(fun j => (c j : ℝ))
(lagrangeanIntegerSet (D.map ((↑) : ℤ → ℝ)) (fun i => (d i : ℝ))) =
lpValue (fun j => (c j : ℝ))
{x : Fin n → ℝ |
(fun i => (b i : ℝ)) ≤ (A.map ((↑) : ℤ → ℝ)).mulVec x ∧
x ∈ convexHull ℝ (lagrangeanIntegerSet (D.map ((↑) : ℤ → ℝ))
(fun i => (d i : ℝ)))} := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 11.4, p. 496