Solver configuration

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.

Brute force

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

Advantages:

  • It finds 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 has a horrible performance and scalability. Mostly unusable for a real-world problem due to time constraints.

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

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 finds an optimal solution. If there is more then 1 optimal solution, it can find all optimal solutions if needed.

Disadvantages:

  • It still scales very badly.

Branch and bound is currently not implemented in drools-solver.

Simplex

Simplex turns all constraints and data into a big equation, which it transmutes into a mathematical function without local optima. It then finds an optimal solution to the planning problem by finding an optima of that mathematical function.

Advantages:

  • It finds an optimal solution.

Disadvantages:

  • It's usually rather complex and mathematical to implement constraints.

Drools-solver does not currently implement simplex.

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

Local search starts from an initial solution and evolves that single solution into a better and better solution. It uses a single search path of solutions. At each solution in this path it evaluates a number of possible 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-solver's implementation).

  • It's very scalable, even when adding extra constraints (at least in drools-solver's implementation).

  • It generally needs to worry about less negative hard constraints, because the move pattern can fulfill a number of the negative hard constraints.

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-solver implements local search, including tabu search and simulated annealing.

The Solver interface

Every build-in solver implemented in drools-solver implements the Solver interface:

public interface Solver {

    void setStartingSolution(Solution solution);

    Number getBestScore();
    Solution getBestSolution();
    
    void solve();

    // ...

}

Solving a planning problem with drools-solver 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.

A Solver should currently directly be accessed from a single thread. Support from accessing it from a different thread, for example to finish solving early or to change the problem facts in real-time, will be added in future releases.

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/solver/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/solver/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>
    <scoreCalculator>
        <scoreCalculatorType>SIMPLE</scoreCalculatorType>
    </scoreCalculator>
    <finish>
        <feasableScore>0.0</feasableScore>
    </finish>
    <selector>
        <moveFactoryClass>org.drools.solver.examples.nqueens.solver.NQueensMoveFactory</moveFactoryClass>
    </selector>
    <accepter>
        <completeSolutionTabuSize>1000</completeSolutionTabuSize>
    </accepter>
    <forager>
        <foragerType>MAX_SCORE_OF_ALL</foragerType>
    </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-solver 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 that 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. In any case, during your testing it's advisable to set that Random instance, so your tests are reproducible.

The Solution interface

A Solver can only solve 1 problem 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 {

    Collection<? extends Object> getFacts();

    Solution cloneSolution();

}

For example, an NQueens instance just holds a list of all it's queens:

public class NQueens implements Solution {

    private List<Queen> queenList;

    // ...

}

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

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

The cloneSolution() method should clone no more and no less than the parts of the Solution that can change during solving. For example, in the lesson schedule example the lessons are cloned, but teachers, groups and timeslots are not cloned because only a lesson's appointed timeslot changes during solving:

    /**
     * Clone will only deep copy the lessons
     */
    public LessonSchedule cloneSolution() {
        LessonSchedule clone = new LessonSchedule();
        clone.timeslotList = timeslotList; // No Deep copy
        clone.teacherList = teacherList; // No Deep copy
        clone.groupList = groupList; // No Deep copy
        List<Lesson> clonedLessonList = new ArrayList<Lesson>(lessonList.size());
        for (Lesson lesson : lessonList) {
            clonedLessonList.add(lesson.clone());
        }
        clone.lessonList = clonedLessonList;
        return clone;
    }

The starting solution

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

solver.setStartingSolution(startingSolution);

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 1.9. Starting solution for the 4 queens puzzle

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.

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 ussually 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 intialization process.

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

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

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 1.10. Best solution for the 4 queens puzzle (also an optimal solution)

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).