The timetabling solver gap
University timetabling solver constraints grow exponentially with rooms, students, and courses. Manual scheduling is prone to clashes, room capacity overflows, and scheduling inefficiencies.
University Timetabling Solver focuses on constraint programming, automated infeasibility detection, and timetable optimization through Large Neighbourhood Search.
Project Objectives
Formulate university scheduling as a Constraint Programming problem
Detect and repair infeasible timetables automatically
Evaluate included ITC-2019 instances and document solution quality
Expose configurable solve and LNS budgets for instances of different sizes
Build a live interactive dashboard for results visualization
Expose the solver through a FastAPI wrapper for programmatic access
System Design
Browser Client
- •ITC-2019 XML upload
- •Constraint diagnostics visualization
- •Solver configuration controls
- •Schedule and analytics dashboards
ITC-2019 Parser
- •XML instance validation
- •Course and room extraction
- •Student enrollment mapping
- •Constraint preprocessing
FastAPI Wrapper
- •XML parser boundary
- •Solver parameter configuration
- •Timeout-bounded subprocess execution
- •JSON artifact formatting
CP-SAT Solver
- •Multi-objective scoring and candidate evaluation
- •Hard constraints validation
- •Solve time budget handling
- •Feasible incumbent search
LNS Optimizer
- •Destruction neighborhood sizes
- •Incremental repairs search
- •Intermediate quality logging
- •Solve continuation paths
Data Flow Steps
ITC-2019 XML Input
Parses standard instances: rooms, courses, students, time slots, and hard constraints
Infeasibility Detection
Identifies room-capacity bottlenecks and student clash hotspots before solving
CP-SAT Model
Formulates scheduling as CSP with multi-objective scoring and candidate evaluation
LNS Improvement
Large Neighbourhood Search iteratively destroys and repairs solution fragments
Validation
Validates zero student clashes and generates ranked diagnostic recommendations
JSON Output + Dashboard
Structured output consumed by interactive GitHub Pages dashboard
Solver Features
Multi-objective scoring system
CP-SAT optimization engine
Large Neighbourhood Search improvement phase
ITC-2019 benchmark compatibility
FastAPI execution wrapper
Solver Run Simulation
Interactive Solver Simulator
Run the hybrid CP-SAT + LNS optimization sequence live
Solver Results
The solver successfully generates optimized schedules verifying all ITC-2019 rules.
Note: Quality Score 100 is instance-specific (based on included sample files) and does not guarantee optimal performance on all ITC-2019 instances.
API Design
Programmatic access to the CP-SAT and LNS solver wrapper
| Method | Endpoint | Responsibility |
|---|---|---|
| GET | / | Service identification and status check |
| GET | /health | Lightweight health status endpoint |
| POST | /solve | Accepts an ITC-2019 XML file upload, executes the solver in a timeout-bounded subprocess, and returns the solution JSON |
| GET | /docs | Interactive API documentation generated by FastAPI |
Key Decisions
CP-SAT over heuristic-only solver
OR-Tools CP-SAT can return feasible incumbents under a time limit and prove optimality when the search completes
LNS as improvement layer
Pure CP-SAT on large instances is slow; LNS improves solution quality incrementally without full re-solve
ITC-2019 benchmark format
A recognized instance format makes parser behavior and constraint inputs easier to inspect and reproduce
FastAPI wrapper
A thin HTTP boundary reuses the CLI solver path and makes XML-to-JSON execution available to other clients
Visual Showcase
Engineering Challenges
Modeling timetable constraints without exponential variable growth
Naive representation of slots (Room x Time x Class) creates millions of binary variables, causing solver memory exhaustion.
Formulated constraints using integer variables for time slots and room indices instead of sparse binary matrices.
Reduced total decision variables, allowing the solver to generate timetables from structured academic inputs.
Detecting infeasible schedules before optimization
Oversubscribed schedules (e.g., more classes than total room hours) caused solver to search indefinitely for non-existent solutions.
Built a pre-solve diagnostic checker that counts pigeonhole limits and conflicts before launching OR-Tools CP-SAT.
Instantly flags impossible bounds, returning descriptive bottleneck logs to user without initiating solver run.
Balancing solution quality against solver runtime
Getting a mathematically optimal schedule took hours, while users expected interactive feedback within seconds.
Configured the CP-SAT solver with search limits and configured solver time limits and tiered attempts, accepting feasible candidate schedules within the configured time budget.
Good quality schedules returned within the configured solver time limit.
Designing effective destruction and repair neighborhoods for LNS
Standard Large Neighborhood Search (LNS) randomly deleted variables, failing to escape deep local minima on highly constrained datasets.
Designed custom heuristics that selectively destroy classes in over-utilized rooms and repair them using time-slack priority.
Achieved improved objective scores compared to generic solver runs within the same time limit.
Maintaining schedule validity during iterative optimization
Multi-phase scheduling could yield invalid intermediate states that violate hard constraint rules like teacher availability.
Modeled all state updates as transaction-like modifications validated via CP-SAT's internal constraint checker at every iteration.
validated generated outputs against hard constraint rules.
Boundaries & Learnings
Limitations
- •Solve time grows with instance size and depends on the configured time budget
- •Hybrid mode (online/physical) adds constraint complexity not in base ITC-2019
- •No live database integration — inputs are file-based XML
- •Dashboard is read-only — no drag-and-drop manual adjustment
- •Room preference soft constraints are approximated, not exact
Key Learnings
- •Constraint Programming formulation for NP-hard combinatorial problems
- •OR-Tools CP-SAT API — variable domains, constraints, and objective functions
- •Large Neighbourhood Search design patterns for local improvement
- •ITC-2019 problem format and evaluation criteria
- •FastAPI wrapper design and file-upload handling
- •Translating optimization outputs into actionable scheduling insights