Lemma 8.2.4 — a TU linear program with integral right-hand side has an integral optimum
ProvedMatousekLP.Integrality.tu_integral_optimalConsider a linear program with nonnegative variables and inequalities of the form
where is a real matrix, and . If is totally unimodular and the linear program has an optimal solution, then it also has an integral optimal solution .
This lemma is what makes integer programs with a totally unimodular constraint matrix solvable by linear programming: the integrality constraints can be dropped without changing the optimum. The objective vector need not be integral.
Formalization Note "Optimal solution" is a feasible point whose objective value is at least that of every feasible point. The integral optimal solution is given as a vector whose real image is optimal.
import Mathlib import Definitions.Def_MatousekLP_Integrality_InequalityLP
namespace MatousekLP.Integrality
theorem tu_integral_optimal {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℤ)
(c : Fin n → ℝ) (hA : A.IsTotallyUnimodular)
(hopt : ∃ x : Fin n → ℝ, IsOptimalIneq A (fun i => (b i : ℝ)) c x) :
∃ z : Fin n → ℤ, IsOptimalIneq A (fun i => (b i : ℝ)) c (fun j => (z j : ℝ)) := by sorry
end MatousekLP.Integrality
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.