Theorem 8.3: variable fixing from the Lagrangian bounds, or in every optimal solution
ProvedSupplyChainTheory.variable_fixingbranch-and-boundfacility-locationlagrangian-relaxationoperations-research
Theorem 8.3. Let be an upper bound on (the cost of any feasible solution), let be any multipliers, the benefits (8.13) under and the subproblem value. If in the solution (8.14) to (UFLP-LR), that is , and
then in every optimal solution to (UFLP); if in that solution, that is , and , then in every optimal solution. The two quantities are the subproblem values with forced to and to ; a feasible solution on the other side of the branch costs at least that much, so more than , and cannot be optimal. These tests fix variables before branch-and-bound.
Preamble
import Definitions.Def_SupplyChainTheory_location
Formal statement
namespace SupplyChainTheory
theorem variable_fixing {n m : ℕ} (h : Fin n → ℝ) (c : Fin n → Fin m → ℝ) (f : Fin m → ℝ)
(hm : 0 < m) (lam : Fin n → ℝ) (UB : ℝ) (hUB : uflpOpt h c f ≤ UB) (j : Fin m) :
(0 ≤ benefit h c lam j + f j → UB < zLR h c f lam + (benefit h c lam j + f j) →
∀ x y, UFLPFeasible x y → uflpCost h c f x y = uflpOpt h c f → x j = 0)
∧ (benefit h c lam j + f j < 0 → UB < zLR h c f lam - (benefit h c lam j + f j) →
∀ x y, UFLPFeasible x y → uflpCost h c f x y = uflpOpt h c f → x j = 1) := 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, pp. 280-281, Sect. 8.2.3.7, Theorem 8.3 and its proof, Eq. (8.23)-(8.24)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.