Behind "University Course Timetabling AI Copilot":
4D 0-1 MILP Formulation (UCTP) & Coupled Multi-Board Scheduling

01Why University Timetabling Requires Multiple Coupled Boards (UCTP)

In Operations Research (OR), the University Course Timetabling Problem (UCTP)—standardized in benchmarks such as the International Timetabling Competition (ITC-2007 Curriculum-Based Track)—is one of the most heavily studied NP-hard scheduling problems alongside the Nurse Scheduling Problem (NSP).

Unlike an elementary school homeroom where one class stays together in one room, a university department timetable couples three distinct dimensions across 25 weekly periods (Mon–Fri × Periods 1–5): 4 student cohorts (Years 1–4), 10 faculty members (8 full-time + 2 adjuncts), and 7 heterogeneous rooms (large lecture halls, medium rooms, PC labs, and seminar rooms). Moving a single lecture immediately ripples across other cohorts taught by the same professor and other courses competing for the same lecture hall or PC lab.

024D Binary Decision Variables and Core Structural Constraints

Let $C$ be the set of 25 courses, $D = \{\text{Mon}, \text{Tue}, \text{Wed}, \text{Thu}, \text{Fri}\}$ be the days, $P = \{1, 2, 3, 4, 5\}$ be the periods, and $R$ be the 7 rooms. We define a 4D binary variable $x_{c,d,p,r} \in \{0, 1\}$ equal to $1$ if and only if course $c$ is assigned to day $d$, period $p$, and room $r$.

Defining the slot projection $u_{c,d,p} = \sum_{r \in R} x_{c,d,p,r} \in \{0, 1\}$, the core structural constraints are:

03Linearizing Pedagogical & Operational Rules

(A) Consecutive Double-Period Lab Sessions (course_consecutive)

While 2-session lecture courses are normally spread across different days ($\sum_{p \in P} u_{c,d,p} \le 1$), hands-on courses like "Software Design Lab (C12)" often require two consecutive periods on the same day (e.g., Tue Periods 2–3). We introduce binary indicator variables $z_{d,p} \in \{0, 1\}$ for $p \in \{1, 2, 3, 4\}$:

(B) Penalizing Student Hollow Gaps ("Idle Bridge Periods")

To prevent students from having a compulsory class in Period 1, an empty Period 2, and another compulsory class in Period 3, we introduce a non-negative continuous slack variable $\text{gap}_{k,d,p} \ge 0$ for each intermediate period $p \in \{2, 3, 4\}$:

(C) Minimal Perturbation Mode (Preserving Existing Assignments)

When an academic affairs officer adds a single rule mid-planning, reshuffling the entire university timetable is disruptive. When Minimal Perturbation Mode is enabled, each previously assigned session $(c, d^*, p^*, r^*)$ receives a negative objective reward ($-6 \cdot u_{c,d^*,p^*} - 2 \cdot x_{c,d^*,p^*,r^*}$), keeping unchanged courses in place unless mathematically required to move.

04Neuro-Symbolic Architecture: Gemini Nano + WaSHI (HiGHS)

Instead of asking an LLM to guess a timetable (which inevitably violates room capacities or double-books faculty), the copilot separates natural-language understanding from combinatorial optimization:

1. Chrome Built-in AI (Gemini Nano / LanguageModel API): Parses unstructured faculty requests into schema-validated tool calls via responseConstraint.
2. WaSHI + HiGHS (WASM MILP Solver): Solves the 4,420-variable, 1,601-constraint MILP to optimality in ~250 ms and verifies zero constraint violations via model.validateSolution().
3. Two-Pass Elastic Conflict Diagnosis: When user rules conflict (Infeasible), WaSHI relaxes every hard constraint with non-negative slacks under two complementary weight profiles (prefer_structural and prefer_user) to isolate the exact colliding constraints.