§2, p. 95 — any lower bound on (PR_λ) is a lower bound for (P)
ProvedRossSolandGAP.Bound.lagrangean_bound_valid_for_Pgeneralized-assignmentinteger-programminglagrangean-relaxationp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix multipliers , one for each assignment constraint . The Lagrangean relaxation is
Every feasible for (P) is feasible for (PR), and there its (PR) objective equals its (P) objective. Hence, if a real number satisfies the (PR) objective of every (PR)-feasible , then for every feasible for (P).
This is why the bound "provided by (PR)" is a valid bound for (P), whatever the multipliers.
Preamble
import Mathlib import Definitions.Def_RossSolandGAP_Bound_Model open Finset
Formal statement
namespace RossSolandGAP.Bound
theorem lagrangean_bound_valid_for_P {m n : ℕ} (c r : Fin m → Fin n → ℝ) (b : Fin m → ℝ)
(lam : Fin n → ℝ) :
(∀ x, FeasibleP r b x → FeasibleLag r b x ∧ lagObj c lam x = cost c x) ∧
∀ L : ℝ, (∀ x, FeasibleLag r b x → L ≤ lagObj c lam x) →
∀ x, FeasibleP r b x → L ≤ cost c x := by sorry
end RossSolandGAP.Bound
Source
Ross & Soland, A Branch and Bound Algorithm for the Generalized Assignment Problem, Mathematical Programming 8, 1975, p. 95, §2, first two paragraphs and (PR_λ); p. 96, second paragraph, last sentence
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.