Proof of Proposition 2.4, p. 155 — no need to backtrack beyond the last decision
ProvedTimetabling85.TwoPeriod.autarkybacktrackingp2o-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 that is closed under implications, . Then
This is the argument by which de Werra shows that, once both decisions and for a teacher lead to a contradiction, no timetable exists at all: the permanent decisions taken earlier never need to be revisited, because the subproblem of the teachers not yet scheduled is independent of them.
Preamble
import Mathlib import Definitions.Def_Timetabling85_TwoPeriod_Backtracking
Formal statement
namespace Timetabling85.TwoPeriod
theorem autarky {n : ℕ} (G : SimpleGraph (Fin n × Bool))
(hpair : ∀ j : Fin n, G.Adj (j, false) (j, true))
(A : Finset (Fin n × Bool)) (hA : G.IsIndepSet (A : Set (Fin n × Bool)))
(hclosed : closure G A = A) :
(∃ T : Finset (Fin n × Bool), G.IsNIndepSet n T) ↔
∃ T : Finset (Fin n × Bool), A ⊆ T ∧ G.IsNIndepSet n 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 ('Let us now show that when decisions x_j and x̄_j have been examined … Hence the problem itself has no timetable.')
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.