Eq. (8.19):
ProvedSupplyChainTheory.lagrangian_dual_boundsdualityfacility-locationlagrangian-relaxationoperations-research
With the Lagrangian dual value (8.17), for every instance with at least one candidate site,
The right inequality is (8.16) taken over all ; the left is Theorem D.2 of the book, that the Lagrangian dual is at least as tight as the LP relaxation, because for each the subproblem value is bounded by the value of the same Lagrangian over the LP-relaxed set, and LP duality bounds that by . Corollary 8.2 sharpens the left inequality to an equality.
Preamble
import Definitions.Def_SupplyChainTheory_location
Formal statement
namespace SupplyChainTheory
theorem lagrangian_dual_bounds {n m : ℕ} (h : Fin n → ℝ) (c : Fin n → Fin m → ℝ) (f : Fin m → ℝ)
(hm : 0 < m) : uflpLP h c f ≤ zLRbest h c f ∧ zLRbest h c f ≤ uflpOpt h c f := by sorry
end SupplyChainTheory
Source
Lawrence V. Snyder and Zuo-Jun Max Shen, Fundamentals of Supply Chain Theory, 2nd ed., Wiley 2019, DOI 10.1002/9781119584445, p. 275, Sect. 8.2.3.3, Eq. (8.18)-(8.19) ('Combining (8.16) and (8.18), we now know that zLP ≤ zLR ≤ z∗')
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.