JBoss.org Community Documentation

- Prev
- Next

## Chapter 3. Planner configuration

## 3.1. Types of solvers

Different solvers solve problems in different ways. Each type has advantages and disadvantages. We 'll roughly discuss a few of the solver types here. You can safely skip this section.

### 3.1.1. Brute force

Brute force creates and evaluates every possible solution, usually by creating a search tree.

Advantages:

- It knows when it has found an optimal solution. If there is more then 1 optimal solution, it finds all optimal solutions.

- It is straightforward and simple to implement.

Disadvantages:

- It performs and scales horribly. Mostly unusable for a real-world problem due to time limitations.

Brute force is currently not implemented in Drools Planner. But we have plans to implement it in the future, as a reference for validating the output of the other solver types.

### 3.1.2. Branch and bound

Branch and bound is an improvement over brute force, as it prunes away subsets of solutions which cannot have a better solution than the best solution already found at that point.

Advantages:

- It knows when it has found an optimal solution. If there is more then 1 optimal solution, it can find all optimal solutions if needed.

- It can determine the bounds of a problem, which gives an indication of the quality of a solution.

Disadvantages:

- It still scales very badly. Mostly unusable for a real-world problem due to time limitations.

Branch and bound is currently not implemented in Drools Planner. But we have plans to implement it in the future, as a reference for validating the output of the other solver types.

### 3.1.3. Simplex

Simplex is an algorithm to find the numerical solution of a linear programming problem.

Advantages:

- It knows when it has found an optimal solution.

Disadvantages:

- It's complex and mathematical to implement constraints.

Drools Planner does not implement simplex.

### 3.1.4. Genetic algorithms

Advantages:

- It's scalable.

- Given a limited time, it can still deliver a pretty decent solution.

Disadvantages:

- It does not know when it has found an optimal solution.

- If the optimal score is unknown (which is usually the case), it must be told when to stop looking (for example based on time spend, user input, ...).

The genetic algorithm is currently not implemented in Drools Planner.

### 3.1.5. Local search (tabu search, simulated annealing, ...)

Local search starts from an initial solution and evolves that single solution into a mostly better and better solution. It uses a single search path of solutions, not a search tree. At each solution in this path it evaluates a number of moves on the solution and applies the most suitable move to take the step to the next solution.

Local search works a lot like a human planner: it uses a single search path and moves facts around to find a good feasible solution.

A simple local search can easily get stuck in a local optima, but improvements (such as tabu search and simulated annealing) address this problem.

Advantages:

- It's relatively simple and natural to implement constraints (at least in Drools Planner's implementation).

- It's very scalable, even when adding extra constraints (at least in Drools Planner's implementation).

- Given a limited time, it can still deliver a pretty decent solution.

Disadvantages:

- It does not know when it has found an optimal solution.

- If the optimal score is unknown (which is usually the case), it must be told when to stop looking (for example based on time spend, user input, ...).

Drools Planner implements local search, including tabu search and simulated annealing.

## 3.2. The size of real world problems

As a planning problem gets bigger, the search space tends to blow up really fast. It's not uncommon to see that it's possible to optimally plan 5 people in less then a second, while planning 6 people optimally would take years. Take a look at the problem size of the examples: many instances have a lot more possible solutions than the minimal number of atoms in the known universe (10^80).

The cold, hard reality is that for most real-world planning problems we will not find the optimal solution in our lifetimes. But that's OK, as long as we improve upon the solutions created by human planners (which is easy) or other systems.

Planning competitions (such as the International Timetabling Competition) show that local search variations (tabu search, simulated annealing, ...) usually perform best for real-world problems given real-world time limitations.

## 3.3. The Solver interface

Solving a planning problem with Drools Planner consists out of 4 steps:

1. Build a solver, for example a tabu search solver for any NQueens puzzle.

2. Set a starting solution on the solver, for example a 4 Queens puzzle instance.

3. Solve it.

4. Get the best solution found by the solver.

Every build-in solver implemented in Drools Planner implements the `Solver` interface:

    public interface Solver {

        void setStartingSolution(Solution solution);

        Solution getBestSolution();

        void solve();

        // ...

    }

There is normally no need to implement the `Solver` interface yourself.

A `Solver` should only be accessed from a single thread, except for the methods that are specifically javadocced as thread-safe.

## 3.4. Building a Solver

You can build a `Solver` instance with the `XmlSolverConfigurer`. Configure it with a solver configuration XML file:

        XmlSolverConfigurer configurer = new XmlSolverConfigurer();

        configurer.configure("/org/drools/planner/examples/nqueens/solver/nqueensSolverConfig.xml");

        Solver solver = configurer.buildSolver();

A basic solver configuration file looks something like this:

    <?xml version="1.0" encoding="UTF-8"?>

    <localSearchSolver>

        <scoreDrl>/org/drools/planner/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>

        <scoreDefinition>

            <scoreDefinitionType>SIMPLE</scoreDefinitionType>

        </scoreDefinition>

        <termination>

            <scoreAttained>0</scoreAttained>

        </termination>

        <selector>

            <moveFactoryClass>org.drools.planner.examples.nqueens.solver.NQueensMoveFactory</moveFactoryClass>

        </selector>

        <acceptor>

            <completeSolutionTabuSize>1000</completeSolutionTabuSize>

        </acceptor>

        <forager>

            <pickEarlyType>NEVER</pickEarlyType>

        </forager>

    </localSearchSolver>

This is a tabu search configuration for n queens. We 'll explain the various parts of a configuration later in this manual.

Drools Planner makes it relatively easy to switch a solver type just by changing the configuration. There's even a benchmark utility which allows you to play out different configurations against each other and report the most appropriate configuration for your problem. You could for example play out tabu search versus simulated annealing, on 4 queens and 64 queens.

### 3.4.1. Environment mode

A solver has a single `Random` instance. Some solver configurations use the `Random` instance a lot more than others. For example simulated annealing depends highly on random numbers, while tabu search only depends on it to deal with score ties. The environment mode influences the seed of that `Random` instance.

The environment mode also allows you to detect common bugs in your implementation.

You can set the environment mode in the solver configuration XML file:

    <localSearchSolver>

        <environmentMode>DEBUG</environmentMode>

        ...

    </localSearchSolver>

There are 3 environment modes:

#### 3.4.1.1. DEBUG

The debug mode is reproducible (see the reproducible mode) and also turns on assertions (such as assert that the undo Move is uncorrupted) to fail-fast on a bug in your Move implementation, your score rule, ...

The debug mode is slow.

It's recommended to write a test case which does a short run of your planning problem with debug mode on.

#### 3.4.1.2. REPRODUCIBLE (default)

The reproducible mode is the default mode because it is recommended during development. In this mode, 2 runs on the same computer will execute the same code in the same order. They will also yield the same result, except if they use a time based termination and they have a sufficiently large difference in allocated CPU time. This allows you to benchmark new optimizations (such as a new move implementation or a different minimalAcceptedSelection setting) fairly.

The reproducible mode is not much slower than the production mode.

In practice, this mode uses the default random seed, and it also disables certain concurrency optimizations (such as work stealing).

#### 3.4.1.3. PRODUCTION

The production mode is the fastest and the most robust, but not reproducible. It is recommended for a production environment.

The random seed is different on every run, which makes it more robust against an unlucky random seed. An unlucky random seed gives a bad result on a certain data set with a certain solver configuration. Note that in most use cases the impact of the random seed is relatively low on the result (even with simulated annealing). An occasional bad result is far more likely caused by another issue (such as a score trap).

## 3.5. The Solution interface

A Solver can only solve 1 problem instance at a time.

You need to present the problem as a starting `Solution` instance to the solver.

You need to implement the `Solution` interface:

    public interface Solution<S extends Score> {

        S getScore();

        void setScore(S score);

        Collection<? extends Object> getFacts();

        Solution<S> cloneSolution();

    }

For example, an `NQueens` instance just holds a list of all its queens:

    public class NQueens implements Solution<SimpleScore> {

        private List<Queen> queenList;

        // ...

    }

### 3.5.1. The getScore and setScore methods

A `Solution` requires a score property. The score property is null if the `Solution` is uninitialized or if the score has not yet been (re)calculated. The score property is usually typed to the specific `Score` implementation you use. For example, `NQueens` uses a `SimpleScore`:

        private SimpleScore score;

        public SimpleScore getScore() {

            return score;

        }

        public void setScore(SimpleScore score) {

            this.score = score;

        }

Most use cases use a `HardAndSoftScore` instead.

### 3.5.2. The getFacts method

All objects returned by the `getFacts()` method will be asserted into the drools working memory. Those facts can be used by the score rules. For example, `NQueens` just returns all `Queen` instances.

        public Collection<? extends Object> getFacts() {

            return queenList;

        }

### 3.5.3. The cloneSolution method

Most solvers use the `cloneSolution()` method to clone the solution each time they encounter a new best solution. The `NQueens` implementation just clones all `Queen` instances:

        public NQueens cloneSolution() {

            NQueens clone = new NQueens();

            List<Queen> clonedQueenList = new ArrayList<Queen>(queenList.size());

            for (Queen queen : queenList) {

                clonedQueenList.add(queen.clone());

            }

            clone.queenList = clonedQueenList;

            clone.score = score;

            return clone;

        }

The `cloneSolution()` method should clone no more and no less than the parts of the `Solution` that can change during planning. For example, in the curriculum course schedule example the lectures are cloned, but teachers, courses, timeslots, periods, rooms, ... are not cloned because only a lecture's appointed period or room changes during solving:

        /**

         * Clone will only deep copy the {@link #lectureList}.

         */

        public CurriculumCourseSchedule cloneSolution() {

            CurriculumCourseSchedule clone = new CurriculumCourseSchedule();

            ...

            clone.teacherList = teacherList;

            clone.curriculumList = curriculumList;

            clone.courseList = courseList;

            clone.dayList = dayList;

            clone.timeslotList = timeslotList;

            clone.periodList = periodList;

            clone.roomList = roomList;

            clone.unavailablePeriodConstraintList = unavailablePeriodConstraintList;

            List<Lecture> clonedLectureList = new ArrayList<Lecture>(lectureList.size());

            for (Lecture lecture : lectureList) {

                Lecture clonedLecture = lecture.clone();

                clonedLectureList.add(clonedLecture);

            }

            clone.lectureList = clonedLectureList;

            clone.score = score;

            return clone;

        }

## 3.6. The starting solution

First, you will need to make a starting solution and set that on the solver:

    solver.setStartingSolution(startingSolution);

### 3.6.1. A simple filler algorithm

For 4 queens we use a simple filler algorithm that creates a starting solution with all queens on a different x and on the same y (with y = 0).

Figure 3.1. Starting solution for the 4 queens puzzle

Here's how we generate it:

        private NQueens createNQueens(int n) {

            NQueens nQueens = new NQueens();

            nQueens.setId(0L);

            List<Queen> queenList = new ArrayList<Queen>(n);

            for (int i = 0; i < n; i++) {

                Queen queen = new Queen();

                queen.setId((long) i);

                queen.setX(i); // Different column

                queen.setY(0); // Same row

                queenList.add(queen);

            }

            nQueens.setQueenList(queenList);

            return nQueens;

        }

The starting solution will probably be far from optimal (or even feasible). Here, it's actually the worst possible solution. However, we 'll let the solver find a much better solution for us anyway.

### 3.6.2. StartingSolutionInitializer

For large problems, a simple filler algorithm like `createNQueens(int)` doesn't suffice. A (local search) solver starting from a bad starting solution wastes a lot of time to reach a solution which an initializer algorithm can generate in a fraction of that time.

An initializer algorithm usually works something like this:

- It sorts the unplanned elements in a queue according to some general rules, for example by exam student size.

- Next, it plans them in the order they come from the queue. Each element is put the best, still available spot.

- It doesn't change an already planned element. It exits when the queue is empty and all elements are planned.

Such an algorithm is very deterministic: it's really fast, but you can't give it more time to generate an even better solution. In some cases the solution it generates will be feasible, but in most cases it won't. You 'll need a real solver to get to a feasible or more optimal solution. Nevertheless you 'll want to such an initializer to give the real solver a serious head start. You can do this by implementing the `StartingSolutionInitializer` interface:

    public interface StartingSolutionInitializer extends SolverAware {

        boolean isSolutionInitialized(Solution solution);

        void initializeSolution(Solution solution);

    }

You'll need to set a (uninitialized) solution on the solver. Once the solver starts, it will first call the `StartingSolutionInitializer` to initialize the solution. If the `StartingSolutionInitializer` adds, edits or removes facts it needs to notify the workingMemory about this. It can use score calculation during its initialization process.

Here's an example on how you add the `StartingSolutionInitializer` to the configuration:

    <localSearchSolver>

        ...

        <startingSolutionInitializerClass>org.drools.planner.examples.examination.solver.solution.initializer.ExaminationStartingSolutionInitializer</startingSolutionInitializerClass>

        ...

    </localSearchSolver>

## 3.7. Solving a problem

Solving a problem is quite easy once you have a solver and the starting solution:

        solver.setStartingSolution(startingSolution);

        solver.solve();

        Solution bestSolution = solver.getBestSolution();

The `solve()` method will take a long time (depending on the problem size and the solver configuration). The solver will remember (actually clone) the best solution it encounters during its solving. Depending on a number factors (including problem size, how long you allow the solver to work, which solver type you use, ...), that best solution will be a feasible or even an optimal solution.

Figure 3.2. Best solution for the 4 queens puzzle (also an optimal solution)

After a problem is solved, you can reuse the same solver instance to solve another problem (of the same problem type).

- PrevChapter 2. Use cases and examples
- Top of page
- Front page
- NextChapter 4. Score calculation with a rule engine