🧩 Constraint Solving POTD:Problem of the Day: Course Timetabling

[github-actions[bot]]

Problem Statement

Course timetabling is the task of assigning lectures, tutorials, and exams to time slots and rooms while satisfying hard constraints (must be met) and soft constraints (should be met when possible).

Small Instance: Three Courses, Four Time Slots

• Courses: Mathematics (M), Physics (P), Chemistry (C)
• Time slots: {Monday 9am, Monday 2pm, Tuesday 9am, Tuesday 2pm}
• Rooms: {Room 101, Room 102}
• Instructors: Dr. Smith (teaches M, P), Dr. Jones (teaches C)
• Lectures per course: 2 each

Hard constraints:

• No instructor teaches two courses at the same time
• At most one course per room per time slot
• Each course gets exactly 2 lectures

Soft constraints:

• Prefer not to schedule lectures back-to-back (same room)
• Dr. Jones prefers not to teach on Monday

Task: Find an assignment of courses to (time slot, room) pairs satisfying all hard constraints and minimizing violations of soft constraints.

---

Why It Matters

Educational institutions depend on timetabling to serve thousands of students and faculty each term. A poor schedule creates cascading effects: student conflicts, instructor overload, unused rooms, and student complaints.

Exam scheduling at universities must respect individual student exam timetables (no student takes two exams simultaneously) while minimizing back-to-back exams across days.

Workforce management in airlines, hospitals, and call centers relies on similar principles: staff skill assignments, shift timing, coverage requirements, and personal preferences all interact in complex ways.

---

Modeling Approaches

Approach 1: Constraint Programming (CP)

Decision variables:

• schedule[c, i, t, r]: Boolean indicating whether course c, lecture i, is in time slot t, room r
• time[c, i, t]: Boolean indicating whether lecture i of course c is at time t (aggregated over rooms)

Key constraints (pseudo-code):

foreach course c, lecture i:
    sum_t,r schedule[c, i, t, r] = 1    # each lecture assigned exactly once

foreach instructor instr, time t:
    sum_c,i,r (schedule[c, i, t, r] AND teaches[instr, c]) ≤ 1    # instructor free

foreach time t, room r:
    sum_c,i schedule[c, i, t, r] ≤ 1    # one course per room per slot

# Soft constraints (penalized in objective)
minimize(
    weight_backtoback * (# back-to-back lectures) +
    weight_preference * (# instructor preference violations)
)

Strengths: Declarative modeling; strong global constraint propagation (e.g., alldifferent, cumulative); expresses hard and soft constraints naturally.

Weaknesses: May require careful constraint ordering; solving large instances can be slow without good search heuristics.

---

Approach 2: Mixed Integer Programming (MIP)

Decision variables:

• x[c, i, t, r] ∈ {0, 1}: 1 if course c, lecture i, assigned to slot t, room r
• slack[s] ≥ 0: Penalty for soft constraint s

Key constraints (mathematical notation):

∑_{t,r} x[c, i, t, r] = 1    ∀c, i

∑_{c: teaches[instr, c]=1} ∑_r x[c, i, t, r] ≤ 1    ∀instr, t

∑_c ∑_i x[c, i, t, r] ≤ 1    ∀t, r

Minimize: ∑_s weight[s] · slack[s]

Strengths: Mature LP/MIP solvers (CPLEX, Gurobi); integrates continuous relaxations for bounds; exploits structure via cutting planes.

Weaknesses: Large integer variable sets; global constraints must be reformulated as linear inequalities (verbose); soft constraints need auxiliary variables.

---

Approach 3: Local Search / Metaheuristic

Start with a greedy assignment, then repeatedly:

1. Select a course or lecture to reschedule
2. Propose a new time slot / room
3. Accept if: cost decreases, or accept with probability proportional to cost increase (simulated annealing)

Strengths: Fast for medium-sized instances; naturally handles soft constraints; scales well to real-world sizes.

Weaknesses: May get stuck in local optima; no optimality guarantee; requires careful tuning of move operators and temperature schedules.

---

Example Model (MiniZinc)

int: n_courses = 3;
int: n_slots = 4;
int: n_rooms = 2;
int: n_lectures = 2;

% Binary: (course, lecture, slot, room)
array[1..n_courses, 1..n_lectures, 1..n_slots, 1..n_rooms] of var 0..1: schedule;

% Each lecture assigned exactly once
constraint forall(c in 1..n_courses, i in 1..n_lectures)(
    sum(t in 1..n_slots, r in 1..n_rooms)(schedule[c, i, t, r]) = 1
);

% At most one course per room per slot
constraint forall(t in 1..n_slots, r in 1..n_rooms)(
    sum(c in 1..n_courses, i in 1..n_lectures)(schedule[c, i, t, r]) <= 1
);

% Instructor conflict: Dr. Smith teaches courses 1,2; Dr. Jones teaches course 3
constraint forall(t in 1..n_slots)(
    sum(i in 1..n_lectures)(schedule[1, i, t, 1] + schedule[1, i, t, 2]) +
    sum(i in 1..n_lectures)(schedule[2, i, t, 1] + schedule[2, i, t, 2]) <= 1
);

solve minimize 0;  % Feasibility for this example
output[show(schedule)];

---

Key Techniques

1. Constraint Propagation & Global Constraints

The alldifferent and cumulative global constraints enforce instructor and room constraints efficiently via:

• Arc consistency algorithms (e.g., AC-3): prune variable domains before search
• Resource reasoning: track cumulative load (instructor hours per day)

For large timetables, propagation often proves infeasibility early, avoiding futile search.

2. Symmetry Breaking

Timetables have inherent symmetries: swapping two empty rooms or two identical time slots generates equivalent solutions.

Techniques:

• Order time slots lexicographically: if lecture 1 and lecture 2 of the same course are unordered, enforce lecture_1_slot ≤ lecture_2_slot.
• Group identical instructors: assume instructor 1 gets the "first" slot among a symmetry class.

Symmetry breaking can reduce search space by orders of magnitude.

3. Hierarchical Constraint Relaxation

Prioritize constraints:

1. Level 1 (hard): No instructor double-booking, no room conflicts
2. Level 2 (soft): Minimize back-to-back lectures
3. Level 3 (soft): Respect preferences

Solve level 1 to feasibility, then optimize level 2 subject to level 1, etc. This avoids infeasible branches early.

---

Challenge Corner

Can you model this with fewer variables?

Instead of a 4-indexed boolean array schedule[c, i, t, r], could you use a 2-indexed assignment: lecture_slot[lecture_id] mapping each lecture to a (slot, room) pair? What advantage or disadvantage would this bring for expressing instructor and room conflicts?

What symmetry-breaking constraints would help?

How would you add symmetry-breaking to rule out time-slot permutations that don't materially affect the quality of the schedule? Hint: think about which lectures are interchangeable and impose a canonical ordering.

Handling robustness:

Real timetables need to accommodate last-minute cancellations and room changes. How would you model a "buffer" or "flexibility margin" in your solution to permit local modifications without breaking constraints?

---

References

1. Müller, T. (2009). Constraint-based timetabling. In: Recent Advances in Constraints (LNCS 5655). A concise survey of CP-based approaches with practical examples from university scheduling.

2. Kingston, J. H. (2013). Educational timetabling. In: Handbook of Constraint Programming (pp. 857–875). Comprehensive overview of problem variants and solving techniques.

3. Cambazard, H., & O'Sullivan, B. (2015). Propagating the cumulative constraint combining control and automaton-based reasoning. In: AAAI. Covers advanced propagation for resource constraints essential to scheduling.

4. Ceschia, S., & Schaerf, A. (2010). Local search for quantum SAT and related combinatorial optimization problems. Annals of Operations Research, 176(1). Explores metaheuristic techniques for large-scale instances.

Generated by 🧩 Constraint Solving — Problem of the Day · 10.3 AIC · ⌖ 13.7 AIC · ⊞ 5.7K · ◷

• expires on Jun 30, 2026, 4:24 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 #41216.