Chapter 1. User Guide

Table of Contents

Solver introduction
What is a Solver?
Status of drools-solver
Building drools-solver and running an example
Solver examples
Introduction
The n queens example
The lesson schedule example
The traveling tournament example
The ITC2007 examination example
Solver configuration
Types of solvers
The Solver interface
Building a solver
The Solution interface
The starting solution
A simple filler algorithm
Solving a problem
Score calculation with a rule engine
Rule based score calculation
The ScoreDefinition interface
Tips and tricks
Local search solver
Overview
A move
Move generation
A step
Getting stuck in local optima
Deciding the next step
Best solution
Finish

Solver introduction

What is a Solver?

Drools-solver combines a search algorithm with the power of the drools rule engine to solve planning problems. Good examples of such planning problems include:

A planning problem consists out of a number of constraints. Generally, there are 3 types 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.

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

These constraints define the score function of a planning problem. This is where the drools rule engine comes into play: adding constraints with score rules is easy and scalable.

A planning problem has a number of solutions. Each solution has a score. There are 3 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 remote case that it's not a feasible solution because there are no feasible solutions.

Drools-solver supports several search algorithms to efficiently wade through the incredbly large number of possible solutions. It makes it easy to switch the search algorithm, by simply changing the solver configuration.

Status of drools-solver

Drools-solver is an beta module of Drools. 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. You can find this recipe in subversion and in every release.

You can download a beta release of Drools-solver from the drools download site. It is also available on the jboss maven repository.

Building drools-solver and running an example

You can also easily build it from source yourself. Check out drools from subversion and do a maven 2 build with the solver profile:

$ svn checkout http://anonsvn.jboss.org/repos/labs/labs/jbossrules/trunk/ drools
...
$ cd drools
$ mvn -Dmaven.test.skip clean install
...

After that, you can run any example directly from the command line, for example to run the n queens example, run:

$ cd drools-solver/drools-solver-examples/
$ mvn exec:exec -Dexec.mainClass="org.drools.solver.examples.nqueens.app.NQueensApp"
...

You will use drools-solver with the latest, unstable snapshot of the drools rule engine. If you would rather use a stable version of the drools rule engine, edit /drools-solver/pom.xml and overwrite the drools jar versions, before building and running the examples:

    <dependencyManagement>
        <dependencies>
            <dependency>
                <groupId>org.drools</groupId>
                <artifactId>drools-core</artifactId>
                <version>5.0.1</version>
            </dependency>
            <dependency>
                <groupId>org.drools</groupId>
                <artifactId>drools-compiler</artifactId>
                <version>5.0.1</version>
            </dependency>
        </dependencies>
    </dependencyManagement>