Constraint Programming with OR-Tools

1 Introduction: Why Constraint Programming?

In many real-world scenarios, we often face problems that involve making a series of decisions subject to a set of constraints. For example, assigning employees to shifts, organizing school timetables, or optimizing routes for delivery services. These are known as combinatorial optimization problems, and they can be quite challenging to solve with brute force or simple heuristics.

This is where constraint programming (CP) comes in — a paradigm designed for solving such problems efficiently. Google’s OR-Tools is a powerful open-source toolkit that provides a constraint solver along with other optimization engines. In this article, we’ll explore how to use OR-Tools in Python to model and solve a scheduling problem with hard constraints.

Our example: Assigning subjects to weekly time slots in classrooms, where each subject has a required number of hours, and subjects must not overlap within the same classroom.

Let’s dive in!

2 Defining the Scheduling Problem

We are given a list of subjects and classrooms. Each subject has a required number of hours per week. Our goal is to assign subjects to weekly time slots such that:

1. Each subject gets exactly the number of hours it requires.
2. Each classroom has only one subject per slot.

Let’s define our subjects and classrooms:

subjects = {
    "PAI": {"hour": 2},
    "Al-Qur'an": {"hour": 3},
    "Olahraga": {"hour": 2},
}

classrooms = ["Kelas1_C0", "Kelas1_C1"]

weekdays = ["Senin", "Selasa", "Rabu", "Kamis", "Jumat"]
hours = ["07.00", "08.00", "09.00", "10.00", "11.00", "13.00"]
slots = [(d, h) for d in weekdays for h in hours]

3 Building the Constraint Model

We’ll use cp_model from OR-Tools to define our variables and constraints.

from ortools.sat.python import cp_model

model = cp_model.CpModel()

# Variable: is_subject_assigned[(classroom, subject, slot)] = 1 if subject is scheduled in that slot
is_subject_assigned = {}
for cls in classrooms:
    for subj in subjects:
        for slot in slots:
            is_subject_assigned[(cls, subj, slot)] = model.NewBoolVar(f"{cls}_{subj}_{slot}")

4 Adding Constraints to the Model

4.1 1. Each subject must be assigned the exact number of required hours:

subject_slots_per_classroom_subject = {}
for cls in classrooms:
    for subj, subject in subjects.items():
        assigned_slots = [is_subject_assigned[(cls, subj, slot)] for slot in slots]
        var = model.NewIntVar(0, len(slots), f"hours_{cls}_{subj}")
        model.Add(var == sum(assigned_slots))
        model.Add(var == subject["hour"])
        subject_slots_per_classroom_subject[(cls, subj)] = var

4.2 2. Each classroom can only have one subject per slot:

for cls in classrooms:
    for slot in slots:
        one_subject_per_slot = [is_subject_assigned[(cls, subj, slot)] for subj in subjects]
        model.Add(sum(one_subject_per_slot) <= 1)

5 Solving the Model

Now we’ll solve the model and print the schedule if it exists.

solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.FEASIBLE or status == cp_model.OPTIMAL:
    for cls in classrooms:
        print(f"\nSchedule for {cls}:")
        for day in weekdays:
            print(f"  {day}:")
            for hour in hours:
                slot = (day, hour)
                subject_found = False
                for subj in subjects:
                    if solver.Value(is_subject_assigned[(cls, subj, slot)]) == 1:
                        print(f"    {hour}: {subj}")
                        subject_found = True
                if not subject_found:
                    print(f"    {hour}: -")
else:
    print("No solution found.")

Schedule for Kelas1_C0:
  Senin:
    07.00: -
    08.00: Al-Qur'an
    09.00: Al-Qur'an
    10.00: -
    11.00: -
    13.00: -
  Selasa:
    07.00: -
    08.00: -
    09.00: -
    10.00: -
    11.00: -
    13.00: Olahraga
  Rabu:
    07.00: -
    08.00: PAI
    09.00: -
    10.00: -
    11.00: -
    13.00: -
  Kamis:
    07.00: -
    08.00: -
    09.00: -
    10.00: -
    11.00: -
    13.00: -
  Jumat:
    07.00: Al-Qur'an
    08.00: PAI
    09.00: -
    10.00: -
    11.00: Olahraga
    13.00: -

Schedule for Kelas1_C1:
  Senin:
    07.00: -
    08.00: -
    09.00: -
    10.00: -
    11.00: -
    13.00: -
  Selasa:
    07.00: -
    08.00: -
    09.00: -
    10.00: Al-Qur'an
    11.00: -
    13.00: -
  Rabu:
    07.00: -
    08.00: PAI
    09.00: -
    10.00: -
    11.00: -
    13.00: -
  Kamis:
    07.00: Al-Qur'an
    08.00: -
    09.00: -
    10.00: Olahraga
    11.00: Olahraga
    13.00: Al-Qur'an
  Jumat:
    07.00: -
    08.00: -
    09.00: -
    10.00: -
    11.00: -
    13.00: PAI

6 Sample Output

Here’s an example output for Kelas1_C0:

Schedule for Kelas1_C0:
  Senin:
    07.00: PAI
    08.00: Al-Qur'an
    09.00: Al-Qur'an
    ...

(Your results may vary based on how the solver assigns time slots.)

7 Conclusion

We’ve just modeled a simple weekly scheduling problem using constraint programming with OR-Tools. We:

• Defined subjects and classrooms
• Created binary decision variables
• Applied hard constraints for hours and exclusivity
• Solved and printed the solution

This is only scratching the surface — you can add more constraints like teacher availability, subject preferences, or soft constraints (e.g., minimizing gaps). Constraint programming gives you a powerful, declarative way to solve such scheduling challenges.

7.1 🔗 Resources

• Google OR-Tools Documentation
• OR-Tools Python Examples
• MiniZinc – another popular CP system

Let me know if you’d like to expand this tutorial to cover optimization goals or soft constraints!