I just announced the new Spring Boot 2 material, coming in REST With Spring:

>> CHECK OUT THE COURSE

1. Introduction to OptaPlanner

In this tutorial, we look at a Java constraint satisfaction solver called OptaPlanner.

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>7.9.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 {

    private List<Integer> roomList;
    private List<Integer> periodList;
    private List<Lecture> lectureList;
    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 {

    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> {

    @Override
    public Score 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.valueOf(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.

4.2. Drools

Drools files give us a quick way to alter rules for applying to files. While the syntax can sometimes be confusing the Drools file can be a way to manage logic outside of the compiled classes.

Our rule to prevent null entries looks like this:

global HardSoftScoreHolder scoreHolder;

rule "noNullRoomPeriod"
    when
        Lecture( roomNumber == null );
        Lecture( period == null );
    then
        scoreHolder.addHardConstraintMatch(kcontext, -1);
end

5. Solver Configuration

Another necessary configuration file, we need an XML file to configure the solver.

5.1. XML Configuration File

<solver>
    <scanAnnotatedClasses/>

    <scoreDirectorFactory>
        <easyScoreCalculatorClass>
            org.baeldung.optaplanner.ScoreCalculator
        </easyScoreCalculatorClass>
    </scoreDirectorFactory>

    <termination>
        <secondsSpentLimit>10</secondsSpentLimit>
    </termination>
</solver>

Due to our annotations in the CourseSchedule class, we use the scanAnnotatedClasses element here to scan files on the classpath.

The scoreDirectorFactory element contents set our ScoreCalculator class to contain our scoring logic.

When we want to use a Drools file, we replace the element contents with:

<scoreDrl>courseScheduleScoreRules.drl</scoreDrl>

Our final setting is the termination element. Rather than search endlessly for an optimized solution that may never exist, this setting will stop the search after a time limit.

Ten seconds is more than enough for most problems.

6. Testing

We configured our solution, solver and problem classes. Let’s test it!

6.1. Setting up our Test

First, we do some setup:

SolverFactory<CourseSchedule> solverFactory = SolverFactory
  .createFromXmlResource("courseScheduleSolverConfiguration.xml");
solver = solverFactory.buildSolver();

unsolvedCourseSchedule = new CourseSchedule();

Second, we populate data into the planning entity collection and problem fact List objects.

6.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.

7. 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.

8. 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 Java 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.

I just announced the new Spring Boot 2 material, coming in REST With Spring:

>> CHECK OUT THE LESSONS

newest oldest most voted
Notify of
Geoffrey De Smet
Guest
Geoffrey De Smet

Great article. Thanks for covering OptaPlanner.
Currently we haven’t written a optaplanner-spring-boot-starter yet. Do you think that would be useful? And more importantly, what do you think it should do?

See also this discussion:
https://groups.google.com/forum/#!topic/optaplanner-dev/fPgmKy6XNZs

We intend to build SolverManager, a component that manages several Solvers and their threads. I think that might be a good candidate to make it easy to inject – but I am looking for proposals of strawman examples on how people would want that to work.

Kyle Doyle
Guest
Kyle Doyle

Hi Geoffrey –

I am very glad you like the article.

I think that a Spring Boot starter could be nice. However, OptaPlanner integration, as it stands currently, is pretty simple. Some of the examples could be beneficial to include as Spring Boot projects.

Possibly examples that show custom heuristic algorithms or further customization using OptaPlanner.

I appreciate the additional information below as well. I included the Drools rule as a simple way to integrate Drools in the article without creating an overly complex use case.

Thanks again for the comments!

Geoffrey De Smet
Guest
Geoffrey De Smet

For completeness: the drools rule is obsolete because OptaPlanner guarantees that none of the planning variables are null after solving, unless @PlanningVariable(nullabe=true).

It’s even slightly better not to have that constraint (very advanced explanation: the initializingScoreTrend becomes ANY instead of ONLY_DOWN, so the Construction Heuristics algorithms can’t take certain shortcuts any more) – but don’t worry too much about this last part.