Theorem 8.1: solves (UFLP-LR) and
ProvedSupplyChainTheory.lagrangian_subproblemfacility-locationinteger-programminglagrangian-relaxationoperations-research
Theorem 8.1. For any multipliers , let and set if and otherwise (8.14), and if and and otherwise (8.15). Then is feasible and optimal for the Lagrangian subproblem (UFLP-LR), and its objective value, the optimal value , is
The subproblem decomposes by facility: opening lets every customer with negative reduced cost be assigned to it, so is worth opening exactly when its benefit outweighs its fixed cost. Customers may end up assigned to no facility or to several, since (8.4) has been relaxed.
Preamble
import Definitions.Def_SupplyChainTheory_location
Formal statement
namespace SupplyChainTheory
theorem lagrangian_subproblem {n m : ℕ} (h : Fin n → ℝ) (c : Fin n → Fin m → ℝ) (f : Fin m → ℝ)
(lam : Fin n → ℝ) :
LagrFeasible (lagrX h c f lam) (lagrY h c f lam)
∧ lagrObjective h c f lam (lagrX h c f lam) (lagrY h c f lam)
= ∑ j, min 0 (benefit h c lam j + f j) + ∑ i, lam i
∧ zLR h c f lam = ∑ j, min 0 (benefit h c lam j + f j) + ∑ i, lam i := 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. 274, Sect. 8.2.3.2, Theorem 8.1, Eq. (8.13)-(8.15)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.