🧩 Constraint Solving POTD:Problem of the Day: Examination Scheduling

[github-actions[bot]]

Problem Statement

Examination Scheduling is the task of assigning examinations to time slots and rooms while satisfying a complex set of constraints.

Concrete Instance

Consider a university with:

• 6 courses: A, B, C, D, E, F
• 3 time slots: 9 AM, 2 PM, 5 PM (one day)
• 2 rooms: Room 101, Room 102
• Enrollment conflicts:
  • 50 students take both A and B
  • 30 students take both C and D
  • 20 students take both E and F

Constraints:

1. No student can take two exams at the same time (hard)
2. Room capacity: Room 101 holds 80, Room 102 holds 60 (hard)
3. Minimize the spread of exams across the day (soft—prefer shorter exam period)

Goal: Assign each course to a (slot, room) pair such that:

• No conflicts occur
• Room capacities are respected
• The exam period is minimized

Input/Output Specification

Input:

• Set of exams, set of time slots, set of rooms
• Enrollment matrix (which students take which exams)
• Room capacities
• Weights on soft constraints

Output:

• A timetable: exam → (time slot, room)
• Objective value(s): number of violations (if any), exam spread, room utilization

---

Why It Matters

Educational Institutions: Universities and schools must schedule thousands of exams annually while respecting student timetables and resource limits. A poor schedule forces students to take exams back-to-back or creates long gaps, hurting student performance.

Certification Bodies: Large-scale exam providers (SAT, GRE, IELTS) deploy exams across multiple centers with complex room and proctor availability constraints. Efficient scheduling reduces operational costs and candidate inconvenience.

Corporate Training: Companies scheduling competency assessments across multiple centers and time zones face similar constraints at smaller scale.

---

Modeling Approaches

Approach 1: Constraint Programming (CP)

Paradigm: Declarative constraint model with global constraints and propagation.

Decision Variables:

time[i] ∈ {1..T}  for each exam i (time slot assignment)
room[i] ∈ {1..R}  for each exam i (room assignment)

Constraints:

Conflict avoidance:
  For each pair of exams (i, j) with common students:
    time[i] ≠ time[j]

Room capacity:
  For each time slot t and room r:
    count({i : time[i] = t AND room[i] = r AND size[i] > cap[r]}) = 0
    OR sum of exam sizes at (t, r) ≤ cap[r]

Soft constraint (lexicographic ordering):
  Minimize: max(time[i]) - min(time[i])  (exam spread)

Strengths:

• Native support for conflict graph via all-different-like constraints
• Global constraints (cumulative, global cardinality) propagate effectively
• Easy to add/modify soft constraints

Weaknesses:

• Problem size explodes with many exams and slots
• Requires careful modeling of capacity constraints

Approach 2: Mixed-Integer Programming (MIP)

Paradigm: Integer linear optimization with binary and continuous variables.

Decision Variables:

x[i,t,r] ∈ {0,1}  (exam i assigned to slot t and room r)
spread ∈ R+       (auxiliary variable for objective)

Constraints:

Assignment (each exam assigned exactly once):
  Σ_{t,r} x[i,t,r] = 1  for all exams i

Conflict avoidance (big-M):
  Σ_r x[i,t,r] + Σ_r x[j,t,r] ≤ 1 + M·y[i,j]
  where y[i,j] = 1 if exams i,j conflict, else 0

Capacity:
  Σ_i size[i]·x[i,t,r] ≤ cap[r]  for all slots t, rooms r

Span linearization:
  spread ≥ t·Σ_r x[i,t,r] - t_min  for all exams i, slots t

Minimize: spread

Strengths:

• Leverage mature solvers (CPLEX, Gurobi, HiGHS)
• Linear objective and continuous relaxations enable branch-and-bound
• Parallelizable solving

Weaknesses:

• Many binary variables (can be T × R × N for N exams)
• Big-M coefficients must be tuned carefully
• Weak relaxation bounds can slow branch-and-bound

---

Example Model (Pseudo-code)

A simplified MiniZinc model:

enum EXAMS = {A, B, C, D, E, F};
enum SLOTS = {S1, S2, S3};
enum ROOMS = {R101, R102};

array[EXAMS] of int: size = [40, 50, 35, 45, 30, 25];
array[ROOMS] of int: capacity = [80, 60];

array[EXAMS] of var SLOTS: slot;
array[EXAMS] of var ROOMS: room;

% Conflict constraints
constraint alldifferent_on([slot[A], slot[B]]);  % A and B conflict
constraint alldifferent_on([slot[C], slot[D]]);
constraint alldifferent_on([slot[E], slot[F]]);

% Capacity constraints
forall(s in SLOTS, r in ROOMS) (
  sum(i in EXAMS where slot[i] = s /\ room[i] = r)(size[i]) <= capacity[r]
);

% Objective: minimize span
var int: span = max(slot) - min(slot);
solve minimize span;

output ["Timetable:
"] ++
  ["\(i): slot \(slot[i]), room \(room[i])
" | i in EXAMS];

---

Key Techniques

1. Graph Coloring and Conflict Analysis

Model the problem as a conflict graph where exams are nodes and edges represent students taking both. This transforms the core conflict constraint into a vertex coloring problem. Use clique detection to identify highly constrained exam clusters and solve them first.

2. Symmetry Breaking

Room assignments often have symmetries (two rooms of similar capacity are interchangeable). Use symmetry-breaking constraints:

• Order rooms lexicographically for the first exam in each room
• Aggregate exams into capacity-balanced groups pre-assignment

3. Decomposition and Large Neighborhood Search

Split the problem into phases:

1. Slot assignment: Solve the conflict graph coloring without room constraints
2. Room assignment: Assign each slot's exams to rooms (bin packing subproblem)
3. Local optimization: Apply large neighborhood search to swap exams and reduce spread

This two-phase approach scales better than monolithic solving.

---

Challenge Corner

Question: Suppose some exams are soft conflicts (e.g., students prefer not to take two exams in the same slot, but it's allowed with a penalty). How would you model this?

Extension: Real universities have sequential constraints: "Course C's exam cannot be before Course B's exam" (prerequisites, or coordination with lecture schedules). How would you incorporate precedence constraints?

Symmetry Puzzle: Can you express the exam scheduling problem using only a single global constraint? (Hint: think of it as a multi-dimensional bin packing variant.)

---

References

1. Burke, E. K., & Petrovic, S. (2002). "Recent Research Directions in Automated Timetabling." European Journal of Operational Research, 140(2), 266–280.
   A comprehensive survey of exam and lecture timetabling problems and solution approaches.

2. Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier.
   Chapter 7 covers constraint programming for scheduling problems, including timetabling.

3. Qu, R., Burke, E. K., & McCollum, B. (2009). "Adaptive Automated Construction of Hybrid Heuristics for Exam Timetabling and Course Timetabling Problems." European Journal of Operational Research, 198(2), 555–571.
   Modern hybrid approaches combining metaheuristics with constraint-based reasoning.

4. International Timetabling Competition (ITC). (www.itc2019.org/redacted)
   Benchmarks and open instances for examination and course timetabling problems.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 6.83 AIC · ⌖ 5.89 AIC · ⊞ 6K · ◷

• expires on Oct 10, 2026, 4:53 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #65572.