JBoss.orgCommunity Documentation

Chapter 3. Planner configuration

3.1. Types of solvers
3.1.1. Simplex
3.1.2. Genetic algorithms
3.1.3. Local search (tabu search, simulated annealing, ...)
3.2. The size of real world problems
3.3. The Solver interface
3.4. Building a Solver
3.4.1. Environment mode
3.5. The Solution interface
3.5.1. The getScore and setScore methods
3.5.2. The getFacts method
3.5.3. The cloneSolution method
3.6. The starting solution
3.6.1. A simple filler algorithm
3.7. Solving a problem

TODO remove this section

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.

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 do better than the solutions created by human planners (which is easy) and other software.

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.

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

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.

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.

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 4 environment modes:

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<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;
    // ...
}

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;
    }

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

solver.setStartingSolution(startingSolution);

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.


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