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.
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.
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 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:
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:
@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})"
)
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:
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:
value_range_provider_refs
, describes where it gets its values from.
It a list of the id of its value range providersThe constraints tell OptaPlanner how good a solution is. Here how we create the constraints in Python:
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.
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:
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.
Now that we defined our model and constraints, let create an instance of the problem:
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:
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.