Exam Timetable Solver in Answer Set Programming

The problem is declared rather than searched. Exams, rooms, timeslots, student clashes, room capacities and durations are stated as rules and constraints in ASP, and Clingo finds and optimises the calendar — there is no hand-written search anywhere in the system.

Hard and weak constraints are genuinely separated: a hard constraint eliminates an answer set outright, a weak one adds cost. That distinction is what lets the same encoding express “this must never happen” and “avoid this where you can” without collapsing them into one weighted mush.

YAML instances are parsed into ASP facts by a Python front end, and solved calendars come back as TSV. An independent Prolog validator checks the output against the specification, so a calendar is verified by something other than the code that produced it.

A pytest suite of purpose-built instances covers the constraints one at a time — each with an instance designed to be satisfiable, unsatisfiable, or to carry a specific cost — so a regression in one rule fails a named test rather than silently shifting a total.

Experiments were scripted rather than run by hand: a harness sweeps time limits, thread counts, per-constraint configurations and weight settings, writes results to CSV with metadata, and a second script turns those CSVs into the charts below. Any number in the report can be regenerated from the raw run.

Two of the experiments returned nothing, and that is a result too. With a fixed time budget, wall-clock time is pinned to the budget regardless of thread count — 324.7s against 324.8s across one to twelve threads — so parallelism has to be judged on solution quality, not on time, which is what the threads-versus-cost chart measures instead.