§2.1, p. 153 — the minimum number of days for CT2 is max(max_j ⌈Σ_i r_ij/b_j⌉, max_i ⌈Σ_j r_ij/a_i⌉)
ProvedTimetabling85.ClassTeacher.min_daysedge-coloringminimum-daysp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1timetabling
Let be an requirement matrix of nonnegative integers and , positive integers. Put
(an empty maximum being ). Then for every number of days , problem CT2 with daily bounds , has a solution over days if and only if .
So days suffice and no smaller number of days does: is the minimum number of days needed, as the paper states.
Formalization Note The "minimum" is stated as the equivalence "solvable over days iff ", which says both that is feasible and that every smaller is infeasible, without an sInf over a possibly empty set.
Preamble
import Mathlib import Definitions.Def_Timetabling85_ClassTeacher_Problems
Formal statement
namespace Timetabling85.ClassTeacher
/-- The minimum number of days (de Werra 1985, §2.1, p. 153): for positive `a i`, `b j`, CT2 is
solvable over `p` days exactly when `p ≥ minDays R a b`. -/
theorem min_days {m n : ℕ} (R : Fin m → Fin n → ℕ) (a : Fin m → ℕ) (b : Fin n → ℕ)
(ha : ∀ i, 0 < a i) (hb : ∀ j, 0 < b j) (p : ℕ) :
(∃ x : Fin m → Fin n → Fin p → ℕ, IsCT2 R p a b x) ↔ minDays R a b ≤ p := by sorry
end Timetabling85.ClassTeacher
Source
de Werra, An introduction to timetabling, Eur. J. Oper. Res. 19 (1985), p. 153, §2.1, display for the minimum number of days p
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.