1. Introduction to OptaPlanner
In this tutorial, we look at a Java constraint satisfaction solver called OptaPlanner.
Note: For its fork/continuation, check out the Timefold Solver guide.
OptaPlanner solves planning problems using a suite of algorithms with minimal setup.
Although an understanding of the algorithms may provide helpful detail, with the framework performing the hard work for us.
2. Maven Dependency
First, we’ll add a Maven dependency for OptaPlanner:
<dependency>
<groupId>org.optaplanner</groupId>
<artifactId>optaplanner-core</artifactId>
<version>8.24.0.Final</version>
</dependency>
We locate the most recent version of OptaPlanner from Maven Central repository.
3. Problem/Solution Class
To solve a problem we certainly need a specific one as an example.
Lecture timetabling is a suitable example due to the difficulty in balancing resources such as rooms, time and teachers.
3.1. CourseSchedule
CourseSchedule contains a combination of our problem variables and planning entities consequently it is the solution class. As a result, we use multiple annotations to configure it.
Let’s take a closer look at each separately:
@PlanningSolution
public class CourseSchedule {
@ValueRangeProvider(id = "availableRooms")
@ProblemFactCollectionProperty
private List<Integer> roomList;
@ValueRangeProvider(id = "availablePeriods")
@ProblemFactCollectionProperty
private List<Integer> periodList;
@ProblemFactCollectionProperty
private List<Lecture> lectureList;
@PlanningScore
private HardSoftScore score;
The PlanningSolution annotation tells OptaPlanner that this class contains the data to encompass a solution.
OptaPlanner expects these minimum components: the planning entity, problem facts, and a score.
3.2. Lecture
Lecture, a POJO, looks like:
@PlanningEntity
public class Lecture {
@PlaningId
private Long id;
public Integer roomNumber;
public Integer period;
public String teacher;
@PlanningVariable(
valueRangeProviderRefs = {"availablePeriods"})
public Integer getPeriod() {
return period;
}
@PlanningVariable(
valueRangeProviderRefs = {"availableRooms"})
public Integer getRoomNumber() {
return roomNumber;
}
}
We use Lecture class as the planning entity, so we add another annotation on the getter in CourseSchedule:
@PlanningEntityCollectionProperty
public List<Lecture> getLectureList() {
return lectureList;
}
Our planning entity contains the constraints that are being set.
The PlanningVariable annotation and the valueRangeProviderRef annotations link the constraints to the problem facts.
These constraint values will be scored later across all planning entities.
3.3. Problem Facts
The roomNumber and period variables act as constraints similarly to each other.
OptaPlanner scores the solutions as a result of logic using these variables. We add annotations to both getter methods:
@ValueRangeProvider(id = "availableRooms")
@ProblemFactCollectionProperty
public List<Integer> getRoomList() {
return roomList;
}
@ValueRangeProvider(id = "availablePeriods")
@ProblemFactCollectionProperty
public List<Integer> getPeriodList() {
return periodList;
}
These lists are all possible values used in the Lecture fields.
OptaPlanner populates them in all solutions across the search space.
Finally, it then sets a score to each of the solutions, so we need a field to store the score:
@PlanningScore
public HardSoftScore getScore() {
return score;
}
Without a score, OptaPlanner cannot find the optimal solution hence the stressed importance earlier.
4. Scoring
In contrast to what we have looked at so far, the scoring class requires more custom code.
This is because the score calculator is specific to the problem and the domain model.
4.1. Custom Java
We use a simple score calculation to solve this problem (although it may not seem like it):
public class ScoreCalculator
implements EasyScoreCalculator<CourseSchedule, HardSoftScore> {
@Override
public HardSoftScore calculateScore(CourseSchedule courseSchedule) {
int hardScore = 0;
int softScore = 0;
Set<String> occupiedRooms = new HashSet<>();
for(Lecture lecture : courseSchedule.getLectureList()) {
String roomInUse = lecture.getPeriod()
.toString() + ":" + lecture.getRoomNumber().toString();
if(occupiedRooms.contains(roomInUse)){
hardScore += -1;
} else {
occupiedRooms.add(roomInUse);
}
}
return HardSoftScore.Of(hardScore, softScore);
}
}
If we take a closer look at the above code, the important parts become more clear. We calculate a score in the loop because the List
The HashSet is used to save a unique key (string) so that we can penalize duplicate lectures in the same room and period.
As a result, we receive unique sets of rooms and periods.
5. Testing
We configured our solution, solver and problem classes. Let’s test it!
5.1. Setting up Our Test
First, we do some setup:
SolverFactory<CourseSchedule> solverFactory = SolverFactory.create(new SolverConfig()
.withSolutionClass(CourseSchedule.class)
.withEntityClasses(Lecture.class)
.withEasyScoreCalculatorClass(ScoreCalculator.class)
.withTerminationSpentLimit(Duration.ofSeconds(1)));
solver = solverFactory.buildSolver();
unsolvedCourseSchedule = new CourseSchedule();
Second, we populate data into the planning entity collection and problem fact List objects.
5.2. Test Execution and Verification
Finally, we test it by calling solve.
CourseSchedule solvedCourseSchedule = solver.solve(unsolvedCourseSchedule);
assertNotNull(solvedCourseSchedule.getScore());
assertEquals(-4, solvedCourseSchedule.getScore().getHardScore());
We check that the solvedCourseSchedule has a score which tells us that we have the “optimal” solution.
For a bonus, we create a print method that will display our optimized solution:
public void printCourseSchedule() {
lectureList.stream()
.map(c -> "Lecture in Room "
+ c.getRoomNumber().toString()
+ " during Period " + c.getPeriod().toString())
.forEach(k -> logger.info(k));
}
This method displays:
Lecture in Room 1 during Period 1
Lecture in Room 2 during Period 1
Lecture in Room 1 during Period 2
Lecture in Room 2 during Period 2
Lecture in Room 1 during Period 3
Lecture in Room 2 during Period 3
Lecture in Room 1 during Period 1
Lecture in Room 1 during Period 1
Lecture in Room 1 during Period 1
Lecture in Room 1 during Period 1
Notice how the last three entries are repeating. This happens because there is no optimal solution to our problem. We chose three periods, two classrooms and ten lectures.
There are only six possible lectures due to these fixed resources. At the very least this answer shows the user that there are not enough rooms or periods to contain all the lectures.
6. Extra Features
Our example for OptaPlanner we created was a simple one, however, the framework has added features for more diverse use cases. We may want to implement or alter our algorithm for optimization and then specify the framework to use it.
Due to recent improvements in Java’s multi-threading capabilities, OptaPlanner also gives developers the ability to use multiple implementations of multi-threading such as fork and join, incremental solving and multitenancy.
Refer to the documentation for more information.
7. Conclusion
The OptaPlanner framework provides developers with a powerful tool to solve constraint satisfaction problems such as scheduling and resource allocation.
OptaPlanner offers minimal JVM resource usage as well as integrating with Jakarta EE. The author continues to support the framework, and Red Hat has added it as part of its Business Rules Management Suite.
As always the code can be found over on Github.