Chapter 1. OptaPlanner Introduction

OptaPlanner is a lightweight, embeddable constraint satisfaction engine which optimizes planning problems. It solves use cases such as:

Employee shift rostering: timetabling nurses, repairmen, ...
Agenda scheduling: scheduling meetings, appointments, maintenance jobs, advertisements, ...
Educational timetabling: scheduling lessons, courses, exams, conference presentations, ...
Vehicle routing: planning vehicles (trucks, trains, boats, airplanes, ...) with freight and/or people
Bin packing: filling containers, trucks, ships and storage warehouses, but also cloud computers nodes, ...
Job shop scheduling: planning car assembly lines, machine queue planning, workforce task planning, ...
Cutting stock: minimizing waste while cutting paper, steel, carpet, ...
Sport scheduling: planning football leagues, baseball leagues, ...
Financial optimization: investment portfolio optimization, risk spreading, ...

Every organization faces planning problems: provide products or services with a limited set of constrained resources (employees, assets, time and money). OptaPlanner optimizes such planning to do more business with less resources. This is known as Constraint Satisfaction Programming (which is part of the Operations Research discipline).

OptaPlanner helps normal Java^TM programmers solve constraint satisfaction problems efficiently. Under the hood, it combines optimization heuristics and metaheuristics with very efficient score calculation.

1.2. Requirements

OptaPlanner is open source software, released under the Apache Software License 2.0. This license is very liberal and allows reuse for commercial purposes. Read the layman's explanation.

OptaPlanner is 100% pure Java^TM and runs on any JVM 1.6 or higher. It integrates very easily with other Java^TM technologies. OptaPlanner is available in the Maven Central Repository.

1.3. What is a Planning Problem?

1.3.1. A Planning Problem is NP-complete or NP-hard

All the use cases above are probably NP-complete or harder. In layman's terms, NP-complete means:

It's easy to verify a given solution to a problem in reasonable time.
There is no silver bullet to find the optimal solution of a problem in reasonable time (*).

Note

(*) At least, none of the smartest computer scientists in the world have found such a silver bullet yet. But if they find one for 1 NP-complete problem, it will work for every NP-complete problem.

In fact, there's a $ 1,000,000 reward for anyone that proves if such a silver bullet actually exists or not.

The implication of this is pretty dire: solving your problem is probably harder than you anticipated, because the 2 common techniques won't suffice:

A Brute Force algorithm (even a smarter variant) will take too long.
A quick algorithm, for example in bin packing, putting in the largest items first, will return a solution that is far from optimal.

By using advanced optimization algorithms, OptaPlanner does find a good solution in reasonable time for such planning problems.

1.3.2. A Planning Problem Has (Hard and Soft) Constraints

Usually, a planning problem has at least 2 levels of constraints:

A (negative) hard constraint must not be broken. For example: 1 teacher can not teach 2 different lessons at the same time.
A (negative) soft constraint should not be broken if it can be avoided. For example: Teacher A does not like to teach on Friday afternoon.

Some problems have positive constraints too:

A positive soft constraint (or reward) should be fulfilled if possible. For example: Teacher B likes to teach on Monday morning.

Some basic problems (such as N Queens) only have hard constraints. Some problems have 3 or more levels of constraints, for example hard, medium and soft constraints.

These constraints define the score calculation (AKA fitness function) of a planning problem. Each solution of a planning problem can be graded with a score. With OptaPlanner, score constraints are written in an Object Oriented language, such as Java code or Drools rules. Such code is easy, flexible and scalable.

1.3.3. A Planning Problem Has a Huge Search Space

A planning problem has a number of solutions. There are several categories of solutions:

A possible solution is any solution, whether or not it breaks any number of constraints. Planning problems tend to have an incredibly large number of possible solutions. Many of those solutions are worthless.
A feasible solution is a solution that does not break any (negative) hard constraints. The number of feasible solutions tends to be relative to the number of possible solutions. Sometimes there are no feasible solutions. Every feasible solution is a possible solution.
An optimal solution is a solution with the highest score. Planning problems tend to have 1 or a few optimal solutions. There is always at least 1 optimal solution, even in the case that there are no feasible solutions and the optimal solution isn't feasible.
The best solution found is the solution with the highest score found by an implementation in a given amount of time. The best solution found is likely to be feasible and, given enough time, it's an optimal solution.

Counterintuitively, the number of possible solutions is huge (if calculated correctly), even with a small dataset. As you can see in the examples, most instances have a lot more possible solutions than the minimal number of atoms in the known universe (10^80). Because there is no silver bullet to find the optimal solution, any implementation is forced to evaluate at least a subset of all those possible solutions.

OptaPlanner supports several optimization algorithms to efficiently wade through that incredibly large number of possible solutions. Depending on the use case, some optimization algorithms perform better than others, but it's impossible to tell in advance. With OptaPlanner, it is easy to switch the optimization algorithm, by changing the solver configuration in a few lines of XML or code.

1.4. Download and Run the Examples

1.4.1. Get the Release .zip and Run the Examples

To try it now:

Download a release zip of OptaPlanner from the OptaPlanner website and unzip it.
Open the directory examples and run the script.
Linux or Mac:
```
$ cd examples
$ ./runExamples.sh
```
Windows:
```
$ cd examples
$ runExamples.bat
```

The Examples GUI application will open. Pick an example to try it out:

Note

OptaPlanner itself has no GUI dependencies. It runs just as well on a server or a mobile JVM as it does on the desktop.

Besides the GUI examples, there are also a set of webexamples to try out:

Download a JEE application server, such as JBoss EAP or WildFly and unzip it.
Download a release zip of OptaPlanner from the OptaPlanner website and unzip it.
Open the directory webexamples and deploy the optaplanner-webexamples-*.war file on the JEE application server.
Surf to http://localhost:8080/optaplanner-webexamples-*/ (replace the * with the actual version).

Note

The webexamples (but not OptaPlanner itself) require several JEE API's (such as Servlet, JAX-RS and CDI) to run. To successfully deploy optaplanner-webexamples-*.war on a servlet container (such as Jetty or Tomcat), instead of on a real JEE application server (such as WildFly), add the missing implementation libraries (for example RestEasy and Weld) in the war manually.

Pick an example to try it out, such as the Vehicle Routing example:

1.4.2. Run the Examples in an IDE (IntelliJ, Eclipse, NetBeans)

To run the examples in your favorite IDE:

Configure your IDE:
- In IntelliJ IDEA, NetBeans or a non-vanilla Eclipse, just open the file examples/sources/pom.xml as a new project, the maven integration will take care of the rest.
- In a vanilla Eclipse (which lacks the M2Eclipse plugin), open a new project for the directory examples/sources.
  - Add all the jars to the classpath from the directory binaries and the directory examples/binaries, except for the file examples/binaries/optaplanner-examples-*.jar.
  - Add the Java source directory src/main/java and the Java resources directory src/main/resources.
Create a run configuration:
- Main class: org.optaplanner.examples.app.OptaPlannerExamplesApp
- VM parameters (optional): -Xmx512M -server
Run that run configuration.

To run a specific example directly and skip the example selection window, run its App class (for example CloudBalancingApp) instead of OptaPlannerExamplesApp.

1.4.3. Use OptaPlanner with Maven, Gradle, Ivy, Buildr or ANT

The OptaPlanner jars are also available in the central maven repository (and also in the JBoss maven repository).

If you use Maven, add a dependency to optaplanner-core in your project's pom.xml:

    <dependency>
      <groupId>org.optaplanner</groupId>
      <artifactId>optaplanner-core</artifactId>
    </dependency>

This is similar for Gradle, Ivy and Buildr. To identify the latest version, check the central maven repository.

Because you might end up using other OptaPlanner modules too, it's recommended to import the optaplanner-bom in Maven's dependencyManagement so the OptaPlanner version is specified only once:

  <dependencyManagement>
    <dependencies>
      <dependency>
        <groupId>org.optaplanner</groupId>
        <artifactId>optaplanner-bom</artifactId>
        <type>pom</type>
        <version>...</version>
        <scope>import</scope>
      </dependency>
      ...
    </dependencies>
  </dependencyManagement>

If you're still using ANT (without Ivy), copy all the jars from the download zip's binaries directory in your classpath.

Note

The download zip's binaries directory contains far more jars then optaplanner-core actually uses. It also contains the jars used by other modules, such as optaplanner-benchmark.

Check the maven repository pom.xml files to determine the minimal dependency set of a specific module (for a specific version).

1.4.4. Build OptaPlanner from Source

It's easy to build OptaPlanner from source:

Set up Git and clone optaplanner from GitHub (or alternatively, download the zipball):
```
$ git clone git@github.com:droolsjbpm/optaplanner.git optaplanner
...
```
Note
If you don't have a GitHub account or your local Git installation isn't configured with it, use this command instead, to avoid an authentication issue:
```
$ git clone https://github.com/droolsjbpm/optaplanner.git optaplanner
...
```
Build it with Maven:
```
$ cd optaplanner
$ mvn clean install -DskipTests
...
```
Note
The first time, Maven might take a long time, because it needs to download jars.

Run the examples:

$ cd optaplanner-examples
$ mvn exec:java
...

Edit the sources in your favorite IDE.
Optional: use a Java profiler.

1.5. Governance

1.5.1. Status of OptaPlanner

OptaPlanner is:

Stable: Heavily tested with unit, integration and stress tests.
Reliable: Used in production across the world.
Scalable: One of the examples handles 50 000 variables with 5 000 variables each, multiple constraint types and billions of possible constraint matches.
Documented: See this detailed manual or one of the many examples.

1.5.2. Backwards Compatibility

OptaPlanner separates its API and implementation:

Public API: All classes in the package namespace org.optaplanner.core.api are 100% backwards compatible in future releases (especially minor and hotfix releases). In rare circumstances, if the major version number changes, a few specific classes might have a few backwards incompatible changes, but those will be clearly documented in the recipe UpgradeFromPreviousVersionRecipe.txt.
XML configuration: The XML solver configuration is backwards compatible for all elements, except for elements that require the use of non public API classes. The XML solver configuration is defined by the classes in the package namespace org.optaplanner.core.config.
Implementation classes: All classes in the package namespace org.optaplanner.core.impl are not backwards compatible: they will change in future major or minor releases (but probably not in hotfix releases). The recipe UpgradeFromPreviousVersionRecipe.txt describes every such relevant change and on how to quickly deal with it when upgrading to a newer version. That recipe file is included in every release zip.

Note

This documentation covers some impl classes too. Those documented impl classes are reliable and safe to use (unless explicitly marked as experimental in this documentation), but we're just not entirely comfortable yet to write their signatures in stone.

1.5.3. Community and Support

For news and articles, check our blog, Google+ (OptaPlanner, Geoffrey De Smet) and twitter (OptaPlanner, Geoffrey De Smet). If OptaPlanner helps you, help us by blogging or tweeting about it!

Public questions are welcome on our community forum. Bugs and feature requests are welcome in our issue tracker. Pull requests are very welcome on GitHub and get priority treatment! By open sourcing your improvements, you 'll benefit from our peer review and from our improvements made on top of your improvements.

Red Hat sponsors OptaPlanner development by employing the core team. For enterprise support and consulting, take a look at the BRMS and BPMS products (which contain OptaPlanner) or contact Red Hat.

1.5.4. Relationship with Drools and jBPM

OptaPlanner is part of the KIE group of projects. It releases regularly (often once or twice per month) together with the Drools rule engine and the jBPM workflow engine.

See the architecture overview to learn more about the optional integration with Drools.