§3.2, p. 17 — for 0/1 slot assignments the relaxed objective (19) equals the objective with (17)
ProvedSkutellaCQP.RelDates.zqp_slotIndp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quadratic-programmingschedulingtime-slots
Let be any assignment of jobs to time slots and its 0/1 vector ( iff ). Then the objective of the quadratic programming relaxation at , with completion times (19) and slot starts (15)–(16), equals the objective of the integer program, with completion times (17):
This is why the quadratic program is a relaxation: for integral the factor equals , and the right-hand side of (17) "is the sum of these expressions over all time slots weighted by ; it is thus equal to the completion time of ".
Formalization Note. Stated for every slot assignment, feasible or not; standing assumptions are hypotheses.
Preamble
import Mathlib import Definitions.Def_SkutellaCQP_RelDates_Setting
Formal statement
namespace SkutellaCQP.RelDates
open Finset
/-- p. 17: for a 0/1 slot assignment, the objective of the quadratic programming relaxation
(with (19)) equals the objective with the completion times (17). -/
theorem zqp_slotInd {m n : ℕ} (p : Fin m → Fin n → ℝ) (w : Fin n → ℝ) (r : Fin m → Fin n → ℝ)
(hp : ∀ i j, 0 < p i j) (hw : ∀ j, 0 ≤ w j) (hr : ∀ i j, 0 ≤ r i j)
(τ : Fin n → Fin m × Fin n) :
ZQPrel p w r (slotInd τ) = ∑ j, w j * Cslot p w r τ j := by sorry
end SkutellaCQP.RelDates
Source
Skutella, Convex quadratic and semidefinite programming relaxations in scheduling, J. ACM 48 (2001), p. 17, §3.2, paragraph after (14)–(18), and (19)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.