OptaPy - OptaPlanner in Python

OptaPy is an AI constraint solver for Python to optimize the Vehicle Routing Problem, Employee Rostering, Maintenance Scheduling, Task Assignment, School Timetabling, Cloud Optimization, Conference Scheduling, Job Shop Scheduling, Bin Packing and many more planning problems.

OptaPy wraps the OptaPlanner engine internally, but using OptaPy in Python is significantly slower than using OptaPlanner in Java or Kotlin.

WARNING: OptaPy is an experimental technology. It is at least 20 times slower than using OptaPlanner in Java or Kotlin.

What is OptaPlanner?

OptaPlanner is an AI constraint solver. It optimizes planning and scheduling problems, such as the Vehicle Routing Problem, Employee Rostering, Maintenance Scheduling, Task Assignment, School Timetabling, Cloud Optimization, Conference Scheduling, Job Shop Scheduling, Bin Packing and many more. Every organization faces such challenges: assign a limited set of constrained resources (employees, assets, time and/or money) to provide products or services. OptaPlanner delivers more efficient plans, which reduce costs and improve service quality.

Constraints apply on plain domain objects and can call existing code. There’s no need to input constraints as mathematical equations. Under the hood, OptaPlanner combines sophisticated Artificial Intelligence optimization algorithms (such as Tabu Search, Simulated Annealing, Late Acceptance and other metaheuristics) with very efficient score calculation and other state-of-the-art constraint solving techniques.

An Example: School Timetabling

Model the domain objects and constraints

The goal is to assign each lesson to a time slot and a room. The model is divided into four kind of objects

Problem Facts

Problem facts are facts about the problem. As such, they do not change during solving (and thus cannot have any planning variables). An example problem fact is shown below:

In [1]:
from optapy import problem_fact, planning_id

@problem_fact
class Room:
    def __init__(self, id, name):
        self.id = id
        self.name = name

    @planning_id
    def get_id(self):
        return self.id

    def __str__(self):
        return f"Room(id={self.id}, name={self.name})"

The @problem_fact decorator creates a Java class for Room, which allows it to be used in constraints. The @planning_id decorator tells OptaPlanner that it can use that method for identifying identifical pairs. It is only required if you use fromUniquePair on the class in a constraint.

The code for the Timeslot probelm fact is shown below:

In [2]:
@problem_fact
class Timeslot:
    def __init__(self, id, day_of_week, start_time, end_time):
        self.id = id
        self.day_of_week = day_of_week
        self.start_time = start_time
        self.end_time = end_time

    @planning_id
    def get_id(self):
        return self.id

    def __str__(self):
        return (
                f"Timeslot("
                f"id={self.id}, "
                f"day_of_week={self.day_of_week}, "
                f"start_time={self.start_time}, "
                f"end_time={self.end_time})"
        )

Planning Entities

During a lesson, represented by the Lesson class, a teacher teaches a subject to a group of students, for example, Math by A.Turing for 9th grade or Chemistry by M.Curie for 10th grade. If a subject is taught multiple times per week by the same teacher to the same student group, there are multiple Lesson instances that are only distinguishable by id. For example, the 9th grade has six math lessons a week.

During solving, OptaPlanner changes the timeslot and room fields of the Lesson class, to assign each lesson to a time slot and a room. Because OptaPlanner changes these fields, Lesson is a planning entity. Here is how we would write it in Python:

In [3]:
from optapy import planning_entity, planning_variable

@planning_entity
class Lesson:
    def __init__(self, id, subject, teacher, student_group, timeslot=None, room=None):
        self.id = id
        self.subject = subject
        self.teacher = teacher
        self.student_group = student_group
        self.timeslot = timeslot
        self.room = room

    @planning_id
    def get_id(self):
        return self.id

    @planning_variable(Timeslot, ["timeslotRange"])
    def get_timeslot(self):
        return self.timeslot

    def set_timeslot(self, new_timeslot):
        self.timeslot = new_timeslot

    @planning_variable(Room, ["roomRange"])
    def get_room(self):
        return self.room

    def set_room(self, new_room):
        self.room = new_room

    def __str__(self):
        return (
            f"Lesson("
            f"id={self.id}, "
            f"timeslot={self.timeslot}, "
            f"room={self.room}, "
            f"teacher={self.teacher}, "
            f"subject={self.subject}, "
            f"student_group={self.student_group}"
            f")"
        )

The @planning_entity decorator creates a Java class for Lesson, which allows it to be used in constraints. The @planning_variable specify that a method returns a planning variable. As such, OptaPlanner will call the corresponding setter to change the value of the variable during solving. It must be named get%Variable() and has a corresponding setter set%Variable (where %Variable is the name of the variable). It takes two parameters:

  • The first parameter is the type this planning variable takes.
  • The second parameter, value_range_provider_refs, describes where it gets its values from. It a list of the id of its value range providers

The Constraints

The constraints tell OptaPlanner how good a solution is. Here how we create the constraints in Python:

In [4]:
from optapy import constraint_provider
from optapy.types import Joiners, HardSoftScore
from datetime import datetime, date, timedelta

# Trick since timedelta only works with datetime instances
today = date.today()


def within_30_minutes(lesson1, lesson2):
    between = datetime.combine(today, lesson1.timeslot.end_time) - datetime.combine(today, lesson2.timeslot.start_time)
    return timedelta(minutes=0) <= between <= timedelta(minutes=30)


@constraint_provider
def define_constraints(constraint_factory):
    return [
        # Hard constraints
        room_conflict(constraint_factory),
        teacher_conflict(constraint_factory),
        student_group_conflict(constraint_factory),
        # Soft constraints
        teacher_room_stability(constraint_factory),
        teacher_time_efficiency(constraint_factory),
        student_group_subject_variety(constraint_factory)
    ]


def room_conflict(constraint_factory):
    # A room can accommodate at most one lesson at the same time.
    return constraint_factory \
        .for_each(Lesson) \
        .join(Lesson,
              # ... in the same timeslot ...
              Joiners.equal(lambda lesson: lesson.timeslot),
              # ... in the same room ...
              Joiners.equal(lambda lesson: lesson.room),
              # form unique pairs
              Joiners.less_than(lambda lesson: lesson.id)
              ) \
        .penalize("Room conflict", HardSoftScore.ONE_HARD)


def teacher_conflict(constraint_factory):
    # A teacher can teach at most one lesson at the same time.
    return constraint_factory \
        .for_each(Lesson) \
        .join(Lesson,
              Joiners.equal(lambda lesson: lesson.timeslot),
              Joiners.equal(lambda lesson: lesson.teacher),
              Joiners.less_than(lambda lesson: lesson.id)
              ) \
        .penalize("Teacher conflict", HardSoftScore.ONE_HARD)


def student_group_conflict(constraint_factory):
    # A student can attend at most one lesson at the same time.
    return constraint_factory \
        .for_each(Lesson) \
        .join(Lesson,
              Joiners.equal(lambda lesson: lesson.timeslot),
              Joiners.equal(lambda lesson: lesson.student_group),
              Joiners.less_than(lambda lesson: lesson.id)
              ) \
        .penalize("Student group conflict", HardSoftScore.ONE_HARD)


def teacher_room_stability(constraint_factory):
    # A teacher prefers to teach in a single room.
    return constraint_factory \
        .for_each(Lesson) \
        .join(Lesson,
              Joiners.equal(lambda lesson: lesson.teacher),
              Joiners.less_than(lambda lesson: lesson.id)
              ) \
        .filter(lambda lesson1, lesson2: lesson1.room != lesson2.room) \
        .penalize("Teacher room stability", HardSoftScore.ONE_SOFT)


def teacher_time_efficiency(constraint_factory):
    # A teacher prefers to teach sequential lessons and dislikes gaps between lessons.
    return constraint_factory \
        .for_each(Lesson) \
        .join(Lesson,
              Joiners.equal(lambda lesson: lesson.teacher),
              Joiners.equal(lambda lesson: lesson.timeslot.day_of_week)
              ) \
        .filter(within_30_minutes) \
        .reward("Teacher time efficiency", HardSoftScore.ONE_SOFT)


def student_group_subject_variety(constraint_factory):
    # A student group dislikes sequential lessons on the same subject.
    return constraint_factory \
        .for_each(Lesson) \
        .join(Lesson,
              Joiners.equal(lambda lesson: lesson.subject),
              Joiners.equal(lambda lesson: lesson.student_group),
              Joiners.equal(lambda lesson: lesson.timeslot.day_of_week)
              ) \
        .filter(within_30_minutes) \
        .penalize("Student group subject variety", HardSoftScore.ONE_SOFT)

The @constraint_provider decorator creates a Java ConstraintProvider class, allowing OptaPlanner to use it. You can call any python method when evaluating your constraints.

Planning Solution

Finally, there is the planning solution. The planning solution stores references to all the problem facts and planning entities that define the problem. Additionally, it also contain the score of the solution. The planning solution class represent both the problem and the solution; as such, a problem can be viewed as an unintialized planning solution. Here how we define it in Python:

In [5]:
from optapy import planning_solution, planning_entity_collection_property, \
    problem_fact_collection_property, \
    value_range_provider, planning_score


def format_list(a_list):
    return ',\n'.join(map(str, a_list))


@planning_solution
class TimeTable:
    def __init__(self, timeslot_list, room_list, lesson_list, score=None):
        self.timeslot_list = timeslot_list
        self.room_list = room_list
        self.lesson_list = lesson_list
        self.score = score
        
    def set_student_group_and_teacher_list(self):
        self.student_group_list = []
        self.teacher_list = []
        for lesson in self.lesson_list:
            if lesson.teacher not in self.teacher_list:
                self.teacher_list.append(lesson.teacher)
            if lesson.student_group not in self.student_group_list:
                self.student_group_list.append(lesson.student_group)

    @problem_fact_collection_property(Timeslot)
    @value_range_provider("timeslotRange")
    def get_timeslot_list(self):
        return self.timeslot_list

    @problem_fact_collection_property(Room)
    @value_range_provider("roomRange")
    def get_room_list(self):
        return self.room_list

    @planning_entity_collection_property(Lesson)
    def get_lesson_list(self):
        return self.lesson_list

    @planning_score(HardSoftScore)
    def get_score(self):
        return self.score

    def set_score(self, score):
        self.score = score
    
    def __str__(self):
        return (
            f"TimeTable("
            f"timeslot_list={format_list(self.timeslot_list)},\n"
            f"room_list={format_list(self.room_list)},\n"
            f"lesson_list={format_list(self.lesson_list)},\n"
            f"score={str(self.score.toString()) if self.score is not None else 'None'}"
            f")"
        )

The @planning_solution decorator creates a Java class for TimeTable, allowing it to be passed to OptaPlanner. The @problem_fact_collection_property decorator tells OptaPlanner that method returns problem facts (it takes in one required argument: the Python class of the problem fact). Similarly, the @planning_entity_collection_property decorator tells OptaPlanner that method returns planning entities (it takes in one required argument: the Python class of the planning entity). The @value_range_provider decorator tells OptaPlanner the method provide values for variables. It range_id parameter is used determine what planning variable(s) accept values from it. For example, timeslot take values from the timeslotRange, so it accept values from getTimeslotList. Finally, the @planning_score decorator tells OptaPlanner the method returns the planning score (how good the solution is). Like with @planning_variable, It must be named get%Score() and has a corresponding setter set%Score (where %Score is the name of the score). Its parameter tells OptaPlanner what kind of score it takes.

Solving

Now that we defined our model and constraints, let create an instance of the problem:

In [6]:
from datetime import time

def generate_problem():
    timeslot_list = [
        Timeslot(1, "MONDAY", time(hour=8, minute=30), time(hour=9, minute=30)),
        Timeslot(2, "MONDAY", time(hour=9, minute=30), time(hour=10, minute=30)),
        Timeslot(3, "MONDAY", time(hour=10, minute=30), time(hour=11, minute=30)),
        Timeslot(4, "MONDAY", time(hour=13, minute=30), time(hour=14, minute=30)),
        Timeslot(5, "MONDAY", time(hour=14, minute=30), time(hour=15, minute=30)),
        Timeslot(6, "TUESDAY", time(hour=8, minute=30), time(hour=9, minute=30)),
        Timeslot(7, "TUESDAY", time(hour=9, minute=30), time(hour=10, minute=30)),
        Timeslot(8, "TUESDAY", time(hour=10, minute=30), time(hour=11, minute=30)),
        Timeslot(9, "TUESDAY", time(hour=13, minute=30), time(hour=14, minute=30)),
        Timeslot(10, "TUESDAY", time(hour=14, minute=30), time(hour=15, minute=30)),
    ]
    room_list = [
        Room(1, "Room A"),
        Room(2, "Room B"),
        Room(3, "Room C")
    ]
    lesson_list = [
        Lesson(1, "Math", "A. Turing", "9th grade"),
        Lesson(2, "Math", "A. Turing", "9th grade"),
        Lesson(3, "Physics", "M. Curie", "9th grade"),
        Lesson(4, "Chemistry", "M. Curie", "9th grade"),
        Lesson(5, "Biology", "C. Darwin", "9th grade"),
        Lesson(6, "History", "I. Jones", "9th grade"),
        Lesson(7, "English", "I. Jones", "9th grade"),
        Lesson(8, "English", "I. Jones", "9th grade"),
        Lesson(9, "Spanish", "P. Cruz", "9th grade"),
        Lesson(10, "Spanish", "P. Cruz", "9th grade"),
        Lesson(11, "Math", "A. Turing", "10th grade"),
        Lesson(12, "Math", "A. Turing", "10th grade"),
        Lesson(13, "Math", "A. Turing", "10th grade"),
        Lesson(14, "Physics", "M. Curie", "10th grade"),
        Lesson(15, "Chemistry", "M. Curie", "10th grade"),
        Lesson(16, "French", "M. Curie", "10th grade"),
        Lesson(17, "Geography", "C. Darwin", "10th grade"),
        Lesson(18, "History", "I. Jones", "10th grade"),
        Lesson(19, "English", "P. Cruz", "10th grade"),
        Lesson(20, "Spanish", "P. Cruz", "10th grade"),
    ]
    lesson = lesson_list[0]
    lesson.set_timeslot(timeslot_list[0])
    lesson.set_room(room_list[0])

    return TimeTable(timeslot_list, room_list, lesson_list)

and solve it:

In [ ]:
from optapy import solver_manager_create
from optapy.types import SolverConfig, Duration
from tango import pick_color
from ipywidgets import Tab
from ipysheet import sheet, cell, row, column, cell_range

solver_config = SolverConfig().withEntityClasses(Lesson) \
    .withSolutionClass(TimeTable) \
    .withConstraintProviderClass(define_constraints) \
    .withTerminationSpentLimit(Duration.ofSeconds(30))


solution = generate_problem()
solution.set_student_group_and_teacher_list()

cell_map = dict()

def on_best_solution_changed(best_solution):
    global timetable
    global solution
    global cell_map
    solution = best_solution
    unassigned_lessons = []
    clear_cell_set = set()
    
    for (table_name, table_map) in cell_map.items():
        for (key, cell) in table_map.items():
            clear_cell_set.add(cell)
            
    for lesson in solution.lesson_list:
        if lesson.timeslot is None or lesson.room is None:
            unassigned_lessons.append(lesson, clear_cell_set)
        else:
            update_lesson_in_table(lesson, clear_cell_set)
            
    for cell in clear_cell_set:
            cell.value = ""
            cell.style["backgroundColor"] = "white"
            
    for (table_name, table_map) in cell_map.items():
        for (key, cell) in table_map.items():
            cell.send_state()

def update_lesson_in_table(lesson, clear_cell_set):
    global cell_map
    x = solution.timeslot_list.index(lesson.timeslot)
    room_column = solution.room_list.index(lesson.room)
    teacher_column = solution.teacher_list.index(lesson.teacher)
    student_group_column = solution.student_group_list.index(lesson.student_group)
    color = pick_color(lesson.subject)


    room_cell = cell_map['room'][(x, room_column)]
    teacher_cell = cell_map['teacher'][(x, teacher_column)]
    student_group_cell = cell_map['student_group'][(x, student_group_column)]
    
    clear_cell_set.discard(room_cell)
    clear_cell_set.discard(teacher_cell)
    clear_cell_set.discard(student_group_cell)

    room_cell.value = f"{lesson.subject}\n{lesson.teacher}\n{lesson.student_group}"
    room_cell.style["backgroundColor"] = color
    room_cell.send_state()

    teacher_cell.value = f"{lesson.room.name}\n{lesson.subject}\n{lesson.student_group}"
    teacher_cell.style["backgroundColor"] = color
    teacher_cell.send_state()

    student_group_cell.value = f"{lesson.room.name}\n{lesson.subject}\n{lesson.teacher}"
    student_group_cell.style["backgroundColor"] = color
    student_group_cell.send_state()

    
def create_table(table_name, solution, columns, name_map):
    global cell_map
    out = sheet(rows=len(solution.timeslot_list) + 1, columns=len(columns) + 1)
    header_color = "#22222222"
    cell(0,0, read_only=True, background_color=header_color)
    header_row = row(0, list(map(name_map, columns)), column_start=1, read_only=True,
                    background_color=header_color)
    timeslot_column = column(0,
            list(map(lambda timeslot: timeslot.day_of_week[0:3] + " " + str(timeslot.start_time)[0:10],
                             solution.timeslot_list)), row_start=1, read_only=True, background_color=header_color)

    table_cells = dict()
    cell_map[table_name] = table_cells
    for x in range(len(solution.timeslot_list)):
        for y in range(len(columns)):
            table_cells[(x, y)] = cell(x + 1, y + 1, "", read_only=True)
    return out
        
solver_manager = solver_manager_create(solver_config)

by_room_table = create_table('room', solution, solution.room_list, lambda room: room.name)
by_teacher_table = create_table('teacher', solution, solution.teacher_list, lambda teacher: teacher)
by_student_group_table = create_table('student_group', solution, solution.student_group_list,
                                      lambda student_group: student_group)

solver_manager.solveAndListen(0, lambda the_id: solution, on_best_solution_changed)

tab = Tab()
tab.children = [by_room_table, by_teacher_table, by_student_group_table]

tab.set_title(0, 'By Room')
tab.set_title(1, 'By Teacher')
tab.set_title(2, 'By Student Group')

tab

The table will automatically update whenever a new best solution is found.