Theorem 3.2.1 — integrality of the bipartite perfect-matching LP relaxation
ProvedMatousekLP.Integrality.perfect_matching_lp_integralLet be an arbitrary finite bipartite graph with real edge weights (of any sign). Consider the LP relaxation of the perfect-matching integer program (3.1):
If this LP relaxation has at least one feasible solution, then it has at least one integral optimal solution , i.e. for every edge and for every feasible of the relaxation. This is an optimal solution for the integer program (3.1) as well.
The theorem says that a maximum-weight perfect matching of a bipartite graph can be found by solving a linear program. It does not assert that every optimal solution of the relaxation is integral.
Formalization Note The conclusion is a vector feasible for (3.1) (hence 0/1) that is optimal among all feasible points of the relaxation, and also, explicitly, among all feasible points of (3.1).
import Mathlib import Definitions.Def_MatousekLP_Integrality_BipartiteGraph import Definitions.Def_MatousekLP_Integrality_PerfectMatchingLP
namespace MatousekLP.Integrality
theorem perfect_matching_lp_integral {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) [DecidableRel G.Adj] (hG : IsBipartite G) (w : G.edgeSet → ℝ)
(hfeas : ∃ x : G.edgeSet → ℝ, IsPMRelaxFeasible G x) :
∃ x : G.edgeSet → ℝ, IsPMIntFeasible G x ∧
(∀ y : G.edgeSet → ℝ, IsPMRelaxFeasible G y → pmObjective G w y ≤ pmObjective G w x) ∧
(∀ y : G.edgeSet → ℝ, IsPMIntFeasible G y → pmObjective G w y ≤ pmObjective G w x) := by sorry
end MatousekLP.Integrality
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.