§2, pp. 93–94 — assigning each task to a least-cost agent solves (PR), with value
ProvedRossSolandGAP.Bound.cheapest_assignment_solves_PRgeneralized-assignmentinteger-programmingp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider the relaxation (PR) of the generalized assignment problem: minimize subject to for all and . Choose for every task an agent with , and let , for . Then is feasible for (PR), its cost is
and for every feasible for (PR). Consequently for every feasible for (P), whatever the resources and budgets .
This is the starting bound of the algorithm; the knapsack penalties are added to it.
Formalization Note The selection is any function with IsCheapest c a; ties are allowed. The last conjunct (" is a lower bound for (P)") is the paper's "This yields the lower bound", made explicit. Agents and tasks are 0-based (Fin m, Fin n).
Preamble
import Mathlib import Definitions.Def_RossSolandGAP_Bound_Model open Finset
Formal statement
namespace RossSolandGAP.Bound
theorem cheapest_assignment_solves_PR {m n : ℕ} (c : Fin m → Fin n → ℝ) (a : Fin n → Fin m)
(ha : IsCheapest c a) :
FeasiblePR (xPR a) ∧ cost c (xPR a) = Z c a ∧
(∀ x, FeasiblePR x → Z c a ≤ cost c x) ∧
(∀ (r : Fin m → Fin n → ℝ) (b : Fin m → ℝ) (x : Fin m → Fin n → ℝ),
FeasibleP r b x → Z c a ≤ 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, pp. 93-94, §2, last paragraph of p. 93 and the display Z on p. 94
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.