JBoss.org Community Documentation

- Prev
- Next

## Chapter 1. Planner introduction

## 1.1. What is Drools Planner?

Drools Planner optimizes planning problems. It solves use cases, such as:

- Employee shift rostering: rostering 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: while minimizing waste: cutting paper, steel, carpet, ...

- Sport scheduling: planning football leagues, baseball leagues, ...

- Financial optimization: investment portfolio optimization, risk spreading, ...

Every organization faces planning problems: they have a number of things to do and a limited set of constrained resources to do them with.

Drools Planner enables normal JavaTM programmers to solve planning problems efficiently. Under the hood, it combines optimization algorithms (including Metaheuristics such as Tabu Search and Simulated Annealing) with the power of score calculation by a rule engine.

Drools Planner, like the rest of Drools, is business-friendly open source software under the Apache Software License 2.0 (layman's explanation).

## 1.2. What is a planning problem?

### 1.2.1. A planning problem is NP-complete

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.

Drools Planner does find a good solution in reasonable time for such planning problems.

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

  In practice, these are just like negative soft constraints, but with a positive weight.

Some toy 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 function (AKA fitness function) of a planning problem. Each solution of a planning problem can be graded with a score. Because we 'll define these constraints as rules in the Drools Expert rule engine, adding constraints in Drools Planner is easy and scalable.

### 1.2.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 a solution that does or does not break any number of constraints. Planning problems tend to have a incredibly large number of possible solutions. Most 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.

Counterintuitively, the number of possible solutions is huge (if calculated correctly), even with a small dataset. As you'll 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.

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

## 1.3. Status of Drools Planner

Drools Planner is production ready. The API is almost stable but backward incompatible changes can occur. With the recipe called `UpgradeFromPreviousVersionRecipe.txt` you can easily upgrade and deal with any backwards incompatible changes between versions. That recipe file is included in every release.

## 1.4. Getting Drools Planner and running the examples

### 1.4.1. Getting the release package and running the examples

You can download a release of Drools Planner from the Drools download site. To run an example, just open the directory `examples` and run the script (`runExamples.sh` on Linux and mac or `runExamples.bat` on windows) and pick an example in the GUI:

    $ cd examples
    $ ./runExamples.sh

    $ cd examples
    $ runExamples.bat

### 1.4.2. Get it with maven, gradle, ivy, buildr or ANT

The Drools Planner jars are available on the central maven repository (and the JBoss maven repository).

If you use maven, just add a dependency to `drools-planner-core` in your project's `pom.xml`:

        <dependency>

            <groupId>org.drools.planner</groupId>

            <artifactId>drools-planner-core</artifactId>

            <version>5.x</version>

        </dependency>

This is similar for gradle, ivy and buildr.

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.

### 1.4.3. Build it from source

You can also easily build it from source yourself. Clone drools from GitHub and do a maven 3 build:

    $ git clone git@github.com:droolsjbpm/drools-planner.git drools-planner
    ...
    $ cd drools-planner
    $ mvn -DskipTests clean install
    ...

After that, you can run any example directly from the command line, just run this command and pick an example:

    $ cd drools-planner-examples
    $ mvn exec:exec
    ...

## 1.5. Questions, issues and blog

Your questions and comments are welcome on the user mailing list. Start the subject of your mail with `[planner]`. You can read/write to the user mailing list without littering your mailbox through this web forum or this newsgroup.

Feel free to report an issue (such as a bug, improvement or a new feature request) for the Drools Planner code or for this manual to the drools issue tracker. Select the component `drools-planner`.

Pull requests (and patches) are very welcome and get priority treatment! Include the pull request link to a JIRA issue and optionally send a mail to the dev mailing list to get the issue fixed fast. By open sourcing your improvements, you 'll benefit from our peer review, improvements made upon your improvements and maybe even a thank you on our blog.

Check our blog and twitter (Geoffrey De Smet) for news and articles. If Drools Planner helps you solve your problem, don't forget to blog or tweet about it!

- Prev
- Top of page
- Front page
- NextChapter 2. Use cases and examples