Proposition 2.2, p. 152 — CT2 has a solution iff column sums are at most p·b_j and row sums at most p·a_i
ProvedTimetabling85.ClassTeacher.prop_2_2bipartite-multigraphedge-coloringp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1timetabling
Let be an requirement matrix of nonnegative integers, a number of days, and , positive integers (the maximum daily loads of the classes and the teachers). Problem CT2 — find nonnegative integers with for all , for all and for all — has a solution if and only if
In edge-colouring terms: the edges of the bipartite multigraph can be coloured with colours so that at most (resp. ) edges at (resp. ) share a colour iff the degree of each node is at most times its bound.
Formalization Note Positivity of and is the paper's hypothesis ("a positive integer"). The statement is for every , including .
Preamble
import Mathlib import Definitions.Def_Timetabling85_ClassTeacher_Problems
Formal statement
namespace Timetabling85.ClassTeacher
/-- Proposition 2.2 (de Werra 1985, p. 152): for positive integers `a i`, `b j`, CT2 has a solution
iff `∑_i r_ij ≤ p b_j` for every `j` and `∑_j r_ij ≤ p a_i` for every `i`. -/
theorem prop_2_2 {m n : ℕ} (R : Fin m → Fin n → ℕ) (p : ℕ) (a : Fin m → ℕ) (b : Fin n → ℕ)
(ha : ∀ i, 0 < a i) (hb : ∀ j, 0 < b j) :
(∃ x : Fin m → Fin n → Fin p → ℕ, IsCT2 R p a b x) ↔
(∀ j, colSum R j ≤ p * b j) ∧ (∀ i, rowSum R i ≤ p * a i) := by sorry
end Timetabling85.ClassTeacher
Source
de Werra, An introduction to timetabling, Eur. J. Oper. Res. 19 (1985), p. 152, Proposition 2.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.