JBoss.orgCommunity Documentation

Chapter 1. Planner introduction

1.1. What is OptaPlanner?
1.2. What is a planning problem?
1.2.1. A planning problem is NP-complete
1.2.2. A planning problem has (hard and soft) constraints
1.2.3. A planning problem has a huge search space
1.3. Download and run the examples
1.3.1. Get the release zip and run the examples
1.3.2. Run the examples in an IDE (IntelliJ, Eclipse, NetBeans)
1.3.3. Use OptaPlanner with Maven, Gradle, Ivy, Buildr or ANT
1.3.4. Build OptaPlanner from source
1.4. Status of OptaPlanner
1.5. Compatibility
1.6. Relationship with Drools and jBPM
1.7. Questions, issues and blog

OptaPlanner is a lightweight, embeddable planning engine that 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 discipline Operations Research).

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

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 JavaTM, runs on any JVM and is available in the Maven Central Repository too.

All the use cases above are probably NP-complete. In layman's terms, this 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 usually far from optimal.

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

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

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 Planner, it is easy to switch the optimization algorithm, by changing the solver configuration in a few lines of XML or code.

To try it now:

The Examples GUI application will open. Just pick an example:

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.

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 and manually verify that your classpath doesn't contain duplicate jars.

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 for a specific version of a specific module.

It's easy to build OptaPlanner from source:

  1. 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
    ...
  2. Build it with Maven:

    $ cd optaplanner
    $ mvn clean install -DskipTests
    ...

    Note

    The first time, Maven might take a lot time, because it needs to download jars.

  3. Run the examples:

    $ cd optaplanner-examples
    $ mvn exec:exec
    ...
  4. Edit the sources in your favorite IDE.

  5. Optional: use a Java profiler.

OptaPlanner is:

OptaPlanner has a public API:

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 entirely comfortable yet to write their signatures in stone.

OptaPlanner is 100% pure JavaTM and runs on any JVM 1.6 or higher.

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.

Questions and suggestions are welcome on our forum. Report any issue (such as a bug, improvement or a new feature request) for the OptaPlanner code or for this manual in our issue tracker.

Pull requests are very welcome and get priority treatment! By open sourcing your improvements, you 'll benefit from our peer review and from our improvements made upon your improvements.

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