Linear programming has a complete duality theory; integer programming does not — and the Lagrangean dual measures exactly how far duality reaches. This mission formalizes the duality theory of integer programming from Section 11.4 of Bertsimas–Tsitsiklis, built on the general linear programming duality of Section 4.10. For the integer program
with integer data, the complicating constraints are dualized with multipliers over the tractable set : the dual function is
and the Lagrangean dual is . Weak duality (Theorem 11.2) always holds, but strong duality can fail. The convex hull of the integer points of a polyhedron with integer data is itself a polyhedron (Theorem 11.3, Meyer's theorem), and the capstone — Theorem 11.4, the central result of Section 11.4 — identifies the Lagrangean dual exactly: equals the optimal cost of the linear program
. This is the geometric explanation of the strength of Lagrangean relaxation, yields the bound ordering , and Corollary 11.1 characterizes exactly when the bounds collapse. The polyhedral engine is the general weak/strong duality pair (Theorems 4.17/4.18) over a primal s.t. , , and the formulation-strength comparison of Theorem 10.1 supplies the motivating principle that tighter relaxations of the same integer set give sharper bounds.
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
(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 .
No open leaves. Every sub-goal is proved or awaiting decomposition.