The work on Timefold Solver 1.0.0 is progressing well. We intend to release in early July. This post will give you a sneak peek of what’s coming.

Brand new benchmark report

The solver benchmark report has been completely redesigned and modernized. It now fits nicely on all kinds of screens, from mobile phones to desktops.

Importantly, every chart in the report is now interactive, allowing you to filter the data points to only show those you want to see.

Static pictures don’t do it justice, you need to see it to believe it. Did you know you can build the solver locally to get access to the latest developments before they’re generally available?

Constraint Streams improvements

Constraint Streams are a powerful way to express constraints in a declarative way. In Timefold Solver 1.0.0, they will become even more powerful by introducing the expand()building block. Consider the following constraint:

Constraint speakerRequiredRoomTags(ConstraintFactory factory) {
   return factory.forEach(Talk.class)
       .filter(talk -> talk.missingSpeakerRequiredRoomTagCount() > 0)
       .penalizeConfigurable(talk -> talk.missingSpeakerRequiredRoomTagCount() * talk.getDurationInMinutes())
       .asConstraint(SPEAKER_REQUIRED_ROOM_TAGS);
}

Note that the method missingSpeakerRequiredRoomTagCount() is called twice; once to filter Talk instances and the second time to penalize every one of them. This is not ideal, and it becomes even worse when you realize that under the hood, this method does some heavy lifting to compute the missing tags. The end result is that this constraint is not very efficient. With the new expand() building block, we can rewrite it as follows:

Constraint speakerRequiredRoomTags(ConstraintFactory factory) {
   return factory.forEach(Talk.class)
           .expand(Talk::missingSpeakerRequiredRoomTagCount)
           .filter((talk, missingTagCount) -> missingTagCount > 0)
           .penalizeConfigurable((talk, missingTagCount) -> missingTagCount * talk.getDurationInMinutes())
           .indictWith((talk, missingTagCount) -> Collections.singleton(talk))
           .asConstraint(SPEAKER_REQUIRED_ROOM_TAGS);
}

Notice that the expand() building block caches the computation and propagate it downstream.

We use the not-so-well-known indictWith() building block, which allows us to indicate which facts are responsible for the constraint violation. Since missingTagCountis a plain integer without any semantics, it doesn’t help us to explain the score and therefore it is removed.

Performance improvements and bugfixes

Behind the scenes, we continue to work tirelessly to improve the performance of our solution. With Timefold Solver 1.0.0, users of Constraint Streams will see performance improvements of up to 15% in some cases. And that is on top of the significant speedup that Timefold already brings over OptaPlanner!

Conclusion

Timefold moves ahead at an ever increasing pace. Migrate to Timefold today, and enjoy the benefits of a modern, fast and powerful constraint solver.

OptaPlanner is an Open Source project used globally to optimize operational planning. Every day, it saves thousands of organizations time, money and resources.

On May 2nd, 2023, OptaPlanner entered a new chapter.

The project we worked on for seventeen years has matured under Red Hat’s wings for the past ten years. In 2022, when Red Hat’s strategy changed, it became apparent that the project needed a new, sustainable future. Therefore, we founded a company around it. A company that lives and breathes planning optimization, to further nurture the Open Source project to its fullest potential, under a new name. Timefold is the continuation of OptaPlanner.

Timefold Solver Community Edition is an Apache-licensed Open Source solver for operational planning optimization. It’s a fork of OptaPlanner, and it is already faster, lighter and better documented than OptaPlanner. Timefold has added features and fixed many bugs that still reside in OptaPlanner. Upgrade from OptaPlanner to Timefold today.

The Timefold Solver project is supported by Timefold BV, a professional Open Source company founded by Maarten Vandenbroucke (CEO) and Geoffrey De Smet (the OptaPlanner creator, CTO), with funding from Smartfin, an Open Source minded VC that fully supports our vision. The OptaPlanner team (Lukáš Petrovický, Radovan Synek, and Christopher Chianelli) have joined Timefold. We sell an Enterprise subscription with professional support and high-scalability features, to pay for the continued development of the free Open Source project.

Our mission is to free the world from wasteful scheduling. Our vision is to make Planning Optimization easy to use and simple to build. If you want to learn everything there is to know about planning optimization, follow us on YouTube, LinkedIn or Twitter.

Timefold is committed to be the world’s most powerful, versatile, and easy-to-use planning optimization solver. We combine our advanced AI solver algorithms with constraint models written in Java or Kotlin to be our main differentiator from other solvers. We remain Open Source which ensures a no-barrier entry for every team that wants to start using Timefold. We are hiring the brightest and most creative engineers to explore how we can make planning optimization even more accessible!

FAQ

We understand this message may be unsettling at first, especially if you use OptaPlanner extensively. We apologize for the short-term disruption, but we believe it is necessary to continue the project.

To address all potential concerns, we have compiled a list of Frequently Asked Questions. If you have any other concerns, don’t hesitate to contact us.

Why would I switch from OptaPlanner to Timefold?

Because it’s better:

1. Continuity, responsiveness, know-how and stability: The entire Timefold company is focused on building the best possible planning optimization software and helping you succeed with it. Timefold Solver has many bugfixes and security fixes since it forked from OptaPlanner. We also added powerful new features and enhancements.

1. Performance: Timefold is twice as fast as OptaPlanner out-of-the-box.

1. Distribution size: Cloud deployments love lightweight components. Timefold has all the features of OptaPlanner, but a jar-with-dependencies assembly of the sameHello World program is 41% smaller:

1. Timefold Solver has fewer dependencies. This also speeds up your Maven or Gradle build.
2. Documentation: We are constantly improving the documentation and fine-tuning the quickstarts. It’s easier to get started with Timefold than with OptaPlanner.

Why did you fork OptaPlanner if you created it?

Geoffrey De Smet: "OptaPlanner is my life’s work. As the creator and lead of OptaPlanner, I wrote most of the code (85% according to github - take that with a grain of salt). First seven years in my spare time. Then nine years for Red Hat. I am grateful to each contributor and every user. And I loved working at Red Hat for all those years. Together, we’ve built a wonderful community and a rock-solid project with a strong reputation.

But the work is far from finished. OptaPlanner has a lot more potential.

After the IBM acquisition, Red Hat’s company strategy changed. Business Automation was no longer a priority. Early 2022, Red Hat Decision Manager (the support subscription that paid for my team) movd to IBM, without OptaPlanner. By late 2022, I no longer saw a sustainable future for OptaPlanner’s development within Red Hat.

I could not just let OptaPlanner perish. So I resigned. And over the past few months, I’ve worked on a way to continue and grow the open source project. To build a company around it. An open source company dedicated to planning optimization. Luckily, I met the right people. So I could continue the project.

Over the summer of 2023, Lukáš Petrovický, Radovan Synek, and Christopher Chianelli - the core OptaPlanner engineers - joined Timefold. With their expertise we are able to accelerate the future of Planning Optimization.

So why fork OptaPlanner? I don’t own the DNS name (the optaplanner.org URL) and it’s debatable who owns the trademark. Both are required to build a sustainable business. To rescue OptaPlanner, I had no other option than to fork it."

Is Timefold 100% open source? What’s your business model?

A professional Open Source project needs a viable Open Source business model. Without paying customers, a professional Open Source project cannot survive. Great software developers don’t write code and documentation for free. Not full-time. Not as a team. Everyone needs to eat.

Red Hat sold a support subscription on OptaPlanner. Despite OptaPlanner’s world-wide usage, it struggled commercially. It’s hard to sell support on stable software. Big corporations used OptaPlanner to schedule 10k+ employees in mission critical systems, and often didn’t pay for it.

Therefore, Timefold has an Open Core model. We offer 2 editions:

• Timefold Solver Community Edition (free, Open Source, Apache License 2.0): a comprehensive, well-documented solver for any planning optimization use case. It has no built-in restrictions.
• Timefold Solver Enterprise Edition (paid): A thin layer of additional high-scalability features on top of Timefold Solver Community Edition, specifically to solve large datasets in mission-critical systems far more efficiently. It comes with full enterprise support.

We are committed to Open Source. It is a fundamental part of our company mission. Our future is to actively develop the Community Edition alongside the Enterprise Edition. The revenue of Timefold Solver Enterprise Edition pays for Timefold Solver Community Edition.

New solver features go to Community Edition, except for high-scalability features. The same logic applied during the fork of OptaPlanner: All OptaPlanner features are part of Community Edition, except for Multithreaded Solving and Nearby Selection. Those are part of Enterprise Edition. 90% of OptaPlanner users don’t use either of these. They are pure high-scalability features. Check if this change affects you, by searching for use of moveThreadCount or NearbyDistanceMeter in your code.

How do the OptaPlanner and Timefold versions relate?

• Timefold 0.8.x is a replacement for OptaPlanner 8. It supports Java 11, Java 17, Spring Boot 2, Quarkus 2 and Java EE 8. It has reached its End of Life and is no longer supported.
• Timefold 1.x is a replacement for OptaPlanner 9. It supports Java 17+, Spring Boot 3, Quarkus 3 and Jakarta EE 10.

Is Timefold Backward Compatible with OptaPlanner?

Yes, except for the branding changes.

Run timefold-migration to automatically change all your code locally. It’s a quick, single command for Maven or Gradle. Then test those changes and commit them. Alternatively, apply the following changes manually.

Timefold Solver 1.x is backward compatible with OptaPlanner 8.x, except that:

• Minimum Java 17 (LTS). Java 21 (LTS) and the latest Java version are also supported.
• The Maven/Gradle GAVs changed:
  • The groupId changed from org.optaplanner to ai.timefold.solver.
  • The artifactIds changed from optaplanner-* to timefold-solver-*.
  • ArtifactIds containing peristence- changed from optaplanner-persistence-*to timefold-solver-*.
    • For example, optaplanner-persistence-jackson changed to timefold-solver-jackson.
• The import statements changed accordingly:
  • import org.optaplanner…; changed to import ai.timefold.solver…;.
  • import org.optaplanner.persistence…; changed to import ai.timefold.solver…; too.
• The JEE dependencies changed from javax to jakarta to accommodate Spring 3 and Quarkus 3.
  • This is the same difference as between OptaPlanner 8.x and OptaPlanner 9.x.
• The OptaPlannerJacksonModule class is now called TimefoldJacksonModule.
• The deprecated scoreDRL support is removed, because Drools with its transitive dependencies have been removed entirely.
• The unsecure module persistence-xstream is removed, because of old, unresolved CVEs in XStream.
• The deprecated, undocumented ScoreHibernateType has been removed because of Jakarta. Use JPA’s ScoreConverter instead.

All other deprecated code remains, to make upgrading easy.

What else has changed in Timefold?

• Issue tracking: GitHub issues instead of JIRA.
  • You can now easily submit an issue for us to fix.
• Discussion list: GitHub discussions instead of Google Groups.
• Continuous Integration: GitHub Actions instead of a private Jenkins instance.
  • Our CI jobs are now open to the community.
  • Releases are now automated with JReleaser.
• Security and bugs: Hotfix releases for Timefold Community are now released to Maven Central, immediately.
• Version numbering: The .Final suffix is removed. It had no use.
• Customer response time: Our team replies swiftly on support, sales or other inquiries.

What stays the same?

• High quality
• Regular releases
• Backwards Compatibility guarantees on the API, following Semantic Versioning.
• Our engineers answer questions on Stack Overflow.
• Open culture. Talk to us on GitHub discussions!

Why did you name it Timefold?

Because we fold time and space to plan your operations.

How do I upgrade from OptaPlanner to Timefold?

Upgrade from OptaPlanner to Timefold Solver Community Edition today. It only takes 2 minutes.

Run the command below to upgrade your code automatically. Do a test run of the solver and commit the changes. If it doesn’t work, just revert it instead and submit an issue. We’ll fix it with the highest priority.

MavenGradle

mvn org.openrewrite.maven:rewrite-maven-plugin:6.2.3:run -Drewrite.recipeArtifactCoordinates=ai.timefold.solver:timefold-solver-migration:1.20.0 -Drewrite.activeRecipes=ai.timefold.solver.migration.ToLatest

Timefold Solver 1.x does not support scoreDRL, nor is it upgraded automatically. If you’re still using scoreDRL from OptaPlanner 7.x, please upgrade to Constraint Streams first.

Upgrade from OptaPlanner to Timefold Solver Community Edition today. It only takes 2 minutes.

Run the command below to upgrade your code automatically. Do a test run of the solver and commit the changes. If it doesn’t work, just revert it instead and submit an issue. We’ll fix it with the highest priority.

MavenGradle

mvn org.openrewrite.maven:rewrite-maven-plugin:6.15.0:run -Drewrite.recipeArtifactCoordinates=ai.timefold.solver:timefold-solver-migration:1.25.0 -Drewrite.activeRecipes=ai.timefold.solver.migration.ToLatest

Note: this command is not actively updated. Check our documentation for the command with the latest version numbers.

Timefold Solver 1.x does not support scoreDRL, nor is it upgraded automatically. If you’re still using scoreDRL from OptaPlanner 7.x, please upgrade to Constraint Streams first.

Why would I switch from OptaPlanner to Timefold?

Because it’s better:

1. Continuity, responsiveness, know-how and stability: The entire Timefold company is focused on building the best possible planning optimization software and helping you succeed with it. Timefold Solver has many bugfixes and security fixes since it forked from OptaPlanner. We also added powerful new features and enhancements.
   

1. Performance: Timefold is twice as fast as OptaPlanner out-of-the-box.
   

1. Distribution size: Cloud deployments love lightweight components. Timefold has all the features of OptaPlanner, but a jar-with-dependencies assembly of the same Hello World program is 41% smaller:
   

1. Documentation: We are constantly improving the documentation and fine-tuning the quickstarts. It’s easier to get started with Timefold than with OptaPlanner.

How do the OptaPlanner and Timefold versions relate?

• Timefold 0.8.x is a replacement for OptaPlanner 8. It supports Java 11, Java 17, Spring Boot 2, Quarkus 2 and Java EE 8. It has reached its End of Life and is no longer supported.
• Timefold 1.x is a replacement for OptaPlanner 9. It supports Java 17+, Spring Boot 3, Quarkus 3 and Jakarta EE 10.

Is Timefold Backward Compatible with OptaPlanner?

Yes, except for the branding changes.

Run timefold-migration to automatically change all your code locally. It’s a quick, single command for Maven or Gradle. Then test those changes and commit them. Alternatively, apply the following changes manually.

Timefold Solver 1.x is backward compatible with OptaPlanner 8.x, except that:

• Minimum Java 17 (LTS). Java 21 (LTS) and the latest Java version are also supported.
• The Maven/Gradle GAVs changed:
  • The groupId changed from org.optaplanner to ai.timefold.solver.
  • The artifactIds changed from optaplanner-* to timefold-solver-*.
  • ArtifactIds containing persistence- changed from optaplanner-persistence-* to timefold-solver-*.
    • For example, optaplanner-persistence-jackson changed to timefold-solver-jackson.
• The import statements changed accordingly:
  • import org.optaplanner…​; changed to import ai.timefold.solver…​;.
  • import org.optaplanner.persistence…​; changed to import ai.timefold.solver…​; too.
• The JEE dependencies changed from javax to jakarta to accommodate Spring 3 and Quarkus 3.
  • This is the same difference as between OptaPlanner 8.x and OptaPlanner 9.x.
• The OptaPlannerJacksonModule class is now called TimefoldJacksonModule.
• The deprecated scoreDRL support is removed, because Drools with its transitive dependencies have been removed entirely.
• The unsecure module persistence-xstream is removed, because of old, unresolved CVEs in XStream.
• The deprecated, undocumented ScoreHibernateType has been removed because of Jakarta. Use JPA’s ScoreConverter instead.

All other deprecated code remains, to make upgrading easy.

Timefold, a new company co-founded by OptaPlanner creator Geoffrey De Smet and Maarten Vandenbroucke, is excited to announce the fork of the popular open-source project, OptaPlanner. This marks the beginning of a new era in the operational planning optimization space, with Timefold Community offering enhanced performance, reduced distribution size, and improved documentation over its predecessor.

OptaPlanner, used by thousands of organizations worldwide, has matured over seventeen years, including a decade under Red Hat’s guidance. However, when Red Hat changed strategy last year, the project needed a new, sustainable future. Timefold was created to address this need and help the open-source project reach its full potential.

Timefold Community is an Apache-licensed open-source solver that optimizes operational planning. Backed by Timefold BV, a professional open-source company, the project offers a subscription with professional support and high-scalability features to fund the continued development of the free, open-source project. Timefold has received funding from Smartfin, an open-source minded venture capital firm that fully supports the company’s vision.

With a mission to free the world from wasteful scheduling, Timefold is dedicated to making planning optimization easy to understand and use. The platform leverages advanced AI solver algorithms and code programmable constraint models in Java, Python, and Kotlin, setting it apart from other solvers in the market. Timefold remains committed to being open-source, ensuring no barrier to entry for any team wishing to use the software.

As Timefold continues to grow, the company is actively engineers and experts to explore ways to make planning optimization even more accessible. To stay up to date with the latest developments, follow Timefold on Twitter or LinkedIn.

For more information about Timefold, visit timefold.ai or learn more about why we forked OptaPlanner.

Brussels, Belgium - Timefold, a Belgian-based commercial open source software startup focused on planning optimization through AI, announced today that it has raised 2 million euro in funding from Smartfin VC. The investment will enable Timefold to expand the technology, make it even easier to use, and extend its services to clients worldwide.

Timefold’s AI technology has been used to solve real-world planning problems, resulting in significant economic and ecological benefits. In several cases around the world involving up to tens of thousands of vehicles, Timefold has been able to reduce driving time by 25%. The technology has been applied to complex and high-scale cases where many other solvers have failed, setting Timefold apart from its competitors.

"We are delighted to have Smartfin VC as our investor." said Maarten Vandenbroucke, co-founder of Timefold. "Smartfin VC shares our vision of using AI to solve complex planning problems and create a positive impact in the world. They have been a great help in introducing Geoffrey and I as founders and have provided us with valuable insights into open source venture building."

Smartfin VC is an internationally connected fund that invests in early-stage startups with disruptive technologies. The fund focuses on investing in companies that have the potential to drastically impact markets or industries.

"We are excited to partner with Timefold." said Thomas Depuydt, general partner at Smartfin VC. "Timefold has demonstrated impressive results with its technology in the past, solving planning problems where other technologies have failed. We believe that Timefold has the potential to change the way we approach planning optimization and the usage of resources, and we look forward to working closely with them to achieve their goals."

For more information about Timefold and its AI-powered Open Source planning optimization technology, visit their website at https://timefold.ai.

Every new company needs a logo. So does Timefold. When starting a company, one of the most fun tasks is creating the logo. Far more exciting than VAT accounting, I can tell you.

Of course, a good logo is important: It’s hard to change. It must be able to stand the test of time. It should fit on a variety of media. So we hired a professional to help us: Ivo Blomme, a digital and brand designer with years of experience. He took us through the process of creating a good logo. Based on our input, he created these:

The left one is based on the rectangles of a physical calendar. The right one, with a fold in it, is based on a fold in space and time. Which logo would you have picked?

It was a though call, but we ended going for the second one. It’s loosely based on the idea of folding space and time:

Our designer even showed us how it would look on digital devices:

Now, we don’t have any plans to create a mobile app. But it would look good, wouldn’t it?

Drools is an extremely fast rule engine. Under the hood, OptaPlanner has used Drools as a score engine for ages. Today, we’re announcing a faster, lightweight alternative: Bavet.

Bavet is a feature of OptaPlanner. It is not a rule engine. It is a pure, single-purpose, incremental score calculation implementation of the ConstraintStreams API. Bavet is feature complete as of OptaPlanner 8.27.0.Final. You can switch from Drools to Bavet in a single line of code.

Twice as fast score calculation. Zero API changes.

Faster

For 20 diverse use cases, we compared Bavet and Drools for OptaPlanner score calculation. We ran JMH benchmarks on OpenJDK 17 (ParallelGC, Xmx1G) on a stable benchmark machine (Intel® Xeon® Silver (12 cores total / 24 threads) and 128 GiB RAM memory) without any other computational demanding processes running.

On average, Bavet is twice as fast as Drools for score calculation. In the Vehicle Routing Problem, Bavet is even three times as fast as Drools:

Use caseDroolsBavetSpeed upAverage:53,644136,765+132%cheaptime4,34914,543+234%cloudbalancing162,820608,204+274%coachShuttleGathering38,543111,991+191%conferenceScheduling1,0721,264+18%curriculumCourse32,27238,933+21%examination11,82125,712+118%flightCrewScheduling97,020126,563+30%investment68,935401,806+483%machineReassignment13,38428,619+114%meetingscheduling2,2912,158-6%nQueens177,528285,268+61%nurserostering10,65721,090+98%pas50,97147,551-7%projectjobscheduling23,71578,291+230%rockTour33,997152,472+348%taskAssigning10,53120,680+96%tennis106,172236,437+123%travelingtournament49,42877,143+56%tsp169,125430,384+154%vehicleRouting8,24726,187+218%Table 1. Score calculation speed on different use cases

Bavet is faster than Drools for 90% of the use cases. Of course, your mileage may vary. Turn on Bavet and if it’s not faster in your use case, let us know.

Drools and Bavet are both still improving. This performance race is far from over.

Scaling

Does Bavet scale well?

On commodity hardware, we ran a 5 minutes VRP benchmark on different dataset sizes, to compare how Drools and Bavet scale up:

belgium-n50-k10belgium-n100-k10belgium-n500-k20belgium-n1000-k20belgium-n2750-k55AverageDrools76,919/s58,365/s36,609/s23,394/s29,770/s45,011/sBavet307,290/s242,400/s147,595/s89,850/s91,115/s175,650/sSpeed up+299.50%+315.32%+303.17%+284.07%+206.06%+290.24%Table 2. Score calculation speed on different dataset sizes of VRP

Same story, but the performance gap does close as the scale goes up.

Not a rule engine

Bavet is not a rule engine. It deliberately doesn’t support inference, nor Complex Event Processing (CEP), nor other common business rule engine features:

OptaPlanner only requires a score engine. Its Drools implementation only uses a small subset of Drools’s features. Bavet on the other hand, is a score engine tailored to OptaPlanner. It’s part of OptaPlanner. It has no use outside of OptaPlanner.

For incremental score calculation, Bavet borrows techniques from the RETE algorithm and Drools’s Phreak algorithm. For example, the JoinNode in Bavet contains insert(), update() and retract() methods. But below the surface, it’s a very different implementation. Compare it with the method signatures of similar methods in the JoinNode in Drools.

History and naming

I created Bavet as a POC in 2019 and added it into OptaPlanner as an experimental, fast, incomplete feature. There it sat frozen. For 3 years. Until recently, when Lukáš Petrovický and me completed all missing features and refactored it to the performance sensation is today.

Naming wise, bavet is a Flemish (Dutch) slang word for a bib. Very useful if your baby is drooling. I came up with that name when we were eating with our kids at a spaghetti restaurant called Bavet, while facing this mural:

Ok, maybe I didn’t put much effort into that.

But it doesn’t really need a good name. It’s just one of OptaPlanner’s score calculation options. An implementation detail, really.

Stability

We believe Bavet is very stable. We successfully run our 48+ hours stress tests on Bavet regularly. These stress tests stomp out score corruption by solving a lot of datasets across many use cases.

More lightweight

In OpenShift and Kubernetes clouds, the size of pods matter. By using Bavet, you can slim down OptaPlanner’s classpath to exclude the Drools dependencies. The Bavet jar is 400 KB.

On the OptaPlanner hello-world quickstart, a Maven assembly of jar-with-dependencies with only Bavet included is 10 MB smaller:

Core dependenciesSizeReductionCore exclusionsAll (default)17.5 MB0%noneDrools CS only17.1 MB-2%optaplanner-constraint-drl, optaplanner-constraint-streams-bavetBavet CS only7.0 MB-60%optaplanner-constraint-drl, optaplanner-constraint-streams-droolsTable 3. Distribution size of jar-with-dependencies on OptaPlanner’s hello-world

By default, optaplanner-core includes both Drools and Bavet, so you have to explicitly exclude it in Maven or Gradle:

   <dependency>
     <groupId>org.optaplanner</groupId>
     <artifactId>optaplanner-core</artifactId>
     <exclusions>
       <exclusion>
         <groupId>org.optaplanner</groupId>
         <artifactId>optaplanner-constraint-drl</artifactId>
       </exclusion>
       <exclusion>
         <groupId>org.optaplanner</groupId>
         <artifactId>optaplanner-constraint-streams-drools</artifactId>
       </exclusion>
     </exclusions>
   </dependency>

This reduces optaplanner-core from 42 to 17 transitive dependencies. Specifically, all these jars are removed from your classpath:

\- org.optaplanner:optaplanner-constraint-streams-drools:...
  +- org.drools:drools-engine:...
  |  +- org.kie:kie-api:...
  |  +- org.kie:kie-internal:...
  |  +- org.drools:drools-core:...
  |  |  +- org.kie:kie-util-xml:...
  |  |  +- org.drools:drools-wiring-api:...
  |  |  +- org.drools:drools-wiring-static:...
  |  |  +- org.drools:drools-util:...
  |  |  \- commons-codec:commons-codec:...
  |  +- org.drools:drools-wiring-dynamic:...
  |  +- org.drools:drools-kiesession:...
  |  +- org.drools:drools-tms:...
  |  +- org.drools:drools-compiler:...
  |  |  +- org.drools:drools-drl-parser:...
  |  |  +- org.drools:drools-drl-extensions:...
  |  |  +- org.drools:drools-drl-ast:...
  |  |  +- org.kie:kie-memory-compiler:...
  |  |  +- org.drools:drools-ecj:...
  |  |  +- org.kie:kie-util-maven-support:...
  |  |  \- org.antlr:antlr-runtime:...
  |  +- org.drools:drools-model-compiler:...
  |  |  \- org.drools:drools-canonical-model:...
  |  \- org.drools:drools-model-codegen:...
  |     +- org.drools:drools-codegen-common:...
  |     +- com.github.javaparser:javaparser-core:...
  |     +- org.drools:drools-mvel-parser:...
  |     \- org.drools:drools-mvel-compiler:...
  \- org.drools:drools-alphanetwork-compiler:...

Bavet (optaplanner-constraint-streams-bavet) has no transitive dependencies (except for optaplanner-constraint-streams-common).

Try it out

First upgrade to OptaPlanner 8.27.0.Final or later, if you haven’t already. If you’re using the deprecated scoreDRL approach, migrate from scoreDRL to constraint streams first.

By default, OptaPlanner still uses Drools for constraint streams. To use Bavet instead, explicitly switch the ConstraintStreamImplType to BAVET:

Plain Java

Switch to Bavet in either your *.java file:

SolverFactory<TimeTable> solverFactory = SolverFactory.create(new SolverConfig()
       ...
       .withConstraintStreamImplType(ConstraintStreamImplType.BAVET)
       ...);

or in your solverConfig.xml:

 <scoreDirectorFactory>
   ...
   <constraintStreamImplType>BAVET</constraintStreamImplType>
 </scoreDirectorFactory>

Quarkus

Switch to Bavet in src/main/resources/application.properties:

quarkus.optaplanner.solver.constraintStreamImplType=BAVET

Spring

Switch to Bavet in src/main/resources/application.properties:

optaplanner.solver.constraintStreamImplType=BAVET

Share your results

Help us out. Try Bavet and let us know here how your score calculation speed changes. Look for the score calculation speed in the INFO log: it’s part of the Solving ended message.

Java 17 (released yesterday) comes with many new features and enhancements. However, most of those require code changes to benefit from. Except for performance. Simply switch your JDK installation and you get a free performance boost. But how much? Is it worth it? Let’s find out by comparing the benchmarks of JDK 17, JDK 16 and JDK 11.

Benchmark methodology

• Hardware: A stable machine without any other computational demanding processes running and with Intel® Xeon® Silver 4116 @ 2.1 GHz (12 cores total / 24 threads) and 128 GiB RAM memory, running RHEL 8 x86_64.
• JDKs (used to both compile and run):
  • JDK 11
  • openjdk 11.0.12 2021-07-20 OpenJDK Runtime Environment Temurin-11.0.12+7 (build 11.0.12+7) OpenJDK 64-Bit Server VM Temurin-11.0.12+7 (build 11.0.12+7, mixed mode)
  • JDK 16
  • openjdk 16.0.2 2021-07-20 OpenJDK Runtime Environment (build 16.0.2+7-67) OpenJDK 64-Bit Server VM (build 16.0.2+7-67, mixed mode, sharing)
  • JDK 17 (downloaded 2021-09-06)
  • openjdk 17 2021-09-14 OpenJDK Runtime Environment (build 17+35-2724) OpenJDK 64-Bit Server VM (build 17+35-2724, mixed mode, sharing)
• JVM options: -Xmx3840M and explicitly specify a garbage collector:
  • -XX:+UseG1GC for G1GC, the low latency garbage collector (the default in all three JDKs).
  • -XX:+UseParallelGC for ParallelGC, the high throughput garbage collector.
• Main class: org.optaplanner.examples.app.GeneralOptaPlannerBenchmarkApp from the module optaplanner-examples in OptaPlanner 8.10.0.Final.
  • Each run solves 11 planning problems with OptaPlanner, such as employee rostering, school timetabling and cloud optimization. Each planning problem runs for 5 minutes. Logging is set to INFO. The benchmark starts with a 30 second JVM warm up which is discarded.
  • Solving a planning problem involves no IO (except a few milliseconds during startup to load the input). A single CPU is completely saturated. It constantly creates many short-lived objects, and the GC collects them afterwards.
  • The benchmarks measure the number of scores calculated per second. Higher is better. Calculating a score for a proposed planning solution is non-trivial: it involves many calculations, including checking for conflicts between every entity and every other entity.
• Runs: Each JDK and each garbage collector combination is run 3 times sequentially. The results below is the average of those 3 runs.

Results

Java 11 (LTS) and Java 16 versus Java 17 (LTS)

AverageCloud balancingMachine reassignmentCourse schedulingExam schedulingNurse rosteringTraveling TournamentDataset 200c800cB1B10c7c8s2s3m1mh1nl14JDK 11 103,60696,700274,10337,42111,77913,66014,3548,9823,5853,3355,019JDK 16 109,20397,567243,09638,03113,95016,25115,2189,5283,8173,5085,472JDK 17 106,14798,069245,64542,09614,40616,92415,6199,7263,8023,6015,61811 → 178.66%2.45%1.42%-10.38%12.49%22.30%23.90%8.81%8.28%6.05%7.98%11.95%16 → 172.41%-2.80%0.51%1.05%10.69%3.27%4.14%2.63%2.08%-0.39%2.65%2.67%Table 1. Score calculation count per second with G1GC on different JDKs

AverageCloud balancingMachine reassignmentCourse schedulingExam schedulingNurse rosteringTraveling TournamentDataset 200c800cB1B10c7c8s2s3m1mh1nl14JDK 11 128,553121,974292,76148,33913,39715,54016,3929,8874,4094,1486,097JDK 16 128,723123,314281,88245,62216,24318,52817,74210,7444,6084,3486,578JDK 17 130,215124,498262,75345,05816,47918,90418,02310,8454,6584,4306,64111 → 176.54%1.29%2.07%-10.25%-6.79%23.00%21.64%9.95%9.68%5.63%6.80%8.92%16 → 170.37%1.16%0.96%-6.79%-1.24%1.45%2.03%1.59%0.94%1.08%1.89%0.96%Table 2. Score calculation count per second with ParallelGC on different JDKs

NoteLooking at the raw data of the 3 individual runs (not shown here), the Machine Reassignment numbers (B1 and B10) fluctuate a lot between runs on the same JDK and GC. Often by more than 10%. The other numbers don’t suffer from this unreliability.

It’s arguably better to ignore the Machine Reassignment numbers. But to avoid cherry-picking data concerns, these results and averages do include them.

G1GC versus ParallelGC on Java 17

AverageCloud balancingMachine reassignmentCourse schedulingExam schedulingNurse rostering^.Traveling TournamentDataset 200c800cB1B10c7c8s2s3m1mh1nl14G1GC 106,14798,069245,64542,09614,40616,92415,6199,7263,8023,6015,618ParallelGC 130,215124,498262,75345,05816,47918,90418,02310,8454,6584,4306,641G1 → ParallelGC16.39%22.67%26.95%6.96%7.04%14.39%11.69%15.39%11.50%22.50%23.01%18.20%Table 3. Score calculation count per second on JDK 17 with different GCs

Executive summary

On average, for OptaPlanner use cases, these benchmarks indicate that:

• Java 17 is 8.66% faster than Java 11 and 2.41% faster than Java 16 for G1GC (default).
• Java 17 is 6.54% faster than Java 11 and 0.37% faster than Java 16 for ParallelGC.
• The Parallel Garbage Collector is 16.39% faster than the G1 Garbage Collector.

No big surprises here: the latest JDK is faster and the high throughput garbage collector is faster than the low latency garbage collector.

Wait a minute here…​

When we benchmarked JDK 15, we saw that Java 15 was 11.24% faster than Java 11. Now, the gain of Java 17 over Java 11 is less. Does that mean that Java 17 is slower than Java 15?

Well, no. Java 17 is faster than Java 15 too. Those previous benchmarks were run on a different codebase (OptaPlanner 7.44 instead of 8.10). Don’t compare apples and oranges.

Conclusion

In conclusion, the performance gained in the JDK17 version is well worth the upgrade - at least for these use cases.

In addition, the fastest garbage collector for these use cases is still ParallelGC, instead of G1GC (the default).

Do you want OptaPlanner to run faster? Do you want to increase your score calculation speed, reaching great solutions sooner? Let me show you how to optimize your Constraint Streams constraints for performance and scalability. Turns out you only need to remember one advice:

Do less

The key to well-performing constraints is limiting the amount of data that flows through your Constraint Streams, which starts with joins. Consider a school timetabling problem, where a teacher must not have two overlapping lessons. This is how the lesson could look in Java:

    @PlanningEntity
    class Lesson {

        ...

        Teacher getTeacher() { ... }

        boolean overlaps(Lesson anotherLesson) { ... }

        boolean isCancelled() { ... }

        ...

    }

The simplest possible Constraint Stream we could write to penalize all overlapping lessons would then look like:

    constraintFactory.from(Lesson.class)
        .join(Lesson.class)
        .filter((leftLesson, rightLesson) ->
            !leftLesson.isCancelled()
	        && !rightLesson.isCancelled()
            && leftLesson.getTeacher()
                .equals(rightLesson.getTeacher())
            && leftLesson.overlaps(rightLesson))
        .penalize("Teacher lesson overlap", HardSoftScore.ONE_HARD)

What this Constraint Stream does is:

1. It creates all possible pairs of Lessons from the planning solution.
2. Then it filters out all the lessons that are cancelled, where the teachers do not match, or which do not overlap.
3. It penalizes all the remaining lesson pairs.

Do you see the problem here? The join creates a cross product between lessons, producing a match (also called a tuple) for every possible combination of two lessons, even though we know that many of these matches will not be penalized. This shows the problem in numbers:

In order to process a thousand lessons, our constraint first creates a cross product of 1 million pairs, only to throw away pretty much all of them before penalizing! If we can reduce the size of the cross product by half, only half of the time will be spent processing it. This is where the original advice comes into play: do less, by avoiding unrestricted cross product. Here’s how.

Filter before joining

As you can see from the first example, cancelled lessons are eventually filtered out after the join. Let’s see if we can remove them from the cross product instead. For the first lesson in the join (also called “left”), this is straightforward; we simply bring the cancellation check before the join like so:

    constraintFactory.from(Lesson.class)
        .filter(lesson -> !lesson.isCancelled())
        .join(Lesson.class)
        .filter((leftLesson, rightLesson) ->
            !rightLesson.isCancelled()
            && leftLesson.getTeacher() == rightLesson.getTeacher()
            && leftLesson.overlaps(rightLesson))
        .penalize("Teacher lesson overlap", HardSoftScore.ONE_HARD)

The cancelled lessons are no longer coming in from the left, which reduces the cross product. However, some cancelled lessons are still coming in from the right through the join. Here, we will use a little trick and join not with a Lesson class, but with a filtered nested Constraint Stream instead:

    constraintFactory.from(Lesson.class)
        .filter(lesson -> !lesson.isCancelled())
        .join(
            constraintFactory.from(Lesson.class)
                .filter(lesson -> !lesson.isCancelled()))
        .filter((leftLesson, rightLesson) ->
            leftLesson.getTeacher() == rightLesson.getTeacher()
            && leftLesson.overlaps(rightLesson))
        .penalize("Teacher lesson overlap", HardSoftScore.ONE_HARD)

As you can see, we’ve created a new Constraint Stream from Lesson, filtering before it entered our join. We have now applied the same improvement on both the left and right sides of the join, making sure it only creates a cross product of lessons which we care about. But we can still do better!

Prefer Joiners to filters

Filters are just a simple check if a tuple matches a predicate. If it does, it is sent downstream, otherwise the tuple is removed from the Constraint Stream. Each tuple needs to go through this check, and that means every pair of lessons will be evaluated. When a Lesson changes, all pairs with that Lesson will be re-evaluated, but not anymore:

    constraintFactory.from(Lesson.class)
        .filter(lesson -> !lesson.isCancelled())
        .join(
            constraintFactory.from(Lesson.class)
                .filter(lesson -> !lesson.isCancelled()),
	        Joiners.equal(Lesson::getTeacher))
        .filter((leftLesson, rightLesson) ->
			leftLesson.overlaps(rightLesson))
        .penalize("Teacher lesson overlap", HardSoftScore.ONE_HARD)

Notice that the Teacher equality check moved from the final filter to something called a Joiner. We are still saying the same thing - a Lesson pair will only be sent downstream if the Lessons share the same Teacher. Unlike the filter, this brings the performance benefit of indexing. Now when a Lesson changes, only the pairs with the matching Teacher will be re-evaluated. So even though the cross-product remains the same, we are doing much less work processing it.

The final filter now only performs one operation on the final cross product, and the Lesson pairs that get this far are already trimmed down in the most efficient way possible.

Remove more, earlier

In some cases, you may have an option to pick the order of your Joiners. In these situations, you should put first the Joiner that will remove more tuples than the others. This will reduce the size of your cross products faster.

Consider a new situation, where lessons also have rooms in which they happen. Although there are possibly dozens of teachers, there are only three rooms. Therefore the join should look like this:

    constraintFactory.from(Lesson.class)
        .join(Lesson.class,
            Joiners.equal(Lesson::getTeacher),
            Joiners.equal(Lesson::getRoom))
    ...

This way, we first create “buckets” for each of the many teachers, and these buckets will only contain a relatively small number of lessons per room. If we did it the other way around, there would be a small amount of large buckets, leading to much more iteration every time a lesson changes.

For that reason, it is generally recommended putting Joiners based on enum fields or boolean fields last.

Conclusion

The key to efficient constraints is the reduction of cross product. There are three main ways of reducing cross product in Constraint Streams:

1. Filtering before joining.
2. Preferring Joiners earlier to filtering later.
3. Applying the more restrictive Joiners first.

There are other optimization techniques as well, and we will discuss some of them in the future, but none of them will give as big a benefit as reducing the size of cross products.