A Guide to OptaPlanner

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<Lecture> contains specific non-unique combinations of rooms and periods.

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.