Corollary 8.2: for the UFLP,
ProvedSupplyChainTheory.lagrangian_equals_lpCorollary 8.2. For the uncapacitated fixed-charge location problem, the Lagrangian dual value obtained by relaxing the assignment constraints (8.4) equals the LP relaxation value:
The Lagrangian subproblem has the integrality property: for every its optimal value does not change when is relaxed to , since the objective is linear and, after choosing optimally for each , linear in . Lemma D.3 of the book (Geoffrion's theorem) then gives . The book draws the consequence that the Lagrangian bound for the UFLP is exactly as tight as the LP bound, no more, and explains why the method is still used: the subproblem is solved by inspection, and the same scheme extends to nonlinear location models that LP solvers cannot handle.
Formalization Note is the supremum over all real multiplier vectors; the theorem asserts it equals the LP value, which is attained, so the supremum is attained as well.
import Definitions.Def_SupplyChainTheory_location
namespace SupplyChainTheory
theorem lagrangian_equals_lp {n m : ℕ} (h : Fin n → ℝ) (c : Fin n → Fin m → ℝ) (f : Fin m → ℝ)
(hm : 0 < m) : uflpLP h c f = zLRbest h c f := by sorry
end SupplyChainTheory
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.