JBoss.orgCommunity Documentation

Chapter 3. Planner configuration

3.1. Overview
3.2. Solver configuration
3.2.1. Solver configuration by XML file
3.2.2. Solver configuration by Java API
3.3. Model your planning problem
3.3.1. Is this class a problem fact or planning entity?
3.3.2. Problem fact
3.3.3. Planning entity and planning variables
3.3.4. Planning value and planning value ranges
3.3.5. Planning problem and planning solution
3.4. Solver
3.4.1. The Solver interface
3.4.2. Solving a problem
3.4.3. Environment mode: Are there bugs in my code?
3.4.4. Logging level: What is the Solver doing?

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

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

        XmlSolverFactory solverFactory = new XmlSolverFactory();

        solverFactory.configure("/org/drools/planner/examples/nqueens/solver/nqueensSolverConfig.xml");
        Solver solver = solverFactory.buildSolver();

A solver configuration file looks something like this:


<?xml version="1.0" encoding="UTF-8"?>
<solver>
  <!-- Define the model -->
  <solutionClass>org.drools.planner.examples.nqueens.domain.NQueens</solutionClass>
  <planningEntityClass>org.drools.planner.examples.nqueens.domain.Queen</planningEntityClass>

  <!-- Define the score function -->
  <scoreDrl>/org/drools/planner/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>
  <scoreDefinition>
    <scoreDefinitionType>SIMPLE</scoreDefinitionType>
  </scoreDefinition>

  <!-- Configure the optimization algorithm(s) -->
  <termination>
    ...
  </termination>
  <constructionHeuristic>
    ...
  </constructionHeuristic>
  <localSearch>
    ...
  </localSearch>
</solver>

Notice the 3 parts in it:

We 'll explain these various parts of a configuration later in this manual.

Drools Planner makes it relatively easy to switch optimization algorithm(s) 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.

As an alternative to the XML file, a solver configuration can also be configured with the SolverConfig API:

        SolverConfig solverConfig = new SolverConfig();

        solverConfig.setSolutionClass(NQueens.class);
        Set<Class<?>> planningEntityClassSet = new HashSet<Class<?>>();
        planningEntityClassSet.add(Queen.class);
        solverConfig.setPlanningEntityClassSet(planningEntityClassSet);

        solverConfig.setScoreDrlList(
                Arrays.asList("/org/drools/planner/examples/nqueens/solver/nQueensScoreRules.drl"));
        ScoreDefinitionConfig scoreDefinitionConfig = solverConfig.getScoreDefinitionConfig();
        scoreDefinitionConfig.setScoreDefinitionType(
                ScoreDefinitionConfig.ScoreDefinitionType.SIMPLE);

        TerminationConfig terminationConfig = solverConfig.getTerminationConfig();
        // ...
        List<SolverPhaseConfig> solverPhaseConfigList = new ArrayList<SolverPhaseConfig>();
        ConstructionHeuristicSolverPhaseConfig constructionHeuristicSolverPhaseConfig
                = new ConstructionHeuristicSolverPhaseConfig();
        // ...
        solverPhaseConfigList.add(constructionHeuristicSolverPhaseConfig);
        LocalSearchSolverPhaseConfig localSearchSolverPhaseConfig = new LocalSearchSolverPhaseConfig();
        // ...
        solverPhaseConfigList.add(localSearchSolverPhaseConfig);
        solverConfig.setSolverPhaseConfigList(solverPhaseConfigList);
        Solver solver = solverConfig.buildSolver();

It is highly recommended to configure by XML file instead of this API. To dynamically configure a value at runtime, use the XML file as a template and extract the SolverConfig class with getSolverConfig() to configure the dynamic value at runtime:

        XmlSolverFactory solverFactory = new XmlSolverFactory();
        solverFactory.configure("/org/drools/planner/examples/nqueens/solver/nqueensSolverConfig.xml");

        SolverConfig solverConfig = solverFactory.getSolverConfig();
        solverConfig.getTerminationConfig().setMaximumMinutesSpend(userInput);
        Solver solver = solverConfig.buildSolver();

A planning entity is a JavaBean (POJO) that changes during solving, for example a Queen that changes to another row. A planning problem has multiple planning entities, for example for a single n queens problem, each Queen is a planning entity. But there's usually only 1 planning entity class, for example the Queen class.

A planning entity class needs to be annotated with the @PlanningEntity annotation.

Each planning entity class has 1 or more planning variables. It usually also has 1 or more defining properties. For example in n queens, a Queen is defined by it's Column and has a planning variable Row. This means that a Queen's column never changes during solving, while it's row does change.

@PlanningEntity
public class Queen {

    private Column column;

    // Planning variables: changes during planning, between score calculations.
    private Row row;

    // ... getters and setters
}

A planning entity class can have multiple planning variables. For example, a Lecture is defined by it's Course and it's index in that course (because 1 course has multiple lectures). Each Lecture needs to be scheduled into a Period and a Room so it has 2 planning variables (period and room). For example: the course Mathematics has 8 lectures per week, of which the first lecture is Monday morning at 08:00 in room 212.

@PlanningEntity
public class Lecture {

    private Course course;
    private int lectureIndexInCourse;

    // Planning variables: changes during planning, between score calculations.
    private Period period;
    private Room room;

    // ...
}

The solver configuration also needs to be made aware of each planning entity class:

<solver>
  ...
  <planningEntityClass>org.drools.planner.examples.nqueens.domain.Queen</planningEntityClass>
  ...
</solver>

Some uses cases have multiple planning entity classes. For example: route freight and trains into railway network arcs, where each freight can use multiple trains over it's journey and each train can carry multiple freights per arc. Having multiple planning entity classes directly raises the implementation complexity of your use case.

Some optimization algorithms work more efficiently if they have an estimation of which planning entities are more difficult to plan. For example: in bin packing bigger items are harder to fit, in course scheduling lectures with more students are more difficult to schedule and in n queens the middle queens are more difficult.

Therefore, you can set a difficultyComparatorClass to the @PlanningEntity annotation:

@PlanningEntity(difficultyComparatorClass = CloudProcessAssignmentDifficultyComparator.class)
public class CloudProcessAssignment {
    // ...
}
public class CloudProcessAssignmentDifficultyComparator implements Comparator<CloudProcessAssignment> {

    public int compare(CloudProcessAssignment a, CloudProcessAssignment b) {
        return new CompareToBuilder()
                .append(a.getCloudProcess().getRequiredMultiplicand(), b.getCloudProcess().getRequiredMultiplicand())
                .append(a.getCloudProcess().getId(), b.getCloudProcess().getId())
                .toComparison();
    }

}

Alternatively, you can also set a difficultyWeightFactoryClass to the @PlanningEntity annotation, so you have access to the rest of the problem facts from the solution too:

@PlanningEntity(difficultyWeightFactoryClass = QueenDifficultyWeightFactory.class)
public class Queen {
    // ...
}
public interface PlanningEntityDifficultyWeightFactory {

    Comparable createDifficultyWeight(Solution solution, Object planningEntity);

}
public class QueenDifficultyWeightFactory implements PlanningEntityDifficultyWeightFactory {

    public Comparable createDifficultyWeight(Solution solution, Object planningEntity) {
        NQueens nQueens = (NQueens) solution;
        Queen queen = (Queen) planningEntity;
        int distanceFromMiddle = calculateDistanceFromMiddle(nQueens.getN(), queen.getColumnIndex());
        return new QueenDifficultyWeight(queen, distanceFromMiddle);
    }

    // ...

    public static class QueenDifficultyWeight implements Comparable<QueenDifficultyWeight> {

        private final Queen queen;
        private final int distanceFromMiddle;

        public QueenDifficultyWeight(Queen queen, int distanceFromMiddle) {
            this.queen = queen;
            this.distanceFromMiddle = distanceFromMiddle;
        }

        public int compareTo(QueenDifficultyWeight other) {
            return new CompareToBuilder()
                    // The more difficult queens have a lower distance to the middle
                    .append(other.distanceFromMiddle, distanceFromMiddle) // Decreasing
                    .append(queen.getColumnIndex(), other.queen.getColumnIndex())
                    .toComparison();
        }

    }

}

None of the current planning variable state may be used to compare planning entities. They are likely to be null anyway. For example, a Queen's row variable may not be used.

Some optimization algorithms work more efficiently if they have an estimation of which planning values are stronger, which means they are more likely to satisfy a planning entity. For example: in bin packing bigger containers are more likely to fit an item and in course scheduling bigger rooms are less likely to break the student capacity constraint.

Therefore, you can set a strengthComparatorClass to the @PlanningVariable annotation:

    @PlanningVariable(strengthComparatorClass = CloudComputerStrengthComparator.class)
    // ...
    public CloudComputer getCloudComputer() {
        // ...
    }
public class CloudComputerStrengthComparator implements Comparator<CloudComputer> {

    public int compare(CloudComputer a, CloudComputer b) {
        return new CompareToBuilder()
                .append(a.getMultiplicand(), b.getMultiplicand())
                .append(b.getCost(), a.getCost()) // Descending (but this is debatable)
                .append(a.getId(), b.getId())
                .toComparison();
    }

}

Alternatively, you can also set a strengthWeightFactoryClass to the @PlanningVariable annotation, so you have access to the rest of the problem facts from the solution too:

    @PlanningVariable(strengthWeightFactoryClass = RowStrengthWeightFactory.class)
    // ...
    public Row getRow() {
        // ...
    }
public interface PlanningValueStrengthWeightFactory {

    Comparable createStrengthWeight(Solution solution, Object planningValue);

}
public class RowStrengthWeightFactory implements PlanningValueStrengthWeightFactory {

    public Comparable createStrengthWeight(Solution solution, Object planningValue) {
        NQueens nQueens = (NQueens) solution;
        Row row = (Row) planningValue;
        int distanceFromMiddle = calculateDistanceFromMiddle(nQueens.getN(), row.getIndex());
        return new RowStrengthWeight(row, distanceFromMiddle);
    }

    // ...

    public static class RowStrengthWeight implements Comparable<RowStrengthWeight> {

        private final Row row;
        private final int distanceFromMiddle;

        public RowStrengthWeight(Row row, int distanceFromMiddle) {
            this.row = row;
            this.distanceFromMiddle = distanceFromMiddle;
        }

        public int compareTo(RowStrengthWeight other) {
            return new CompareToBuilder()
                    // The stronger rows have a lower distance to the middle
                    .append(other.distanceFromMiddle, distanceFromMiddle) // Decreasing (but this is debatable)
                    .append(row.getIndex(), other.row.getIndex())
                    .toComparison();
        }

    }

}

None of the current planning variable state in any of the planning entities may be used to compare planning values. They are likely to be null anyway. For example, None of the row variables of any Queen may be used to determine the strength of a Row.

Most optimization algorithms use the cloneSolution() method to clone the solution each time they encounter a new best solution (so they can recall it later) or to work with multiple solutions in parallel.

The NQueens implementation only deep clones all Queen instances. When the original solution is changed during planning, by changing a Queen, the clone stays the same.

    /**

     * Clone will only deep copy the {@link #queenList}.
     */
    public NQueens cloneSolution() {
        NQueens clone = new NQueens();
        clone.id = id;
        clone.= n;
        clone.columnList = columnList;
        clone.rowList = rowList;
        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 only deep clone the planning entities. Notice that the problem facts, such as Column and Row are normally not cloned: even their List instances are not cloned.

Build a Solution instance to represent your planning problem, so you can set it on the Solver as the planning problem to solve. For example in n queens, an NQueens instance is created with the required Column and Row instances and every Queen set to a different column and every row set to null.

    private NQueens createNQueens(int n) {

        NQueens nQueens = new NQueens();
        nQueens.setId(0L);
        nQueens.setN(n);
        List<Column> columnList = new ArrayList<Column>(n);
        for (int i = 0; i < n; i++) {
            Column column = new Column();
            column.setId((long) i);
            column.setIndex(i);
            columnList.add(column);
        }
        nQueens.setColumnList(columnList);
        List<Row> rowList = new ArrayList<Row>(n);
        for (int i = 0; i < n; i++) {
            Row row = new Row();
            row.setId((long) i);
            row.setIndex(i);
            rowList.add(row);
        }
        nQueens.setRowList(rowList);
        List<Queen> queenList = new ArrayList<Queen>(n);
        long id = 0;
        for (Column column : columnList) {
            Queen queen = new Queen();
            queen.setId(id);
            id++;
            queen.setColumn(column);
            // Notice that we leave the PlanningVariable properties (row) on null
            queenList.add(queen);
        }
        nQueens.setQueenList(queenList);
        return nQueens;
    }

Usually, most of this data comes from your data layer, and your Solution implementation just aggregates that data and creates the uninitialized planning entity instances to plan:

        private void createLectureList(CurriculumCourseSchedule schedule) {
            List<Course> courseList = schedule.getCourseList();
            List<Lecture> lectureList = new ArrayList<Lecture>(courseList.size());
            for (Course course : courseList) {
                for (int i = 0; i < course.getLectureSize(); i++) {
                    Lecture lecture = new Lecture();
                    lecture.setCourse(course);
                    lecture.setLectureIndexInCourse(i);
                    // Notice that we leave the PlanningVariable properties (period and room) on null
                    lectureList.add(lecture);
                }
            }
            schedule.setLectureList(lectureList);
        }

The environment mode allows you to detect common bugs in your implementation. It does not affect the logging level.

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


<solver>
  <environmentMode>DEBUG</environmentMode>
  ...
</solver>

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.

There are 4 environment modes:

The best way to illuminate the black box that is a Solver, is to play with the logging level:

For example, set it to DEBUG logging, to see when the phases end and how fast steps are taken:

INFO  Sovling started: time spend (0), score (null), new best score (null), random seed (0).
DEBUG     Step index (0), time spend (1), score (0), initialized planning entity (col2@row0).
DEBUG     Step index (1), time spend (3), score (0), initialized planning entity (col1@row2).
DEBUG     Step index (2), time spend (4), score (0), initialized planning entity (col3@row3).
DEBUG     Step index (3), time spend (5), score (-1), initialized planning entity (col0@row1).
INFO  Phase construction heuristic finished: step total (4), time spend (6), best score (-1).
DEBUG     Step index (0), time spend (10), score (-1),     best score (-1), accepted move size (12) for picked step (col1@row2 => row3).
DEBUG     Step index (1), time spend (12), score (0), new best score (0), accepted move size (12) for picked step (col3@row3 => row2).
INFO  Phase local search ended: step total (2), time spend (13), best score (0).
INFO  Solving ended: time spend (13), best score (0), average calculate count per second (4846).

All time spends are in milliseconds.

Everything is logged to SLF4J, which is a simple logging facade that can delegate any log to Logback, Apache Commons Logging, Log4j or java.util.logging. Add a dependency to the logging adaptor for your logging framework of choice. If you're not using any logging framework yet, you can use Logback by adding this Maven dependency:

    <dependency>
      <groupId>ch.qos.logback</groupId>
      <artifactId>logback-classic</artifactId>
      <version>1.x</version>
    </dependency>

Configure the logging level on the package org.drools.planner. For example:

In Logback, configure it in your logback.xml file:

<configuration>

  <logger name="org.drools.planner" level="debug"/>

  ...

<configuration>

In Log4J, configure it in your log4j.xml file:

<log4j:configuration xmlns:log4j="http://jakarta.apache.org/log4j/">

  <category name="org.drools.planner">
    <priority value="debug" />
  </category>

  ...

</log4j:configuration>