Three optimizations to make your Timefold Solver faster

Our friends at Dots & Lines recently claimed they made their Timefold Solver 17x faster and they're not wrong. With our IncrementalScoreCalculator, you can absolutely get there. But it comes bundled with months of effort, sacrificed explainability, and constraints that become a nightmare to maintain or extend.

There's a better way. In this post, we'll apply three targeted optimizations to the same course scheduling problem they used and walk away with a 91% speedup while keeping your constraints clean, testable, and easy to change.

# The Setup

We're using the code from the Dots & Lines article as our baseline. If you haven't read it, don't worry, we'll cover everything you need here. One difference: we're measuring things slightly differently. We're using the comp06 dataset (where they saw the biggest gains), running for 1 minute with a 15-second JVM warmup, averaging across 10 runs in separate JVM processes, and using -Xmx1g -XX:+UseParallelGC -XX:+UseCompactObjectHeaders to fine-tune performance and keep the noise out. This gives us a more stable baseline than a single long run.

Here's the starting constraint implementation:

public class CurriculumCourseConstraintProvider implements ConstraintProvider {
    @Override
    public Constraint[] defineConstraints(ConstraintFactory factory) {
        return new Constraint[]{
                conflictingLecturesDifferentCourseInSamePeriod(factory),
                conflictingLecturesSameCourseInSamePeriod(factory),
                roomOccupancy(factory),
                unavailablePeriodPenalty(factory),
                roomCapacity(factory),
                minimumWorkingDays(factory),
                curriculumCompactness(factory),
                roomStability(factory)
        };
    }
    // ************************************************************************
    // Hard constraints
    // ************************************************************************
    Constraint conflictingLecturesDifferentCourseInSamePeriod(ConstraintFactory factory) {
        return factory.forEach(CourseConflict.class)
                .join(Lecture.class,
                        equal(CourseConflict::getLeftCourse, Lecture::getCourse))
                .join(Lecture.class,
                        equal((courseConflict, lecture1) -> courseConflict.getRightCourse(), Lecture::getCourse),
                        equal((courseConflict, lecture1) -> lecture1.getPeriod(), Lecture::getPeriod))
                .filter(((courseConflict, lecture1, lecture2) -> lecture1 != lecture2))
                .penalize(ONE_HARD,
                        (courseConflict, lecture1, lecture2) -> courseConflict.getConflictCount())
                .asConstraint("conflictingLecturesDifferentCourseInSamePeriod");
    }
    Constraint conflictingLecturesSameCourseInSamePeriod(ConstraintFactory factory) {
        return factory.forEachUniquePair(Lecture.class,
                        equal(Lecture::getPeriod),
                        equal(Lecture::getCourse))
                .penalize(ONE_HARD,
                        (lecture1, lecture2) -> 1 + lecture1.getCurriculumSet().size())
                .asConstraint("conflictingLecturesSameCourseInSamePeriod");
    }
    Constraint roomOccupancy(ConstraintFactory factory) {
        return factory.forEachUniquePair(Lecture.class,
                        equal(Lecture::getRoom),
                        equal(Lecture::getPeriod))
                .penalize(ONE_HARD)
                .asConstraint("roomOccupancy");
    }
    Constraint unavailablePeriodPenalty(ConstraintFactory factory) {
        return factory.forEach(UnavailablePeriodPenalty.class)
                .join(Lecture.class,
                        equal(UnavailablePeriodPenalty::getCourse, Lecture::getCourse),
                        equal(UnavailablePeriodPenalty::getPeriod, Lecture::getPeriod))
                .penalize(ofHard(10))
                .asConstraint("unavailablePeriodPenalty");
    }
    // ************************************************************************
    // Soft constraints
    // ************************************************************************
    Constraint roomCapacity(ConstraintFactory factory) {
        return factory.forEach(Lecture.class)
                .filter(lecture -> lecture.getStudentSize() > lecture.getRoom().getCapacity())
                .penalize(ofSoft(1),
                        lecture -> lecture.getStudentSize() - lecture.getRoom().getCapacity())
                .asConstraint("roomCapacity");
    }
    Constraint minimumWorkingDays(ConstraintFactory factory) {
        return factory.forEach(Lecture.class)
                .groupBy(Lecture::getCourse, countDistinct(Lecture::getDay))
                .filter((course, dayCount) -> course.getMinWorkingDaySize() > dayCount)
                .penalize(ofSoft(5),
                        (course, dayCount) -> course.getMinWorkingDaySize() - dayCount)
                .asConstraint("minimumWorkingDays");
    }
    Constraint curriculumCompactness(ConstraintFactory factory) {
        return factory.forEach(Curriculum.class)
                .join(Lecture.class,
                        filtering((curriculum, lecture) -> lecture.getCurriculumSet().contains(curriculum)))
                .ifNotExists(Lecture.class,
                        equal((curriculum, lecture) -> lecture.getDay(), Lecture::getDay),
                        equal((curriculum, lecture) -> lecture.getTimeslotIndex(), lecture -> lecture.getTimeslotIndex() + 1),
                        filtering((curriculum, lectureA, lectureB) -> lectureB.getCurriculumSet().contains(curriculum)))
                .ifNotExists(Lecture.class,
                        equal((curriculum, lecture) -> lecture.getDay(), Lecture::getDay),
                        equal((curriculum, lecture) -> lecture.getTimeslotIndex(), lecture -> lecture.getTimeslotIndex() - 1),
                        filtering((curriculum, lectureA, lectureB) -> lectureB.getCurriculumSet().contains(curriculum)))
                .penalize(ofSoft(2))
                .asConstraint("curriculumCompactness");
    }
    Constraint roomStability(ConstraintFactory factory) {
        return factory.forEach(Lecture.class)
                .groupBy(Lecture::getCourse, countDistinct(Lecture::getRoom))
                .filter((course, roomCount) -> roomCount > 1)
                .penalize(HardSoftScore.ONE_SOFT,
                        (course, roomCount) -> roomCount - 1)
                .asConstraint("roomStability");
    }
}

With that out of the way, let's get to the optimizations!

# Upgrading to the latest Timefold Solver

The original article used Timefold Solver 1.21.0, a version which is more than a year old at the time of writing this article. Since then, there have been many optimizations and bugfixes to the Timefold Solver codebase, and upgrading to the latest version of Timefold Solver is the first step to get optimal performance. 

While upgrading to the newest Timefold Solver version did not significantly impact baseline performance in this use case, the newer versions do come with extra features you can implement to improve performance. 

# Precomputing static joins

Let's consider the conflictingLecturesDifferentCourseInSamePeriod constraint:

return factory.forEach(CourseConflict.class)
    .join(Lecture.class,
            equal(CourseConflict::getLeftCourse, Lecture::getCourse))
    .join(Lecture.class,
            equal((courseConflict, lecture1) -> courseConflict.getRightCourse(), Lecture::getCourse),
            equal((courseConflict, lecture1) -> lecture1.getPeriod(), Lecture::getPeriod))
    .filter(((courseConflict, lecture1, lecture2) -> lecture1 != lecture2))
    .penalize(ONE_HARD,
            (courseConflict, lecture1, lecture2) -> courseConflict.getConflictCount())
    .asConstraint("conflictingLecturesDifferentCourseInSamePeriod");

This constraint has two joins - the first join is between CourseConflict and Lecture, and the second join is between the result of the first join and Lecture again. The first join is static. It only depends on the problem facts and does not depend on any variables. This means that the product of this join will never change during solving, and we can therefore cache it before solving, using a recently introduced precomputation feature of Timefold Solver. The adapted constraint would look like so:

return factory.precompute(
            f -> f.forEachUnfiltered(Curriculum.class)
                .join(Lecture.class,
                      filtering((curriculum, lecture) -> lecture.getCurriculumSet().contains(curriculum))))
        .join(Lecture.class,
              equal((courseConflict, lecture1) -> courseConflict.getRightCourse(), Lecture::getCourse),
              equal((courseConflict, lecture1) -> lecture1.getPeriod(), Lecture::getPeriod))
        .filter(((courseConflict, lecture1, lecture2) -> lecture1 != lecture2))
        .penalize(ONE_HARD,
            (courseConflict, lecture1, lecture2) -> courseConflict.getConflictCount())
        .asConstraint("conflictingLecturesDifferentCourseInSamePeriod");

And what do we get in return for this small change? A nice 17% speedup!

As is often the case, the best join is a join avoided. Can we avoid more?

# Consecutive sequences

The curriculumCompactness constraint makes sure that lectures of the same curriculum are scheduled in consecutive timeslots. In order to do this, it selects all lectures of a curriculum and checks for each lecture if there is another lecture of the same curriculum in the previous or next timeslot. If there is not, a penalty will ensue.

return factory.forEach(Curriculum.class)
        .join(Lecture.class,
                filtering((curriculum, lecture) -> lecture.getCurriculumSet().contains(curriculum)))
        .ifNotExists(Lecture.class,
                equal((curriculum, lecture) -> lecture.getDay(), Lecture::getDay),
                equal((curriculum, lecture) -> lecture.getTimeslotIndex(), lecture -> lecture.getTimeslotIndex() + 1),
                filtering((curriculum, lectureA, lectureB) -> lectureB.getCurriculumSet().contains(curriculum)))
        .ifNotExists(Lecture.class,
                equal((curriculum, lecture) -> lecture.getDay(), Lecture::getDay),
                equal((curriculum, lecture) -> lecture.getTimeslotIndex(), lecture -> lecture.getTimeslotIndex() - 1),
                filtering((curriculum, lectureA, lectureB) -> lectureB.getCurriculumSet().contains(curriculum)))
        .penalize(ofSoft(2))
        .asConstraint("curriculumCompactness");

This is effectively three joins between Curriculum and Lecture with a filter on the timeslot index. If we can rewrite this constraint to avoid these joins, we can get a significant speedup. The adapted constraint could look like this:

return factory.precompute(CurriculumCourseConstraintProvider::curriculumLectureLeft)
        .groupBy((curriculum, lecture) -> curriculum,
                (curriculum, lecture) -> lecture.getDay(),
                ConstraintCollectors.conditionally(
                        (curriculum, lecture) -> lecture.getDay() != null,
                        ConstraintCollectors.toConsecutiveSequences(
                                (Curriculum curriculum, Lecture lecture) -> lecture,
                                Lecture::getTimeslotIndex)))
        .flattenLast(SequenceChain::getConsecutiveSequences)
        .filter((curriculum, day, sequence) -> sequence.getLength() == 1)
        .penalize(ofSoft(2))
        .asConstraint("curriculumCompactness");

We first take advantage of the fact that much of this constraint is shared with the previous constraint. Therefore, we can reuse the same precomputation to get the lectures of each curriculum. Then we can split these lectures by the curriculum and the day that they fall on and then use the advanced toConsecutiveSequences collector to get the consecutive sequences of lectures for each curriculum and day. If a sequence has a length of 1, it means that there is a lecture that is not scheduled next to any other lecture of the same curriculum, and therefore we need to apply a penalty.

The constraint is now a bit more difficult to read, but we get a 40% speedup for our efforts!

In performance optimizations, this is a common pattern: an obvious and straightforward implementation is often not the most performant one. But can we still do better than this?

# Replacing unique pairs with maths

The roomOccupancy constraint checks if there are two lectures which share the same room and the same period. This is clearly an impossible situation, and therefore needs to be penalized. The constraint gets it done by penalizing every unique pair of lectures that share the same room and the same period:

return factory.forEachUniquePair(Lecture.class,
                equal(Lecture::getRoom),
                equal(Lecture::getPeriod))
        .penalize(ONE_HARD)
        .asConstraint("roomOccupancy");

This is a join, and joins can be expensive when the cross-product becomes large. But those of you who paid attention in maths class might have noticed that this is actually a combinatorial problem. If there are n lectures in the same room and period, there are n choose 2 unique pairs between those lectures, which is equal to n * (n - 1) / 2. This means that we can rewrite the constraint to list all lectures, group them by room and period, count the number of lectures in each group, and apply the combinatorial formula to calculate the number of unique pairs in each group. The adapted constraint would look like this:

return factory.forEach(Lecture.class)
        .groupBy(Lecture::getRoom, Lecture::getPeriod, count())
        .filter((room, period, count) -> count > 1)
        .penalize(ONE_HARD, (room, period, count) -> (count * (count - 1)) / 2)
        .asConstraint("roomOccupancy");

Another join replaced, this time for an additional 13% speedup!

# What we achieved

Three optimizations. A few hours of work. A 91% speedup and the constraints are still readable, testable, and easy to extend. Compare that to the IncrementalScoreCalculator route: weeks of implementation, no out-of-the-box explainability without serious effort, and constraints that are genuinely painful to add or change. That's not a small thing. 

The 17x headline is real, but it is the ceiling of what's possible after an enormous investment. We got to 2x in an afternoon, and that may be just enough.

# When to optimize (and when to stop)

Performance work is always about tradeoffs. Here's the approach we'd recommend:

1. Start clean: Write straightforward Constraint Streams code first. It's readable, testable, and fast enough for most problems.
2. Don't optimize prematurely: If your solver is fast enough, ship it. Every optimization adds complexity.
3. Profile before guessing: When you do need to optimize, use Constraint Profiling to find the actual bottlenecks...they're rarely where you expect.
4. Optimize one thing at a time: Apply the highest-impact change, benchmark it, then decide if you need more.
5. Know when to stop: Diminishing returns kick in fast. A 91% speedup from three targeted changes may already beat chasing a full rewrite. We'd only recommend reaching for IncrementalScoreCalculator if you've genuinely exhausted everything else and still can't hit your performance targets. For most problems, you ain't gonna need it. What you will need is ease of maintenance, and the ability to add new constraints without breaking a sweat.