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 :
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 :
@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 :
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 :
from optapy import constraint_provider, get_class
from optapy.types import Joiners, HardSoftScore
from datetime import datetime, date, timedelta

LessonClass = get_class(Lesson)
RoomClass = get_class(Room)

# 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 \
.forEach(LessonClass) \
.join(LessonClass,
[
# ... in the same timeslot ...
Joiners.equal(lambda lesson: lesson.timeslot),
# ... in the same room ...
Joiners.equal(lambda lesson: lesson.room),
# form unique pairs
Joiners.lessThan(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 \
.forEach(LessonClass) \
.join(LessonClass,
[
Joiners.equal(lambda lesson: lesson.timeslot),
Joiners.equal(lambda lesson: lesson.teacher),
Joiners.lessThan(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 \
.forEach(LessonClass) \
.join(LessonClass,
[
Joiners.equal(lambda lesson: lesson.timeslot),
Joiners.equal(lambda lesson: lesson.student_group),
Joiners.lessThan(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 \
.forEach(LessonClass) \
.join(LessonClass,
[
Joiners.equal(lambda lesson: lesson.teacher),
Joiners.lessThan(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.forEach(LessonClass) \
.join(LessonClass,
[
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.forEach(LessonClass) \
.join(LessonClass,
[
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 :
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

@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 :
from datetime import time
from functools import reduce

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
lesson.set_timeslot(timeslot_list)
lesson.set_room(room_list)

return TimeTable(timeslot_list, room_list, lesson_list)

def print_timetable(timetable: TimeTable):
room_list = timetable.room_list
lesson_list = timetable.lesson_list
timeslot_room_lesson_triple_list = list(map(lambda the_lesson: (the_lesson.timeslot, the_lesson.room, the_lesson),
filter(lambda the_lesson:
the_lesson.timeslot is not None and
the_lesson.room is not None,
lesson_list)))
lesson_map = dict()
for timeslot, room, lesson in timeslot_room_lesson_triple_list:
if timeslot in lesson_map:
if room in lesson_map[timeslot]:
lesson_map[timeslot][room].append(lesson)
else:
lesson_map[timeslot][room] = [lesson]
else:
lesson_map[timeslot] = {room: [lesson]}

print("|" + ("------------|" * (len(room_list) + 1)))
print(reduce(lambda a, b: a + b + " | ",
map(lambda the_room: "{:<10}".format(the_room.name)[0:10], room_list),
"|            | "))
print("|" + ("------------|" * (len(room_list) + 1)))
for timeslot in timetable.timeslot_list:
cell_list = list(map(lambda the_room: lesson_map.get(timeslot, {}).get(the_room, []),
room_list))
out = "| " + (timeslot.day_of_week[0:3] + " " + str(timeslot.start_time))[0:10] + " | "
for cell in cell_list:
if len(cell) == 0:
out += "           | "
else:
out += "{:<10}".format(reduce(lambda a, b: a + "," + b,
map(lambda assigned_lesson: assigned_lesson.subject,
cell)))[0:10] + " | "
print(out)
out = "|            | "
for cell in cell_list:
if len(cell) == 0:
out += "           | "
else:
out += "{:<10}".format(reduce(lambda a, b: a + "," + b,
map(lambda assigned_lesson: assigned_lesson.teacher,
cell)))[0:10] + " | "
print(out)
out = "|            | "
for cell in cell_list:
if len(cell) == 0:
out += "           | "
else:
out += "{:<10}".format(reduce(lambda a, b: a + "," + b,
map(lambda assigned_lesson: assigned_lesson.student_group,
cell)))[0:10] + " | "
print(out)
print("|" + ("------------|" * (len(room_list) + 1)))
unassigned_lessons = list(
filter(lambda unassigned_lesson: unassigned_lesson.timeslot is None or unassigned_lesson.room is None,
lesson_list))
if len(unassigned_lessons) > 0:
print()
print("Unassigned lessons")
for lesson in unassigned_lessons:
print(" " + lesson.subject + " - " + lesson.teacher + " - " + lesson.student_group)

and solve it:

In [ ]:
from optapy import solver_factory_create
from optapy.types import SolverConfig, Duration

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

solver = solver_factory_create(solver_config).buildSolver()
solution = solver.solve(generate_problem())

print_timetable(solution)

Which will print a solution that look like the following:

|------------|------------|------------|------------|
|            | Room A     | Room B     | Room C     |
|------------|------------|------------|------------|
| MON 08:30: |            | Math       | History    |
|            |            | A. Turing  | I. Jones   |
|------------|------------|------------|------------|
| MON 09:30: |            | Math       | History    |
|            |            | A. Turing  | I. Jones   |
|------------|------------|------------|------------|
| MON 10:30: |            | Math       | English    |
|            |            | A. Turing  | I. Jones   |
|------------|------------|------------|------------|
| MON 13:30: | Math       | Spanish    |            |
|            | A. Turing  | P. Cruz    |            |
|------------|------------|------------|------------|
| MON 14:30: | Math       | English    |            |
|            | A. Turing  | P. Cruz    |            |
|------------|------------|------------|------------|
| TUE 08:30: | Physics    | Spanish    |            |
|            | M. Curie   | P. Cruz    |            |
|------------|------------|------------|------------|
| TUE 09:30: | Chemistry  |            | English    |
|            | M. Curie   |            | I. Jones   |