Proof of Proposition 2.4, p. 155 — implications of chosen schedules stay inside every timetable that contains them
ProvedTimetabling85.TwoPeriod.closure_subset_of_stablebacktrackingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stable-settimetabling
Let be a graph on the nodes , of teachers in which and are linked for every . Let be a set of pairwise non-adjacent nodes of (a timetable), and let . Then
where is the set of all implications of the choices .
Consequently, if the implications of a set of choices are not pairwise non-adjacent ("for some teacher no schedule can be found"), then no timetable contains those choices. This is what justifies reversing a decision in the limited backtracking.
Preamble
import Mathlib import Definitions.Def_Timetabling85_TwoPeriod_Backtracking
Formal statement
namespace Timetabling85.TwoPeriod
theorem closure_subset_of_stable {n : ℕ} (G : SimpleGraph (Fin n × Bool))
(hpair : ∀ j : Fin n, G.Adj (j, false) (j, true))
(T : Finset (Fin n × Bool)) (hT : G.IsNIndepSet n T)
(S : Finset (Fin n × Bool)) (hS : S ⊆ T) :
closure G S ⊆ T := by sorry
end Timetabling85.TwoPeriod
Source
de Werra, An introduction to timetabling, Eur. J. Oper. Res. 19 (1985), p. 155, Proof of Proposition 2.4 ('one considers all the implications of this choice')
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.